📄 fibonaccinumber.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>费式数列</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 费式数列</a></h1>
<h2> 说明</h2>
Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：“若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免
子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......”。 <br>
<br>
如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数
列，一般习惯称之为费氏数列，例如以下： <br>
1、1 、2、3、5、8、13、21、34、55、89......
<h2> 解法</h2>
依说明，我们可以将费氏数列定义为以下： <br>
<div style="margin-left: 40px; font-weight: bold; font-family: Courier New,Courier,monospace;">fn = fn-1 + fn-2 if n > 1<br>
fn = n if n = 0, 1 </div>
<h2> 演算法</h2>
费氏阵列的解法很多，基本上可以使用递回解，演算法最简单，如下： <br>
<pre>Procedure FIB(N) [<br> IF (N < 0) <br> PRINT ("输入错误"); <br><br> IF (N = 0 OR N = 1) <br> RETURN (N); <br> ELSE <br> RETURN ( FIB(N-1) + FIB(N-2) ); <br>] <br></pre>
<br>
简单，但是不实用，因为太慢了，在求每一个费氏数时，都会发生严重的重覆计算，也就是递回该行 ( FIB(N-1) + FIB(N-2)
)，最差的big-o可以到2的n/2次方，画张递回的树状图就可以知道重覆计算的数有多少了。 <br>
<br>
可以采取非递回的版本，可以将big(o)减至n，演算法如下： <br>
<pre>Procedure FIB(N) <br> a = 1; <br> b = 1; <br> FOR i = 2 TO N [<br> temp = b; <br> b = a + b; <br> a = temp; <br> ]<br> RETURN b; <br>] <br></pre>
<br>
若想要一次列出所有N之前的费氏数，则可以将for回圈的部份改以阵列，也就是： <br>
<pre>F(0) = 0; <br>F(1) = 1; <br>FOR i<-2 TO N [<br> F(i) = F(i-1) + F(i-2); <br>] <br></pre>
<br>
费氏阵列并不是使用递回来解一定不好，事实上单就执行次数上来说，有一个使用递回的演算法可以更快
(big(o)是以2为底的Logn值)，但是要使用到乘法运算，所以实际上要看所使用的机器而定。 <br>
<pre>Procedure FIB(N) <br> IF (n <= 1)<br> RETURN(n); <br><br> IF (n = 2) <br> RETURN(1); <br> ELSE [ <br> i = n/2; <br> f1 = FIB(i+1); <br> f2 = FIB(i); <br><br> IF (n mod 2 = 0)<br> RETURN( f2*(2*f1-f2) ); <br> ELSE <br> RETURN ( f1**2+f2**2 ); <br> ]<br>] <br></pre>
<br>
您可以实际使用费氏数列来印证演算法中的那两条公式，其中f1**2表示f1的平方；若将递回的树状图画出来，就像这样：<br>
<div style="text-align: center;"><img style="width: 399px; height: 178px;" alt="费式数列" title="费式数列" src="images/fibonacciNumber-1.jpg"></div>
<br>
另外费氏数列还有公式解，导证方式就不提了：<br>
<div style="text-align: center;"><img style="width: 320px; height: 53px;" alt="费式数列" title="费式数列" src="images/fibonacciNumber-2.jpg"></div>
您说，如果免子不只生一只小免子的话怎么办？像这种问题，我们可以将费氏数列加以扩充，称之为扩充费氏数列： <br>
<div style="margin-left: 40px; font-weight: bold;">fn = X * fn-1 + Y * fn-2 if n > 1<br>
fn = 1 if n = 0, 1 <br>
</div>
<br>
当X、Y等于1时，自然就是一般的费氏数列了。 <br>
<br>
想了解费氏数列与自然界神奇的关系，可以造访这个 <a href="http://episte.math.ntu.edu.tw/articles/sm/sm_02_08_1/index.html">网页<cite class="urllink"></cite></a>。
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>#define N 20 <br><br>int main(void) { <br> int Fib[N] = {0}; <br> int i; <br><br> Fib[0] = 0; <br> Fib[1] = 1; <br><br> for(i = 2; i < N; i++) <br> Fib[i] = Fib[i-1] + Fib[i-2]; <br><br> for(i = 0; i < N; i++) <br> printf("%d ", Fib[i]); <br> printf("\n"); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class Fibonacci {<br> public static void main(String[] args) {<br> int[] fib = new int[20]; <br><br> fib[0] = 0; <br> fib[1] = 1; <br><br> for(int i = 2; i < fib.length; i++) <br> fib[i] = fib[i-1] + fib[i-2]; <br><br> for(int i = 0; i < fib.length; i++) <br> System.out.print(fib[i] + " "); <br> System.out.println();<br> }<br>}</pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -