問題陳述:
?????? Fibonacci為1200年代的歐洲數(shù)學(xué)家,在他的著作中曾經(jīng)提到:若有一只兔子每個月生一只小兔子,一個月后小兔子也開始生產(chǎn)。起始只有一只兔子,一個月后就有兩只兔子,二個月后有三只兔子,三個月后有五只兔子(小兔投入生產(chǎn))......。這就是Fibonacci數(shù)列,一般習(xí)慣稱之為費氏數(shù)列,例如如下: 1 1 2 3 5 8 13 21 34 55 89.....
?
問題解法:
?????? 根據(jù)問題陳述,我們可以將費氏數(shù)列定義為一下:
?????? F(n) = F(n-1) + F(n-2)??????? if n > 1
?????? F(n) = 1???????????????????????????? if n = 0, 1
?????? Fibonacci有兩種最常見的解法,即迭代法和遞歸法。
?
代碼詳解:
1 /* 2 注:fibanacci數(shù)列下標從0開始 3 fibRecurse(int n) 遞歸計算數(shù)列下標為n的值 4 fibIterate(int n) 迭代計算數(shù)列下標為n的值 5 */ 6 #include <stdio.h> 7 #include <stdlib.h> 8 9 int fibRecurse( int n); 10 int fibIterate( int n); 11 12 int main() 13 { 14 int i, n; 15 printf( " Please input a number : " ); 16 scanf( " %d " , & n); 17 printf( " Recursion:\n " ); 18 for (i= 0 ; i<n; i++ ) { 19 printf( " %-5d " ,fibRecurse(i)); 20 if ((i+ 1 )% 10 == 0 ) { 21 printf( " \n " ); 22 } 23 } 24 printf( " \n " ); 25 printf( " Iteration:\n " ); 26 for (i= 0 ; i<n; i++ ) { 27 printf( " %-5d " ,fibIterate(i)); 28 if ((i+ 1 )% 10 == 0 ) { 29 printf( " \n " ); 30 } 31 } 32 return 0 ; 33 } 34 35 int fibRecurse( int n) { 36 if (n < 0 ) { 37 return - 1 ; 38 } 39 if (n== 0 || n== 1 ) { 40 return 1 ; 41 } else { 42 return fibRecurse(n- 1 ) + fibRecurse(n- 2 ); 43 } 44 } 45 46 int fibIterate( int n) { 47 int a = 1 , b = 1 , i, s; 48 if (n < 0 ) { 49 return - 1 ; 50 } 51 if (n== 0 || n== 1 ) { 52 return 1 ; 53 } else { 54 for (i= 1 ; i<n; i++ ) { 55 s = a+ b; 56 a = b; 57 b = s; 58 } 59 } 60 return s; 61 }
?
轉(zhuǎn)載請注明出處: http://www.cnblogs.com/michaelwong/p/4114942.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
