費氏數列的兩種解法

tonyh

1. 遞迴
2. 動態規劃





Java

1. // 0 1 1 2 3 5 8 ...
   
2. public class Ch01 {
   
3. 
   
4.         Ch01()
   
5.         {
   
6.                 System.out.println("費氏數列第12項: "+f(12));
   
7.                 System.out.println("費氏數列第23項: "+f(23));
   
8.                 System.out.println("費氏數列第37項: "+f(37));
   
9.                 System.out.println("費氏數列第42項: "+f(42));
   
10.         }
    
11. 
    
12.         int f(int n)
    
13.         {
    
14.                 if(n<2)
    
15.                         return n;
    
16.                 else
    
17.                         return f(n-2)+f(n-1);
    
18.         }
    
19. 
    
20.         public static void main(String[] args) {
    
21.                 long start=System.currentTimeMillis();
    
22.                 new Ch01();
    
23.                 long end=System.currentTimeMillis();
    
24.                 System.out.println("花費: "+(end-start)+" 毫秒");
    
25.         }
    
26. 
    
27. }
    
28. /*
    
29.     f(5)
    
30.     =f(3)+f(4)
    
31.     =f(1)+f(2)+f(2)+f(3)
    
32.     =1+f(0)+f(1)+f(0)+f(1)+f(1)+f(2)
    
33.     =1+0+1+0+1+1+f(0)+f(1)
    
34.     =1+1+1+1+1=5
    
35. */

複製代碼

1. // 0 1 1 2 3 5 8 ...
   
2. public class Ch02 {
   
3. 
   
4.         Ch02()
   
5.         {
   
6.                 long data[]=new long[90];
   
7.                 data[0]=0;
   
8.                 data[1]=1;
   
9.                 for(int i=2; i<90; i++)
   
10.                         data[i]=data[i-2]+data[i-1];
    
11.                 System.out.println("費氏數列第12項: "+data[12]);
    
12.                 System.out.println("費氏數列第23項: "+data[23]);
    
13.                 System.out.println("費氏數列第37項: "+data[37]);
    
14.                 System.out.println("費氏數列第42項: "+data[42]);
    
15.                 System.out.println("費氏數列第59項: "+data[59]);
    
16.                 System.out.println("費氏數列第89項: "+data[89]);
    
17.         }
    
18. 
    
19.         public static void main(String[] args) {
    
20. 
    
21.                 long start=System.currentTimeMillis();
    
22.                 new Ch02();
    
23.                 long end=System.currentTimeMillis();
    
24.                 System.out.println("花費: "+(end-start)+" 毫秒");
    
25.         }
    
26. 
    
27. }

複製代碼

C++

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int f(int n)
   
5. {
   
6.     if(n<2)
   
7.         return n;
   
8.     else
   
9.         return f(n-2)+f(n-1);
   
10. }
    
11. 
    
12. int main()
    
13. {
    
14.     cout<<"費氏數列第12項: "<<f(12)<<endl;
    
15.     cout<<"費氏數列第23項: "<<f(23)<<endl;
    
16.     cout<<"費氏數列第37項: "<<f(37)<<endl;
    
17.     cout<<"費氏數列第42項: "<<f(42)<<endl;
    
18.     cout<<"花費: "<<clock()<<" 毫秒"<<endl;
    
19.     return 0;
    
20. }

複製代碼

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     long long data[90];
   
7.     data[0]=0;
   
8.     data[1]=1;
   
9.     for(int i=2; i<90; i++)
   
10.         data[i]=data[i-2]+data[i-1];
    
11.     cout<<"費氏數列第12項: "<<data[12]<<endl;
    
12.     cout<<"費氏數列第23項: "<<data[23]<<endl;
    
13.     cout<<"費氏數列第37項: "<<data[37]<<endl;
    
14.     cout<<"費氏數列第42項: "<<data[42]<<endl;
    
15.     cout<<"費氏數列第59項: "<<data[59]<<endl;
    
16.     cout<<"費氏數列第89項: "<<data[89]<<endl;
    
17.     cout<<"花費: "<<clock()<<" 毫秒"<<endl;
    
18.     return 0;
    
19. }

複製代碼