Board logo

標題: 費氏數列的兩種解法 [打印本頁]
作者: tonyh    時間: 2023-1-6 19:30     標題: 費氏數列的兩種解法

本帖最後由 tonyh 於 2023-5-6 20:16 編輯

1. 遞迴
2. 動態規劃





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

  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.         }

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

  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.         }

  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 {

  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.         }

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

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

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

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

  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;

  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. }
複製代碼
作者: 李穎俊    時間: 2023-1-6 20:38

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

  4. public class P1 {
  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  6.         P1() throws Exception
  7.         {
  8.                  System.out.println("費氏數列第12項: "+f(12));
  9.          System.out.println("費氏數列第23項: "+f(23));
  10.          System.out.println("費氏數列第37項: "+f(37));
  11.          System.out.println("費氏數列第42項: "+f(42));
  12.         }
  13.         int f(int n)
  14.     {
  15.             if(n<2)
  16.                     return n;
  17.             else
  18.                     return f(n-2)+f(n-1);
  19.     }
  20.         public static void main(String[] args) throws Exception {
  21.                  long start=System.currentTimeMillis();
  22.          new P1();
  23.          long end=System.currentTimeMillis();
  24.          System.out.println("花費: "+(end-start)+" 毫秒");
  25.         }
  26. }
複製代碼
作者: 劉愷鈞    時間: 2023-1-6 20:43

  1. 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 x)
  11.         {
  12.                 if(x<2)
  13.                         return x;
  14.                 else
  15.                         return f(x-1)+f(x-2);
  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. }
複製代碼
  1. public class Ch01 {

  3.         Ch01()
  4.         {
  5.                 long data[]=new long[90];
  6.                 data[0]=0;
  7.                 data[1]=1;
  8.                 for(int i=2;i<90;i++)
  9.                 {
  10.                         data[i]=data[i-1]+data[i-2];
  11.                 }
  12.                 System.out.println("費氏數列第12項: "+data[12]);
  13.         System.out.println("費氏數列第23項: "+data[23]);
  14.         System.out.println("費氏數列第37項: "+data[37]);
  15.         System.out.println("費氏數列第42項: "+data[42]);
  16.         System.out.println("費氏數列第59項: "+data[59]);
  17.         System.out.println("費氏數列第89項: "+data[89]);
  18.         }
  19.         public static void main(String[] args) {
  20.                 long start=System.currentTimeMillis();
  21.                 new Ch01();
  22.                 long end=System.currentTimeMillis();
  23.                 System.out.println("花費: "+(end-start)+" 毫秒");
  24.         }
  25. }
複製代碼
作者: 陳宥穎    時間: 2023-1-6 20:44

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;


  6. public class Ch02 {
  7.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  8.         Ch02() throws Exception, Exception
  9.         {
  10.                 long x[]=new long[90],input;
  11.                 input=Integer.parseInt(br.readLine());
  12.                 x[0]=0;
  13.                 x[1]=1;
  14.                 for(int i=2; i<x.length; i++)
  15.                         x[i]=x[i-1]+x[i-2];               
  16.                 System.out.println(x[(int) input]);
  17.         }
  18.         public static void main(String[] args) throws Exception {
  19.                 long start=System.currentTimeMillis();
  20.                 new Ch02();
  21.                 System.out.println(System.currentTimeMillis()-start+"ms");
  22.         }
  23. }
複製代碼
作者: 陳宥穎    時間: 2023-1-6 20:47

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;


  6. public class Ch02 {
  7.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  8.         Ch02() throws Exception, Exception
  9.         {
  10.                 int input;
  11.                 input=Integer.parseInt(br.readLine());
  12.                 System.out.println(f(input));
  13.         }
  14.         int f(int n)
  15.         {
  16.                 if(n<2)
  17.                         return n;
  18.                 else
  19.                         return f(n-2)+f(n-1);
  20.         }
  21.         public static void main(String[] args) throws Exception {
  22.                 long start=System.currentTimeMillis();
  23.                 new Ch02();
  24.                 long end=System.currentTimeMillis();
  25.                 System.out.println((end-start)+"ms");
  26.         }
  27. }
複製代碼
作者: 董宸佑    時間: 2023-1-6 20:48

  1. package test;

  3. public class test {
  4.        
  5.         test(){
  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.         }

  19.         public static void main(String[] args) {
  20.                 long star=System.currentTimeMillis();
  21.                 new test();
  22.                 long end=System.currentTimeMillis();
  23.                 System.out.println("花費 "+(end-star)+" 毫秒");
  24.         }
  25. }
複製代碼
作者: 林祐霆    時間: 2023-1-6 20:56

  1. public class Rickroll {
  2.         Rickroll(){
  3.                 System.out.println("費氏數列第12項: "+func(12));
  4.         System.out.println("費氏數列第23項: "+func(23));
  5.         System.out.println("費氏數列第37項: "+func(37));
  6.         System.out.println("費氏數列第42項: "+func(42));
  7.         }
  8.         public static void main(String[] args) {
  9.                 long s=System.currentTimeMillis();
  10.                 new Rickroll();
  11.                 long e=System.currentTimeMillis();
  12.                 System.out.println("使用遞迴的秒數: "+(e-s)+" 毫秒");
  13.         }
  14.         int func(int n){
  15.                 if(n<2)
  16.                         return n;
  17.                 else
  18.                         return func(n-2)+func(n-1);
  19.         }
  20. }
複製代碼
  1. public class Hi {
  2.         Hi(){
  3.                 long data[]=new long[90];
  4.                 data[0]=0;
  5.                 data[1]=1;
  6.                 for(int i=2;i<90;i++){
  7.                         data[i]=data[i-2]+data[i-1];
  8.                 }
  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 s=System.currentTimeMillis();
  18.                 new Hi();
  19.                 long e=System.currentTimeMillis();
  20.                 System.out.println("使用動態規劃的秒數: "+(e-s)+" 毫秒");
  21.         }
  22. }
複製代碼
作者: 蘇韋誠    時間: 2023-1-6 20:57

  1. public class ha {

  3.         ha() throws Exception
  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.                 {
  14.                         return n;
  15.                 }
  16.                 else
  17.                 {
  18.                         return f(n-2)+f(n-1);
  19.                 }
  20.         }
  21.         public static void main(String[] args) throws Exception {               
  22.                 long start=System.currentTimeMillis();
  23.                 new ha();
  24.                 long end=System.currentTimeMillis();
  25.                 System.out.println("花費: "+(end-start)+" 毫秒");
  26.         }
  27. }
複製代碼
  1. public class ha {

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

  20.         public static void main(String[] args) throws Exception {               
  21.                 long start=System.currentTimeMillis();
  22.                 new ha();
  23.                 long end=System.currentTimeMillis();
  24.                 System.out.println("花費: "+(end-start)+" 毫秒");
  25.         }
  26. }
複製代碼
作者: 洪承廷    時間: 2023-1-6 21:10

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

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

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

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

  26. }
複製代碼




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