Fibonacci数列的一点思考哈哈

Fibonacci数列对于我们计算机的学生来说，太熟悉不过，但是今天在看书的时候还是发现了点新的东西。

一般的找出Fibonacci数的方法如下：

public static long fib(long index){
	if (index == 0) {
		return 0;
	}else if(index == 1){
		return 1;
	}else{
		return fib(index - 1)+fib(index -2);
	}
}

其复杂度显然为：O(2的n次方)，递归问题，与汉诺塔问题的复杂度一致。

下面给出一种较好的方法，其算法复杂度为O(n)：

package MyAlgorithom;

import java.util.Scanner;

public class ImprovedFibonacci {
	public static void main(String[] args) {
		/*创建一个用户输入*/
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入一个Fibonacci数列的index：");
		int index = scanner.nextInt();

		System.out.println("Fibonacci number at index"+index+" is "+fib(index));
	}

	public static long fib(long n){
		long f0 = 0;
		long f1 = 1;
		long f2 = 1;

		if (n == 0) {
			return f0;
		} else if(n == 1){
			return f1;
		} else if(n == 2){
			return f2;
		}

		for (int i = 3; i <= n; i++) {
			f0 = f1;
			f1 = f2;
			f2 = f1+f0;
		}
		return f2;
	}
}

程序结果：
输入一个Fibonacci数列的index：
[color=cyan]100[/color]
Fibonacci number at index100 is 3736710778780434371

“灵活”计算机程序的精髓，这种“移位”思想比递归好多了吧哈哈。