【问题描述】著名的菲波拉契(Fibonacci)数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。
【分析】按菲波拉契数列的原则，数列为：0 1 1 2 3 5 8 13 21 34 55 ……无疑地，寻找其项数位置与项值的关系（即通项公式）是非常困难的。而根椐该数列的形成规则，其有一个的公式即“Ｕn＝Ｕn-1＋Ｕn-2”表明了相邻的数据项之间的明显关系。因此，可以其作为递推公式，以已知项0与1为起点，逐项产生第3项、第4项、……，直到取得需要的第N项为止。
【Pascal代码】
program Fibonacci;
var
n,i:longint;
function fib(n:longint):longint;{用递归算法求出数列中第N项}
begin
if n=1 then fib:=0;
if n=2 then fib:=1;
if n>2 then fib:=fib(n-1)+fib(n-2);
end;
begin
write("Input N:");
readln(n);
for i:=1 to n do write(" ",fib(i));{输出前N项}
readln;
end.
说明：下面是用非递归算法求第N项的方法
function fbi(n:longint):longint;
var
i,j,k,p:longint;
begin
i:=2;
j:=0;
k:=1;
repeat
i:=i+1;
p:=j+k;
j:=k;
k:=p;
until i=n;
fbi:=p;
end.
【C代码】
#include<stdio.h>
int fbi(int n)
{
if (n==1) return 0;
if (n==2) return 1;
if (n>2) return fbi(n-1)+fbi(n-2); else return 0;
}
void main()
{
int n,i;
printf("Input N:");
scanf("%d",&n);
for (i=1;i<=n;i++) printf("d% ",fbi(i));
getch();
}
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
