1. 遞迴
2. 動態規劃
Java- // 0 1 1 2 3 5 8 ...
- public class Ch01 {
- Ch01()
- {
- System.out.println("費氏數列第12項: "+f(12));
- System.out.println("費氏數列第23項: "+f(23));
- System.out.println("費氏數列第37項: "+f(37));
- System.out.println("費氏數列第42項: "+f(42));
- }
- int f(int n)
- {
- if(n<2)
- return n;
- else
- return f(n-2)+f(n-1);
- }
- public static void main(String[] args) {
- long start=System.currentTimeMillis();
- new Ch01();
- long end=System.currentTimeMillis();
- System.out.println("花費: "+(end-start)+" 毫秒");
- }
- }
- /*
- f(5)
- =f(3)+f(4)
- =f(1)+f(2)+f(2)+f(3)
- =1+f(0)+f(1)+f(0)+f(1)+f(1)+f(2)
- =1+0+1+0+1+1+f(0)+f(1)
- =1+1+1+1+1=5
- */
複製代碼- // 0 1 1 2 3 5 8 ...
- public class Ch02 {
- Ch02()
- {
- long data[]=new long[90];
- data[0]=0;
- data[1]=1;
- for(int i=2; i<90; i++)
- data[i]=data[i-2]+data[i-1];
- System.out.println("費氏數列第12項: "+data[12]);
- System.out.println("費氏數列第23項: "+data[23]);
- System.out.println("費氏數列第37項: "+data[37]);
- System.out.println("費氏數列第42項: "+data[42]);
- System.out.println("費氏數列第59項: "+data[59]);
- System.out.println("費氏數列第89項: "+data[89]);
- }
- public static void main(String[] args) {
- long start=System.currentTimeMillis();
- new Ch02();
- long end=System.currentTimeMillis();
- System.out.println("花費: "+(end-start)+" 毫秒");
- }
- }
複製代碼 C++- #include<bits/stdc++.h>
- using namespace std;
- int f(int n)
- {
- if(n<2)
- return n;
- else
- return f(n-2)+f(n-1);
- }
- int main()
- {
- cout<<"費氏數列第12項: "<<f(12)<<endl;
- cout<<"費氏數列第23項: "<<f(23)<<endl;
- cout<<"費氏數列第37項: "<<f(37)<<endl;
- cout<<"費氏數列第42項: "<<f(42)<<endl;
- cout<<"花費: "<<clock()<<" 毫秒"<<endl;
- return 0;
- }
複製代碼- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- long long data[90];
- data[0]=0;
- data[1]=1;
- for(int i=2; i<90; i++)
- data[i]=data[i-2]+data[i-1];
- cout<<"費氏數列第12項: "<<data[12]<<endl;
- cout<<"費氏數列第23項: "<<data[23]<<endl;
- cout<<"費氏數列第37項: "<<data[37]<<endl;
- cout<<"費氏數列第42項: "<<data[42]<<endl;
- cout<<"費氏數列第59項: "<<data[59]<<endl;
- cout<<"費氏數列第89項: "<<data[89]<<endl;
- cout<<"花費: "<<clock()<<" 毫秒"<<endl;
- return 0;
- }
複製代碼 |