Board logo

標題: 費氏數列的兩種解法 [打印本頁]

作者: tonyh    時間: 2023-5-13 19:03     標題: 費氏數列的兩種解法

1. 遞迴
2. 動態規劃





Java
  1. // 0 1 1 2 3 5 8 ...
  2. public class Ch01 {

  3.         Ch01()
  4.         {
  5.                 System.out.println("費氏數列第12項: "+f(12));
  6.                 System.out.println("費氏數列第23項: "+f(23));
  7.                 System.out.println("費氏數列第37項: "+f(37));
  8.                 System.out.println("費氏數列第42項: "+f(42));
  9.         }

  10.         int f(int n)
  11.         {
  12.                 if(n<2)
  13.                         return n;
  14.                 else
  15.                         return f(n-2)+f(n-1);
  16.         }

  17.         public static void main(String[] args) {
  18.                 long start=System.currentTimeMillis();
  19.                 new Ch01();
  20.                 long end=System.currentTimeMillis();
  21.                 System.out.println("花費: "+(end-start)+" 毫秒");
  22.         }

  23. }
  24. /*
  25.     f(5)
  26.     =f(3)+f(4)
  27.     =f(1)+f(2)+f(2)+f(3)
  28.     =1+f(0)+f(1)+f(0)+f(1)+f(1)+f(2)
  29.     =1+0+1+0+1+1+f(0)+f(1)
  30.     =1+1+1+1+1=5
  31. */
複製代碼
  1. // 0 1 1 2 3 5 8 ...
  2. public class Ch02 {

  3.         Ch02()
  4.         {
  5.                 long data[]=new long[90];
  6.                 data[0]=0;
  7.                 data[1]=1;
  8.                 for(int i=2; i<90; i++)
  9.                         data[i]=data[i-2]+data[i-1];
  10.                 System.out.println("費氏數列第12項: "+data[12]);
  11.                 System.out.println("費氏數列第23項: "+data[23]);
  12.                 System.out.println("費氏數列第37項: "+data[37]);
  13.                 System.out.println("費氏數列第42項: "+data[42]);
  14.                 System.out.println("費氏數列第59項: "+data[59]);
  15.                 System.out.println("費氏數列第89項: "+data[89]);
  16.         }

  17.         public static void main(String[] args) {

  18.                 long start=System.currentTimeMillis();
  19.                 new Ch02();
  20.                 long end=System.currentTimeMillis();
  21.                 System.out.println("花費: "+(end-start)+" 毫秒");
  22.         }

  23. }
複製代碼
C++
  1. #include<bits/stdc++.h>
  2. using namespace std;

  3. int f(int n)
  4. {
  5.     if(n<2)
  6.         return n;
  7.     else
  8.         return f(n-2)+f(n-1);
  9. }

  10. int main()
  11. {
  12.     cout<<"費氏數列第12項: "<<f(12)<<endl;
  13.     cout<<"費氏數列第23項: "<<f(23)<<endl;
  14.     cout<<"費氏數列第37項: "<<f(37)<<endl;
  15.     cout<<"費氏數列第42項: "<<f(42)<<endl;
  16.     cout<<"花費: "<<clock()<<" 毫秒"<<endl;
  17.     return 0;
  18. }
複製代碼
  1. #include<bits/stdc++.h>
  2. using namespace std;

  3. int main()
  4. {
  5.     long long data[90];
  6.     data[0]=0;
  7.     data[1]=1;
  8.     for(int i=2; i<90; i++)
  9.         data[i]=data[i-2]+data[i-1];
  10.     cout<<"費氏數列第12項: "<<data[12]<<endl;
  11.     cout<<"費氏數列第23項: "<<data[23]<<endl;
  12.     cout<<"費氏數列第37項: "<<data[37]<<endl;
  13.     cout<<"費氏數列第42項: "<<data[42]<<endl;
  14.     cout<<"費氏數列第59項: "<<data[59]<<endl;
  15.     cout<<"費氏數列第89項: "<<data[89]<<endl;
  16.     cout<<"花費: "<<clock()<<" 毫秒"<<endl;
  17.     return 0;
  18. }
複製代碼

作者: 王法棣    時間: 2023-5-13 19:49

本帖最後由 王法棣 於 2023-5-13 19:54 編輯
  1. package ch1;

  2. public class ch1 {

  3.        
  4.         ch1()
  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. int f(int n)
  12. {
  13.          if(n<2)
  14.             return n;
  15.          else
  16.              return f(n-2)+f(n-1);
  17. }

  18. public static void main(String[] args) {
  19.          long s=System.currentTimeMillis();
  20.          new ch1();
  21.          long e=System.currentTimeMillis();
  22.          System.out.println(e-s);
  23. }

  24.         }
複製代碼
  1. package ch1;

  2. public class ch1 {

  3.        
  4.         ch1()
  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-1]+data[i-2];
  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.         public static void main(String[] args) {
  19.                 long s=System.currentTimeMillis();
  20.                 new ch1();
  21.                 long e=System.currentTimeMillis();
  22.                 System.out.println(e-s);
  23.         }

  24. }
複製代碼

作者: 王秉鈞    時間: 2023-5-13 19:53

  1. public class Ch69 {

  2.            Ch69()
  3.            {
  4.                    System.out.println("費事數列地12巷"+f(12));
  5.                    System.out.println("費事數列地12巷"+f(23));
  6.                    System.out.println("費事數列地12巷"+f(37));
  7.                    System.out.println("費事數列地12巷"+f(42));
  8.            }
  9. }
  10. int f(int n)
  11. {
  12.         if(n<2)
  13.                 return n;
  14.         else
  15.                 return f(n-2)+f(n-1);
  16. }
  17. public static void main(String[] args){
  18.         long start=System.currentTimeMills();
  19.         System.out.println("花費"+(end-start)+"毫秒");
  20.     }
  21. }
複製代碼

作者: 曾元瑜    時間: 2023-5-13 19:53

  1. public class D1 {
  2.         D1(){
  3.                 System.out.println("費氏數列第12項:"+f(12));
  4.                 System.out.println("費氏數列第23項:"+f(23));
  5.                 System.out.println("費氏數列第37項:"+f(37));
  6.                 System.out.println("費氏數列第42項:"+f(42));
  7.         }
  8.         int f(int n)
  9.         {
  10.                 if(n<2)
  11.                         return n;
  12.                 else
  13.                         return f(n-2)+f(n-1);
  14.         }
  15.         public static void main(String[] args) {
  16.                 long s=System.currentTimeMillis();
  17.                 new D1();
  18.                 long e=System.currentTimeMillis();
  19.                 System.out.println("花費:"+(e-s)+"毫秒");
  20.         }
  21. }
複製代碼

作者: 盧禹廷    時間: 2023-5-13 19:54

  1. public class Ch01 {

  2.         Ch01()
  3.         {
  4.                 long data[]=new long[90];
  5.                 data[0]=0;
  6.                 data[1]=1;
  7.                 for(int i=2; i<90; i++)
  8.                         data[i]=data[i-2]+data[i-1];
  9.                 System.out.println("費氏數列第12項: "+data[12]);
  10.                 System.out.println("費氏數列第23項: "+data[23]);
  11.                 System.out.println("費氏數列第37項: "+data[37]);
  12.                 System.out.println("費氏數列第42項: "+data[42]);
  13.                 System.out.println("費氏數列第59項: "+data[59]);
  14.                 System.out.println("費氏數列第89項: "+data[89]);
  15.         }

  16.         public static void main(String[] args) {

  17.                 long start=System.currentTimeMillis();
  18.                 new Ch01();
  19.                 long end=System.currentTimeMillis();
  20.                 System.out.println("花費: "+(end-start)+" 毫秒");
  21.         }

  22. }
複製代碼

作者: 陳依彤    時間: 2023-5-13 20:08

  1. #include<bits/stdc++.h>
  2. using namespace std;

  3. int main()
  4. {
  5.     long long data[90];
  6.     data[0]=0;
  7.     data[1]=1;
  8.     for(int i=2; i<90; i++)
  9.         data[i]=data[i-2]+data[i-1];
  10.     cout<<"費氏數列第12項: "<<data[12]<<endl;
  11.     cout<<"費氏數列第23項: "<<data[23]<<endl;
  12.     cout<<"費氏數列第37項: "<<data[37]<<endl;
  13.     cout<<"費氏數列第42項: "<<data[42]<<endl;
  14.     cout<<"費氏數列第59項: "<<data[59]<<endl;
  15.     cout<<"費氏數列第89項: "<<data[89]<<endl;
  16.     cout<<"花費: "<<clock()<<" 毫秒"<<endl;
  17.     return 0;
  18. }
複製代碼

作者: 張博竣    時間: 2023-5-13 20:17

  1. public class Ch69 {

  2.            Ch69()
  3.            {
  4.                    System.out.println("費事數列地12巷"+f(12));
  5.                    System.out.println("費事數列地12巷"+f(23));
  6.                    System.out.println("費事數列地12巷"+f(37));
  7.                    System.out.println("費事數列地12巷"+f(42));
  8.            }
  9. }
  10. int f(int n)
  11. {
  12.         if(n<2)
  13.                 return n;
  14.         else
  15.                 return f(n-2)+f(n-1);
  16. }
  17. public static void main(String[] args){
  18.         long start=System.currentTimeMills();
  19.         System.out.println("花費"+(end-start)+"毫秒");
  20.     }
  21. }
複製代碼

作者: 黃子倢    時間: 2023-5-20 19:13

  1. public class Ch01 {

  2.         Ch01()
  3.         {
  4.                 System.out.println("費氏數列第12項: "+f(12));
  5.                 System.out.println("費氏數列第23項: "+f(23));
  6.                 System.out.println("費氏數列第37項: "+f(37));
  7.                 System.out.println("費氏數列第42項: "+f(42));
  8.         }

  9.         int f(int n)
  10.         {
  11.                 if(n<2)
  12.                         return n;
  13.                 else
  14.                         return f(n-2)+f(n-1);
  15.         }

  16.         public static void main(String[] args) {
  17.                 long start=System.currentTimeMillis();
  18.                 new Ch01();
  19.                 long end=System.currentTimeMillis();
  20.                 System.out.println("花費: "+(end-start)+" 毫秒");
  21.         }

  22. }
複製代碼

作者: 王秉鈞    時間: 2023-5-20 19:40

  1. public class Ch71 {
  2.     Ch71()
  3.     {
  4.             long data[]=new long[90];
  5.             data[0]=0;
  6.             data[1]=1;
  7.             for(int i=2;i<90;i++);
  8.             System.out.println("地12巷"+data[12]);
  9.             System.out.println("地23巷"+data[23]);
  10.             System.out.println("地37巷"+data[37]);
  11.             System.out.println("第42巷"+data[42]);
  12.             System.out.println("地59巷"+data[59]);
  13.             System.out.println("地89巷"+data[89]);
  14.            
  15.     }
  16.     public static void main(String[] args){
  17.             long start=System.currentTimeMillis();
  18.     new Ch71();
  19.     long end=System.currentTimeMillis();
  20.     System.out.println("spend"+(end-start)+"0.001sec");
  21.     }
  22. }
複製代碼





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2