我們知道斐波那契數(shù)列的實(shí)現(xiàn)方式是缸浦，下標(biāo)為1或者2時(shí)垢乙，其值就是1查近，當(dāng)下標(biāo)大于3時(shí)眉踱，則f(n) = f(n-1) + f(n-2)；下面編寫(xiě)了遞歸與非遞歸兩種實(shí)現(xiàn)方式（Java代碼）：
public class Fibonacci {
public static void main(String []args) {
System.out.println(FibonacciLoop(40));
System.out.println(FibonacciNoLoop(40));
}
public static long FibonacciLoop(int index) {
if (index <= 0) {
System.out.println("Parameter Error!");
return -1;
}
if (index == 1 || index == 2) {
return 1;
}
else {
return FibonacciLoop(index - 1) + FibonacciLoop(index - 2);
}
}
public static long FibonacciNoLoop(int index) {
if (index <= 0) {
System.out.println("Parameter Error!");
return -1;
}
if (index == 1 || index == 2) {
return 1;
}
long m = 1L;
long n = 1L;
long result = 0;
for (int i = 3; i <= index; i++) {
result = m + n;
m = n;
n = result;
}
return result;
}
}
測(cè)試當(dāng)下標(biāo)為40時(shí)霜威，結(jié)果為102334155谈喳。
斐波那契數(shù)列還有很多衍生的問(wèn)題，比如青蛙跳臺(tái)階問(wèn)題：
一只青蛙一次可以跳上1級(jí)臺(tái)階侥祭，也可以跳上2級(jí)叁执。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
可以把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)矮冬，記為f(n)谈宛。
當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：
一是第一次只跳1級(jí)胎署，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目吆录，即為f(n-1);
另一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下n-2級(jí)臺(tái)階的跳法數(shù)目琼牧，即為f(n-2)恢筝。
因此哀卫，n級(jí)臺(tái)階的不同跳法的總數(shù)f(n)=f(n-1)+f(n-2)。
遞歸與非遞歸的Java代碼撬槽。
public static long FrogJumpLoop(int n) {
if (n <= 0) {
System.out.println("Parameter Error!");
return -1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
else {
return FrogJumpLoop(n - 1) + FrogJumpLoop(n - 2);
}
}
public static long FrogJumpNoLoop(int n) {
if (n <= 0) {
System.out.println("Parameter Error!");
return -1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
long step1 = 1L;
long step2 = 2L;
long result = 0;
for (int i = 3; i <= n; i++) {
result = step1 + step2;
step1 = step2;
step2 = result;
}
return result;
}
其他關(guān)于斐波那契變形的題目可以參考博客：http://blog.csdn.net/u010177286/article/details/47129019
