斐波那契数列简介
斐波那契数列(Fibonacci sequence),又称黄金分割数列、指的是这样一个数列:1、1、2、3、5、8、13、21、34、……即从第3项起,后一项总是等于前两项之和。
在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)。
1. 使用数组实现Fibonacci数列
/**
* 使用数组实现Fibonacci数列
*/
public void fibonacciArray(int n) {
int[] fibonacci = new int[n];
fibonacci[0] = 1;
fibonacci[1] = 1;
for (int i = 2; i < n; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
System.out.println(Arrays.toString(fibonacci));
}
2. 使用栈实现Fibonacci数列
/**
* 使用栈实现Fibonacci数列
*/
public void fibonacciStack(int n) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(1);
while (stack.size() < n) {
Integer numTop1 = stack.pop();
Integer numTop2 = stack.peek();
stack.push(numTop1);
stack.push(numTop1 + numTop2);
}
System.out.println(stack);
}
3. 使用递归求Fibonacci第n项的值
/**
* 使用递归求Fibonacci第n项的值
*/
public int fibonacciRecursion(int n) {
if (n == 1) return 1;
if (n == 2) return 1;
return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
}
网友评论