不使用遞歸和數(shù)組求解斐波那契數(shù)列
題目：
斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
用戶輸入項(xiàng)數(shù)完就告訴他該項(xiàng)的值（要求不使用遞歸和數(shù)組）
解：
核心代碼如下：
public int run22(int n) {
int result = 1;
if (n > 2) {
int first = 1;
int second = 1;
int third = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j == (i - 2)) {
first = second;
}
if (j == (i - 1)) {
second = third;
}
if (j == i) {
third = first + second;
}
}
result = third;
}
}
return result;
}
/**
不用遞歸求菲波那切數(shù)列：
1,1,2,3,5,8.....
f s t
f s t
f s t
*/
public int test7(int n) {
int f = 1, s = 1, t = 1;
if (n > 2) {
for (int i = 3; i <= n; i++) {
f = s;
s = t;
t = f + s;
}
return t;
} else {
return f;
}
}
使用數(shù)組的核心代碼：
public int run21(int n) {
int result = 1;
int[] array = new int[100];
for (int i = 0; i < n; i++) {
array[i] = 1;
if (i > 1) {
array[i] = array[i - 1] + array[i - 2];
}
result = array[i];
}
return result;
}
使用遞歸的核心代碼：
public int run2(int n) {
int result = 1;
if (n > 2) {
result = run2(n - 1) + run2(n - 2);
}
return result;
}
通過(guò)求解斐波那契數(shù)列這個(gè)例子，以及使用的三種思路來(lái)看韧拒，遞歸的好處一目了然淹接，代碼量明顯比其它兩種思路少很多，而且思路更簡(jiǎn)單叛溢。
遞歸的核心思路其實(shí)就是一直循環(huán)直到最底層然后一層一層找回來(lái)塑悼，所以思考遞歸的第一步就是想最底層的情況，然后再考慮后面的遞增情況楷掉。
