求第n个斐波那契数

        今天看到群友发的一个问题：写一个小程序打印第n个斐波那契数。
        自己试了下，搞了好久。。。基础要加强了。
       
        进入正题，什么是斐波那契数列就不说了，拿到这个题目，直接写出如下代码：

public static long findFibonacci(int n){
		if(n <= 2){
			return 1;
		}else{
			return findFibonacci(n - 1) + findFibonacci(n - 2);
		}
	}

        运行一下，输入n分别为：1,2,3,4,5 输出分别为1,1,2,3,5。貌似是正确的，看看有什么问题，如果我们输入n为45。

public static void main(String[] args) {
		long s = System.currentTimeMillis();
		System.out.println(findFibonacci(45));
		long e = System.currentTimeMillis();
		System.out.println("程序运行耗时["+(e-s)+"]毫秒!");
	}

        输出如下：

1134903170
程序运行耗时[4875]毫秒!

        如果输入100的话，就一直在运行。。。。。
        上面程序的问题在于，计算第n个f数时需要计算第n-1和第n-2个f数，但是计算第n+1个f数的时候又要重新计算第n个f数，如此反复，要处理的子问题的数量爆炸式增长。我们加点输出看看。

public static long findFibonacci(int n){
		if(n <= 2){
			System.out.println("计算第["+n+"]个斐波那契数[1]");
			return 1;
		}else{
			long fb = findFibonacci(n - 1) + findFibonacci(n - 2);
			System.out.println("计算第["+n+"]个斐波那契数["+fb+"]");
			return fb;
		}
	}

        n输入为5，输出如下：

计算第[2]个斐波那契数[1]
计算第[1]个斐波那契数[1]
计算第[3]个斐波那契数[2]
计算第[2]个斐波那契数[1]
计算第[4]个斐波那契数[3]
计算第[2]个斐波那契数[1]
计算第[1]个斐波那契数[1]
计算第[3]个斐波那契数[2]
计算第[5]个斐波那契数[5]
5
程序运行耗时[0]毫秒!

        如何解决这个问题呢，如果我们能重复利用子问题的结果，而不是每次去重新求解子问题，这样程序就会快很多，这种处理问题的方式也叫做动态规划。
        针对这个问题，假设我们要求第n个斐波那契数，我们可以建立一个长度为n(为n-1就可以，但为了编码方便)的数组用来保存子问题结果，代码如下：

private static long findFibonacci1(int n, long[] c){
		int index = n - 1;
		if(c[index] != 0){
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci1(n - 1,c) + findFibonacci1(n - 2,c);
		}
		return c[index];
	}
	
	public static long findFibonacci1(int n){
		long c[] = new long[n];
		return findFibonacci1(n,c);
	}

        这次输入45，看看结果：

1134903170
程序运行耗时[0]毫秒!

        这次没问题了。再想想，其实每次求第n个f数只需要重用第n-1和第n-2个f数就可以了，而且依据代码，问题的解决是自底向上的，所以每次保存2个就够了，我们先搞点日志看看。

private static long findFibonacci1(int n, long[] c){
		int index = n - 1;
		if(c[index] != 0){
			System.out.println("从数组下标["+index+"]中获取数据["+c[index]+"]");
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci1(n - 1,c) + findFibonacci1(n - 2,c);
		}
		return c[index];
	}

        输入7，看输出：

从数组下标[1]中获取数据[1]
从数组下标[2]中获取数据[2]
从数组下标[3]中获取数据[3]
从数组下标[4]中获取数据[5]
13
程序运行耗时[0]毫秒!

        可以看到，会从小到大从数组中取数据。继续看看能不能每次只保存2个子问题结果。看代码：

private static long findFibonacci2(int n, long[] c){
		int index = n % 2;
		if(c[index] != 0){
			System.out.println("从数组下标["+index+"]中获取数据["+c[index]+"]");
			return c[index];
		}
		if(n <= 2){
			c[index] = 1;
		}else{
			c[index] = findFibonacci2(n - 1,c) + findFibonacci2(n - 2,c);
		}
		return c[index];
	}
	
	public static long findFibonacci2(int n){
		long c[] = new long[2];
		return findFibonacci2(n,c);
	}

        输出8，看看输出：

从数组下标[0]中获取数据[1]
从数组下标[1]中获取数据[2]
从数组下标[0]中获取数据[3]
从数组下标[1]中获取数据[5]
从数组下标[0]中获取数据[8]
21
程序运行耗时[0]毫秒!

        嗯，果然可以。去掉打印语句，输出1000，看看输出：

817770325994397771
程序运行耗时[0]毫秒!

        ok，嘎嘎。不过这道题直接用循环貌似更简单。。。。
        再来个更短的(无聊)

private static long f(int n, long[] a){
		return a[n & 1] == 0 ? (n <= 2 ? (a[n & 1] = 1)
				:(a[n & 1] = f(n - 1, a) + f(n - 2, a))) : a[n & 1];
	}
	
	public static long findNthFibonacci(int n){
		return f(n, new long[2]);
	}