【剑指offer】斐波那契数列

题意：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

题解：这里用的递推以及黄金分割公式。。我不会用java写矩阵快速幂。可以参见我前面的矩阵快速幂题解。

代码：

 1 public class Solution {
 2     public int Fibonacci(int n) {
 3         if(n == 0){
 4             return 0;
 5         }
 6         else if(n == 1){
 7             return 1;
 8         }
 9         else{
10             int f0 = 0;
11             int f1 = 1;
12             int fn = f1+f0;
13             for(int i = 2 ; i <=n ;i++){
14                 fn = f1+f0;
15                 f0 = f1;
16                 f1 = fn;
17             }
18             return fn;
19         }
20     }
21 }
22 
23 
24 
25 OR
26 
27 
28 
29 public class Solution {
30     public int Fibonacci(int n) {
31         if(n == 0){
32             return 0;
33         }
34         else if(n == 1){
35             return 1;
36         }
37         else{
38             double k = Math.sqrt(5.0);
39             double a = (1 + k) / 2;
40             double b = (1 - k) / 2;
41 
42             int ans = (int)(1.0 / k * (Math.pow(a, n)- Math.pow(b, n)));
43             return ans;
44         }
45     }
46 }

跳台阶，变态跳台阶，矩形覆盖同此题