問題陳述：
?????? 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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
