古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月的兔子总数为多少对? (斐波那契数列)
时间: 2023-09-13 14:05:15 浏览: 655
这是一个经典的斐波那契数列问题。
在这个问题中,兔子的生长情况可以看作是一种斐波那契数列,即每个月的兔子对数都等于前两个月兔子对数之和。假设第一个月有1对兔子,第二个月有1对兔子,那么第三个月就会有2对兔子(第一对兔子生了一对小兔子),第四个月会有3对兔子(第二对兔子也生了一对小兔子),以此类推。
因此,第n个月的兔子对数可以通过斐波那契数列的公式进行计算,即:
```
f(n) = f(n-1) + f(n-2)
```
其中f(1) = f(2) = 1。根据这个公式,可以写出如下的Java代码:
```java
public static int fibonacci(int n) {
if (n <= 2) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
```
这个代码可以递归地计算第n个月的兔子对数,时间复杂度为O(2^n),不太适合计算较大的n值。为了提高效率,可以使用循环来计算斐波那契数列,如下所示:
```java
public static int fibonacci(int n) {
if (n <= 2) {
return 1;
} else {
int a = 1, b = 1, c;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
}
```
这个代码使用循环计算斐波那契数列,时间复杂度为O(n),效率更高。
阅读全文