Herr Deng桑的教學blog: 費式數列

2009年10月1日星期四

費式數列

費式數列:

f[0]=f[1]=1
f[n]=f[n-1]+f[n-2]

請用迴圈算到n最大還是正確的f[n]值!

為什麼不要用遞迴做?

64 則留言:

b97331922009年10月1日下午3:01
#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{

int f[50] ;
int i = 2 ;
f[0] = f[1] = 1 ;
while ( i <= 49 ) {
f[i] = f[i-1] + f[i-2] ;
i++ ;
}

cout << i << "->" << f[i] << endl ;

system("PAUSE");
return EXIT_SUCCESS;

}
回覆刪除
回覆
B97331492009年10月1日下午3:09
#include <iostream>
using namespace std;
int main()
{
    unsigned f[52];
    f[0]=f[1]=1;
    for (int i=2;i<=49;i++)
    {
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system ("pause");
    return 0;
}

因為會讓程式在求每一個費氏數時，都會發生重覆計算的現象
回覆刪除
回覆
B97331382009年10月1日下午3:10
#include <iostream>
using namespace std;
int main()
{
    unsigned f[52];
    f[0]=f[1]=1;
    for (int i=2;i<=49;i++)
    {
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system ("pause");
    return 0;
}

在求每個費式時會產生重複運算
回覆刪除
回覆
b97331352009年10月1日下午3:11
#include <iostream>
using namespace std;
int main()
{
    unsigned f[52];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
         f[i]=f[i-1]+f[i-2];
         cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

因為會重複運算，時間會延長。
回覆刪除
回覆
B97331712009年10月1日下午3:12
#include <iostream>
using namespace std;
int main()
{
    unsigned f[52];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
         f[i]=f[i-1]+f[i-2];
         cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

因為會重複運算，時間會延長。
回覆刪除
回覆
B97331762009年10月1日下午3:13
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
    int f[52],n;
    f[0]=f[1]=1;
    for(n=2;n<=49;n++)
    {
    f[n]=f[n-1]+f[n-2];
    cout<<n<<"->"<<f[n]<<endl;
    }
    system("pause");
    return 0;
}

到45以前是準的

為何不用遞迴:
雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大。
回覆刪除
回覆
B97331652009年10月1日下午3:13
#include <iostream>
using namespace std;
int main()
{
    int f[52];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
{
    f[i]=f[i-1]+f[i-2];
    cout<<i<<"->"<<f[i]<<endl;
}
    system("Pause");
    return 0;
}

到45以前是準的

Q:為什麼不用遞廻?
A:
雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大。
回覆刪除
回覆
B97331842009年10月1日下午3:14
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int f[50];
    f[0]=1;
    f[1]=1;
    int i;
    for(i=2;i<=49;i++)
    {
         f[i]=f[i-1]+f[i-2];
         printf("f[%d]=%d\n",i,f[i]);
         }
         system("pause");
         return 0;
         }

到45以前是準的

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作
回覆刪除
回覆
B97331412009年10月1日下午3:15
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i;
unsigned f[50];
printf("輸入i:\n");
scanf("%d",&i);
f[0]=1;
f[1]=1;
     for(i=2;i<=49;i++)
     {
      f[i]=f[i-1]+f[i-2];
      printf("%d\n",i);
      printf("%d\n",f[i]);
     }

system("PAUSE");
return 0;
}
最大到45最大f[45]=1836311903
因為當呼叫到f(n-1)時,會重複做f(n-1)!!!
回覆刪除
回覆
B97331482009年10月1日下午3:17
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int f[50];
    f[0]=1;
    f[1]=1;
    int i;
    for(i=2;i<=49;i++)
    {
         f[i]=f[i-1]+f[i-2];
         printf("f[%d]=%d\n",i,f[i]);
         }
         system("pause");
         return 0;
         }

到45是準的

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作
回覆刪除
回覆
b97331662009年10月1日下午3:17
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,f[50];
    printf("輸入;");
    scanf("%d",&i);
    f[0]=f[1]=1;
      for(i=2;i<=49;i++)
      {
        f[i]=f[i-1]+f[i-2];
        printf("%d\n",i);
        printf("%d\n",f[i]);
      }
    system ("pause");
    return 0;
}

N為45
為何不用遞迴是因為會重複作n-1
但是答應仍相同
回覆刪除
回覆
B97331732009年10月1日下午3:18
f[46]開始出現錯誤

不使用遞迴是因為當n的數值太大，電腦會作很多次多餘的遞迴運算，程式效率低
回覆刪除
回覆
b97331682009年10月1日下午3:20
從46開始出現錯誤

不使用遞迴，因為當n大一點，電腦會作很多次多餘的遞迴運算，程式效率低
回覆刪除
回覆
B97331242009年10月1日下午3:24
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int f[52];
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=49;i++)
    {
           f[i]=f[i-1]+f[i-2];
           printf("f[%d]=%d\n",i,f[i]);
           }
    system("pause");
    return 0;
    }

為神不用遞迴,因為重複運算,時間就會變長,導致作業時間家長
回覆刪除
回覆
B97331752009年10月1日下午3:25
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int f[52];
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=49;i++)
    {
           f[i]=f[i-1]+f[i-2];
           printf("f[%d]=%d\n",i,f[i]);
           }
    system("pause");
    return 0;
    }

為神不用遞迴,因為重複運算,時間就會變長,
回覆刪除
回覆
B97331512009年10月1日下午3:25
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int f[52];
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=49;i++)
    {
           f[i]=f[i-1]+f[i-2];
           printf("f[%d]=%d\n",i,f[i]);
           }
    system("pause");
    return 0;
    }

為神不用遞迴,因為重複運算,時間就會變長,
回覆刪除
回覆
B97331502009年10月1日下午3:25
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int f[52];
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=49;i++)
    {
           f[i]=f[i-1]+f[i-2];
           printf("f[%d]=%d\n",i,f[i]);
           }
    system("pause");
    return 0;
    }

為神不用遞迴,因為重複運算,時間就會變長,
回覆刪除
回覆
B97331372009年10月1日下午3:28
include <iostream>
using namespace std;
int main()
{
unsigned f[52];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system("pause");
return 0;
}

可以參考到46

因為用遞回會延長時間成為指數時間
回覆刪除
回覆
B97331922009年10月1日下午3:28
#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{

unsigned f[50] ;
int i = 2 ;
f[0] = f[1] = 1 ;
while ( i <= 49 ) {
f[i] = f[i-1] + f[i-2] ;
cout << i << "->" << f[i] << endl ;
i++ ;

}

system("PAUSE");
return EXIT_SUCCESS;

}

i跑到46的時候還是正確的值
當i=47時，會出現不正確的數值

因為時間複雜度會成為指數時間而沒辦法用
回覆刪除
回覆
b97331272009年10月1日下午3:29
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,f[50];
    printf("輸入;");
    scanf("%d",&i);
    f[0]=f[1]=1;
      for(i=2;i<=49;i++)
      {
        f[i]=f[i-1]+f[i-2];
        printf("%d\n",i);
        printf("%d\n",f[i]);
      }
    system ("pause");
    return 0;
}

A:45
回覆刪除
回覆
B97331342009年10月1日下午3:29
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
    unsigned f[50];
    f[0]=f[1]=1;
    for(int i=2;i<=49;i++)
    {
        f[i]=f[i-1]+f[i-2];
        cout<<"f["<<i<<"]="<<f[i]<<'\n';
    }
    system("pause");
    return 0;
}

用遞迴時間複雜度大
回覆刪除
回覆
B97331612009年10月1日下午3:30
46開始
當 n 大一點，電腦會作很多次多餘的遞迴運算，程式效率低
回覆刪除
回覆
b97331232009年10月1日下午3:30
#include <stdio.h>
#include <stdlib.h>
int main()
{
int f[50];
f[0]=1;
f[1]=1;
int i;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
printf("f(%d)-->",i);
printf("-->%d\n",f[i]);
}
system("pause");
return 0;
}

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作，只是因為它用不用遞迴都可以解，而且比較簡單，所以教科書常拿它來做例子。
回覆刪除
回覆
B97331632009年10月1日下午3:31
46開始
當 n 大一點，電腦會作很多次多餘的遞迴運算，程式效率低
回覆刪除
回覆
b97331312009年10月1日下午3:31
#include<iostream>
#include<cstdlib>
using namespace std;
int main(){
unsigned f[50];
f[0]=f[1]=1;
int i;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<"f["<<i<<"]="<<f[i]<<'\n';
}
system("pause");
return 0;
}

遞迴方式的執行時間比迴圈方式久
回覆刪除
回覆
B97331332009年10月1日下午3:31
include <iostream>
using namespace std;
int main()
{
unsigned f[52];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system("pause");
return 0;
}

可以參考到46

使用遞回會延長時間
回覆刪除
回覆
b97331882009年10月1日下午3:31
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,f[50];
    printf("輸入;");
    scanf("%d",&i);
    f[0]=f[1]=1;
      for(i=2;i<=49;i++)
      {
        f[i]=f[i-1]+f[i-2];
        printf("%d\n",i);
        printf("%d\n",f[i]);
      }
    system ("pause");
    return 0;
}

a:45

因為會呼叫很多次來所以不需用遞迴!
回覆刪除
回覆
b97331272009年10月1日下午3:32
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,f[50];
    printf("輸入;");
    scanf("%d",&i);
    f[0]=f[1]=1;
      for(i=2;i<=49;i++)
      {
        f[i]=f[i-1]+f[i-2];
        printf("%d\n",i);
        printf("%d\n",f[i]);
      }
    system ("pause");
    return 0;
}

A:45

因為會一直呼叫,所以無需用遞迴
回覆刪除
回覆
b97331402009年10月1日下午3:32
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<49;i++)
    {
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }

    system("pause");
    return 0;
}

為什麼不用遞迴?
用遞迴函數程式呼叫多次,比較費時
用for迴圈不用呼叫程式
回覆刪除
回覆
B97331942009年10月1日下午3:32
include <iostream>
using namespace std;
int main()
{
unsigned f[52];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system("pause");
return 0;
}

可以參考到46

使用遞回會延長時間
回覆刪除
回覆
b97331742009年10月1日下午3:32
#include <stdio.h>
#include <stdlib.h>
int main()
{
int f[50];
f[0]=1;
f[1]=1;
int i;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
printf("f(%d)-->",i);
printf("-->%d\n",f[i]);
}
system("pause");
return 0;
}

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作，只是因為它用不用遞迴都可以解，而且比較簡單，所以教科書常拿它來做例子。
回覆刪除
回覆
b97331812009年10月1日下午3:33
#include <stdio.h>
#include <stdlib.h>
int main()
{
int f[50];
f[0]=1;
f[1]=1;
int i;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
printf("f(%d)-->",i);
printf("-->%d\n",f[i]);
}
system("pause");
return 0;
}

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作，只是因為它用不用遞迴都可以解，而且比較簡單，所以教科書常拿它來做例子。
回覆刪除
回覆
B97331302009年10月1日下午3:34
1.
#include <iostream>
using namespace std;
int main(){
    unsigned f[50];
    f[0]=f[1]=1;
    for(int i=2;i<50;i++){
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

到46準的
2.雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大
回覆刪除
回覆
B97331292009年10月1日下午3:34
1.
#include <iostream>
using namespace std;
int main(){
    unsigned f[50];
    f[0]=f[1]=1;
    for(int i=2;i<50;i++){
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

到46準的
2.雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大
回覆刪除
回覆
b97331932009年10月1日下午3:34
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    int f[50];
    f[0]=f[1]=1;
    for(int i=2;i<=49;i++)
{
    f[i]=f[i-1]+f[i-2];
    cout<<i<<"->"<<f[i]<<endl;
}
    system("PAUSE");
    return EXIT_SUCCESS;
}
因為計算出來的是指數時間。
回覆刪除
回覆
B97331462009年10月1日下午3:35
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int f[50];
    f[0]=1;
    f[1]=1;
    int i;
    for(i=2;i<=49;i++)
    {
         f[i]=f[i-1]+f[i-2];
         printf("f[%d]=%d\n",i,f[i]);
         }
         system("pause");
         return 0;
         }

如果你的遞迴程式的主迴圈當中，最多只有一個分枝會產生遞迴呼叫，那麼這其實是一個 linear recursive function，其實根本就不需要遞迴。例如二分搜尋法，二元樹的搜尋，或前述的的階乘都是，其實只需要一個迴圈垂直地做 n 次就可以了。這種情況用遞迴，似乎有點小題大作
回覆刪除
回覆
B97331452009年10月1日下午3:35
1.
#include <iostream>
using namespace std;
int main(){
    unsigned f[50];
    f[0]=f[1]=1;
    for(int i=2;i<50;i++){
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

到46準的
2.雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大
回覆刪除
回覆
b97331432009年10月1日下午3:35
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
B91331442009年10月1日下午3:35
1.
#include <iostream>
using namespace std;
int main(){
    unsigned f[50];
    f[0]=f[1]=1;
    for(int i=2;i<50;i++){
        f[i]=f[i-1]+f[i-2];
        cout<<i<<"->"<<f[i]<<endl;
    }
    system("pause");
    return 0;
}

到46準的
2.雖然遞迴函數可以很快地幫我們解決問題，但是它並不是一個有效率的寫法，因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2)，而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3)，如此一來，F(n-2) 就被重複呼叫了，隨著 n 越來越大，這個重複呼叫的次數會越來越大
回覆刪除
回覆
b97331322009年10月1日下午3:36
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331472009年10月1日下午3:36
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331592009年10月1日下午3:36
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331282009年10月1日下午3:36
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331422009年10月1日下午3:37
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331782009年10月1日下午3:37
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
B95330092009年10月1日下午3:37
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    int* f=new int[50];
f[0]=f[1]=1;
for (int i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"="<<f[i]<<endl;
}
    system("PAUSE");
    return EXIT_SUCCESS;
}

因為可以減少不必要打這麼多的程式
還有減少運算時間
加速運算
回覆刪除
回覆
B95330552009年10月1日下午3:37
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    int* f=new int[50];
    f[0]=f[1]=1;
    for(int i=2;i<=49;i++)
    {
    f[i]=f[i-1]+f[i-2];
    cout<<i<<"--"<<f[i]<<endl;
    }


    system("PAUSE");
    return EXIT_SUCCESS;
}

為何不要用遞迴做？
減少時間。（因為遞迴運作時間較長）
回覆刪除
回覆
b97331832009年10月1日下午3:37
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
B97331412009年10月1日下午3:37
(1)#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i;
unsigned f[50];
printf("輸入i:\n");
scanf("%d",&i);
f[0]=1;
f[1]=1;
     for(i=2;i<=49;i++)
     {
      f[i]=f[i-1]+f[i-2];
      printf("%d\n",i);
      printf("%d\n",f[i]);
     }

system("PAUSE");
return 0;
}
最大45最大f[45]=1836311903
(2)因為會造成指數時間
回覆刪除
回覆
b97331822009年10月1日下午3:38
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331792009年10月1日下午3:38
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331722009年10月1日下午3:38
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
b97331622009年10月1日下午3:39
#include <iostream>
using namespace std;
int main()
{
    unsigned f[50];
    int i;
    f[0]=f[1]=1;
    for(i=2;i<=49;i++)
    {
                      f[i]=f[i-1]+f[i-2];
                      cout<<i<<"->"<<f[i]<<endl;
                      }
    system("pause");
    return 0;
}

因為使用遞迴，會呼叫比較多次，用For迴圈就不用呼叫
回覆刪除
回覆
B95330672009年10月1日下午3:39
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    int f[50];
    f[0]=f[1]=1;
    for(int i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"去"<<f[i]<<endl;
}
    system("PAUSE");
    return EXIT_SUCCESS;
}

2.出來時間是指數時間
回覆刪除
回覆
b96330292009年10月1日下午3:39
#include<iostream>
#include<cstdlib>
using namespace std;
int main(){
          unsigned f[50];
          f[0]=f[1]=1;
          int i;
          for(i=2;i<=49;i++)
          {
            f[i]=f[i-1]+f[i-2];
            cout<<"f["<<i<<"]="<<f[i]<<'\n';
            }
          system("pause");
          return 0;
          }
假若輸入的數列為5
就會印出：迴圈方式執行結果：5, 執行時間：112微秒
遞迴方式執行結果：5, 執行時間：59微秒
遞迴方式的執行時間為迴圈方式的 0.53 倍。
回覆刪除
回覆
b97331252009年10月1日下午3:41
#include <iostream>
using namespace std;
int main(int argc,char*argv[])
{
unsigned f[50];
int i=2;
f[0]=f[1]=1;
while(i<=49)
{

f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
i++;
}
system("Pause");
return EXIT_SUCCESS;
}

因為i=45時，才是正確的數值
因為時間複雜度會為指數時間。
回覆刪除
回覆
B97331702009年10月1日下午3:41
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned f[50];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
   f[i]=f[i-1]+f[i-2];
}
for(i=0;i<=49;i++)
   {
   printf("%d\n",i);
   printf("%d\n",f[i]);
   }
system("pause");
return 0;
}

因為i=45時，才是正確的數值
因為時間複雜度為指數時間。
回覆刪除
回覆
b97331262009年10月1日下午3:45
#include<stdio.h>
#include<stdlib.h>
int main()
{
int f[50];
f[0]=f[1]=1;
for(int i=2;i<50;i++){
f[i]=f[i-1]+f[i-2];
printf("%d\n",i);
printf("%d\n" ,f[i]);
}
system("pause");
return 0;
}

因為指數時間
回覆刪除
回覆
b95330412009年10月14日晚上11:34
#include <iostream>
using namespace std;
int main()
{
unsigned f[50];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system("pause");
return 0;
}

使用遞迴，呼叫次數會比較多，使用For迴圈不用呼叫
回覆刪除
回覆
b95330312009年10月14日晚上11:36
#include <iostream>
using namespace std;
int main()
{
unsigned f[52];
f[0]=f[1]=1;
for (int i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system ("pause");
return 0;
}
回覆刪除
回覆
b95330312009年10月14日晚上11:38
#include <iostream>
using namespace std;
int main()
{
unsigned f[52];
f[0]=f[1]=1;
for (int i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system ("pause");
return 0;
}
回覆刪除
回覆
B95330532009年10月14日晚上11:42
unsigned f[50];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
}
for(i=0;i<=49;i++)
{
printf("%d\n",i);
printf("%d\n",f[i]);
}
system("pause");
return 0;
}

因為i=45時，才是正確的數值
因為時間複雜度為指數時間。
回覆刪除
回覆
B95331452009年10月26日晚上10:24
#include <iostream>

using namespace std;

int main()
{
unsigned f[52];
int i;
f[0]=f[1]=1;
for(i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<i<<"->"<<f[i]<<endl;
}
system("pause");
return 0;
}

參考至46 使用遞回會延長時間
回覆刪除
回覆
b96330062009年10月28日晚上8:12
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int f[52];
f[0]=1;
f[1]=1;
for(int i=2;i<=49;i++)
{
f[i]=f[i-1]+f[i-2];
printf("f[%d]=%d\n",i,f[i]);
}
system("pause");
return 0;
}

為神不用遞迴,因為重複運算,時間就會變長,
回覆刪除
回覆

新增留言

HTML 編輯器

網頁

2009年10月1日 星期四

費式數列

64 則留言:

2009年10月1日星期四