学步园

为了应付软考，补补基础知识，特记录下以备后用。

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

以下是Java代码实现(递归与递推两种方式)：

import java.util.Scanner;

/**
 * Fibonacci
 *
 * @author tongqian.zhang
 */
public class Fibonacci {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("Please input this fibonacci n:");
		int n = scanner.nextInt(); // 假设输入为大于零的整数
		
		System.out.println(fibonacci(6) + ":" + fibonacciNormal(6));
		
		int sum = 0;
		for(int i = 1; i <= n; i++){
			sum += fibonacci(i);
		}
		System.out.println(sum);
	}
	
	// 递归实现方式
	public static int fibonacci(int n){
		if(n <= 2){
			return 1;
		}else{
			return fibonacci(n-1) + fibonacci(n-2);
		}
	}
	
	// 递推实现方式
	public static int fibonacciNormal(int n){
		if(n <= 2){
			return 1;
		}
		int n1 = 1, n2 = 1, sn = 0;
		for(int i = 0; i < n - 2; i ++){
			sn = n1 + n2;
			n1 = n2;
			n2 = sn;
		}
		return sn;
	}
}