斐波那契数列（精讲）

典型例题：斐波那契数列

斐波那契数列使我们比较常见的一个练习算法的题，而且有很多的解法。

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、…^

方法一：

package Test;

public class demo6 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
				int num0= 0;
		        int num1= 1;
		        int num2= 1;
		        int num3;
		        int i=3;
		        //输出数列的前两个数
		        System.out.println(num0);
		        System.out.println(num1);
		        System.out.println(num2);
		        //输出数列的第三个数到第十个数
		        while(i<=10){
		            num3 = num1 + num2; //求出第i个数
		            System.out.println(num3);//输出第i个数
		            num1=num2; 
		            num2=num3;
		            i++;
		        }
		    }
		}

斐波那契数列，直观上看就是下一个数是他前两个数的和，所以呈现出0,1,1,2,3,5,8,13……

所以，我们可以直接设置出他的前三个或者是两个数，并且直接设置的数输出出来，后面的数进行一个循环，因为我们已经设置出了前面两个或者三个数了，所以在这里我们要把i跳过我们设置的数。在这里是从3开始的，下一个数是有num1和num2的和算出来的，但是在下一个数是由num2和num3的和构成的，所以在这里我们要把num2的值赋值给num1，把num3的值赋值给num2，并且让i自动增加一个。再重新进行循环，直到到达了循环的终止条件停止。

方法二：

package demo;

public class demo1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(f(10));
		
	}
	public static int f(int n){
		if(n==1||n==2){
			return 1;
			
		}
		return f(n-1)+f(n-2);
	}

}

数学上运用递归算法的思维是：f0=0;f1=1;f2=1;fn=f(n-1)+f(n-2)(n>=2且n属于正整数)

从中我们能有明白，n的临界值就是1或2所以当n=1或n=2的时候递归结束。

同样运用相同的逻辑，把问题分成一个一个的小的问题就如同fn=f(n-1)+f(n-2)一样，不断的缩小问题的范围。最终取得结果。