什么是斐波那契数?
Wikipedia 的定义比较详细,大家可以参考一下。
斐波那契数是一系列连续顺序排列的整型数。主要特征就是当前数是前两位数之和。
例如:
1 1 2 3 5 8 13 21 34 55 89 144 。。。
或则以0为初始值:
0 1 1 2 3 5 8 13 21 34 55 89 144 。。。
思路:
- 利用集合的特性,将数列依次存在集合中再输出
- 循环动态计算,边计算边输出(最佳)
- 利用递归调用
实现:
用ArrayList存储Fibonacci数列
public static void printFibonacciUsingCollection(int len) {
ArrayList<Integer> fi = new ArrayList<>();
fi.add(0);
fi.add(1);
for (int i = 2; i <= len - 1; i++) {
fi.add(fi.get(i - 2) + fi.get(i - 1));
}
if (len < 1) {
System.out.println("the length is invalid");
} else if (len == 1) {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println("[" + fi.get(0) + "]");
} else if (len == 2) {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]");
} else {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println(fi);
}
}
动态计算:
当前fn = fn-2 + fn-1
下一轮fn-2,fn-1的值将这样变换:
fn-2 = fn-1
fn-1 = fn
public static void printFibonacciWithoutCollection(int len) {
int f0 = 0;
int f1 = 1;
int fi;
if (len <= 0) {
System.out.println("the length is invalid");
} else {
System.out.println("the fibonacci series of length " + len + " are here");
if (len == 1) {
System.out.println(f0);
} else if (len == 2) {
System.out.println(f0 + " " + f1);
} else {
System.out.print(f0 + " " + f1 + " ");
for (int i = 3; i <= len; i++) {
fi = f0 + f1;
System.out.print(fi + " ");
f0 = f1;
f1 = fi;
}
System.out.println();
}
}
}
递归调用:
f(n) = f(n-1) + f(n-2)
例如:计算f(4)
f0 = 0
f1 = 1
f(4) = f(2) + f(3) 转换成先计算f(2)和f(3)
f(2) = f(0) + f(1) = 1
f(3) = f(2) + f(1) = 2
再将计算出的结果返回
f(4) = f(2) + f(3) = 1 + 2 = 3
每次分解递归调用再回归
public static int findFibonacciUsingRecursion(int len) {
int f0 = 0;
int f1 = 1;
int fn;
if (len == 1) {
return f0;
} else if (len == 2) {
return f1;
} else {
fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1);
return fn;
}
}
完整代码
递归:
import java.util.*;
public class Test {
public static void main(String[] args) {
testPrintFibonacciUsingRecursion();
}
public static void testPrintFibonacciUsingRecursion() {
System.out.println("Please enter a length greater than 0, -1 means to quit");
Scanner in = new Scanner(System.in);
int len = in.nextInt();
while (len != -1) {
if (len <= 0) {
System.out.println("the length is invalid");
} else {
System.out.println("the fibonacci series of length " + len + " are here:");
for (int i = 1; i <= len; i++) {
System.out.print(findFibonacciUsingRecursion(i) + " ");
}
System.out.println();
}
System.out.println("Please enter a length greater than 0 again, -1 means to quit");
len = in.nextInt();
}
}
public static int findFibonacciUsingRecursion(int len) {
int f0 = 0;
int f1 = 1;
int fn;
if (len == 1) {
return f0;
} else if (len == 2) {
return f1;
} else {
fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1);
return fn;
}
}
}
非递归:
import java.util.*;
public class Test {
public static void main(String[] args) {
testPrintFibonacci();
}
public static void testPrintFibonacci() {
System.out.println("Please enter a length greater than 0, -1 means to quit");
Scanner in = new Scanner(System.in);
int len = in.nextInt();
while (len != -1) {
printFibonacciWithoutCollection(len);
// printFibonacciWithoutCollection(len);
len = in.nextInt();
}
}
public static void printFibonacciUsingCollection(int len) {
ArrayList<Integer> fi = new ArrayList<>();
fi.add(0);
fi.add(1);
for (int i = 2; i <= len - 1; i++) {
fi.add(fi.get(i - 2) + fi.get(i - 1));
}
if (len < 1) {
System.out.println("the length is invalid");
} else if (len == 1) {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println("[" + fi.get(0) + "]");
} else if (len == 2) {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]");
} else {
System.out.println("Fibonacci series of length " + len + " are here:");
System.out.println(fi);
}
}
public static void printFibonacciWithoutCollection(int len) {
int f0 = 0;
int f1 = 1;
int fi;
if (len <= 0) {
System.out.println("the length is invalid");
} else {
System.out.println("the fibonacci series of length " + len + " are here");
if (len == 1) {
System.out.println(f0);
} else if (len == 2) {
System.out.println(f0 + " " + f1);
} else {
System.out.print(f0 + " " + f1 + " ");
for (int i = 3; i <= len; i++) {
fi = f0 + f1;
System.out.print(fi + " ");
f0 = f1;
f1 = fi;
}
System.out.println();
}
}
}
}
输出结果:
Please enter a length greater than 0, -1 means to quit
0
the length is invalid
1
the fibonacci series of length 1 are here
0
2
the fibonacci series of length 2 are here
0 1
3
the fibonacci series of length 3 are here
0 1 1
8
the fibonacci series of length 8 are here
0 1 1 2 3 5 8 13
-1
Process finished with exit code 0