已知Fibonacci數(shù)列,
- 教育綜合
- 2024-02-17 12:59:52
已知Fibonacci數(shù)列定義如下：F(1)=1 F(2)=1 F(n)=f(n-1)+f(n-2)(n>2).求Fibonace:數(shù)列的第18項(xiàng)
Private Sub Form_Click() Dim f(100) As Long f(1) = 1 f(2) = 1 Print 1; f(1) Print 2; f(2) For i = 3 To 18 f(i) = f(i - 1) + f(i - 2) Print i; f(i) Next End Sub 運(yùn)行結(jié)果：f（18）＝2854已知fibonacci數(shù)列：1，1，2，3，5，8，......，它可由下面公式表述：
這個(gè)是用C寫的。會要求輸入一個(gè)整數(shù)，此時(shí)輸入50即可。當(dāng)然可以略作修改，只算F(50)。
#include
int main()
{
int n, first = 0, second = 1, next, c;
printf("Enter the number of terms\n");
scanf("%d",&n);
printf("First %d terms of Fibonacci series are :-\n",n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
return 0;
}
斐波那契數(shù)列的定義者
是意大利數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍貫是比薩。他被人稱作“比薩的萊昂納多”。1202年，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個(gè)研究了印度和阿拉伯?dāng)?shù)學(xué)理論的歐洲人。
他的父親被比薩的一家商業(yè)團(tuán)體聘任為外交領(lǐng)事，派駐地點(diǎn)于阿爾及利亞地區(qū)，萊昂納多因此得以在一個(gè)阿拉伯老師的指導(dǎo)下研究數(shù)學(xué)。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯等地研究數(shù)學(xué)。另外斐波納契還在計(jì)算機(jī)C語言程序題中應(yīng)用廣泛。
分別用非遞歸和遞歸的方法編寫函數(shù)求斐波那契數(shù)列第n項(xiàng)。斐波那契數(shù)列1，1，2，3，5，8，13，…
/**
已知Fibonacci數(shù)列：1,1,2,3,5,8,……，F(xiàn)(1)=1，F(xiàn)(2)=1，F(xiàn)(n)=F(n-1)+F(n-2)
*/
#include
#include
typedef long long int int64;
//方法1，遞歸法
int64 Fibonacci(int n)
{
int64 sum;
if(n<=0)
{
printf("參數(shù)值非法!\n");
exit(-1); //直接終止程序
}
if(n==1 || n==2)
return 1;
else
sum=Fibonacci(n-1)+Fibonacci(n-2);
return sum;
}
非遞歸法
int64 Fibonacci2(int n)
{
int64 a,b,c;
if(n<=0)
{
printf("參數(shù)值非法!\n");
exit(-1); //直接終止程序
}
if(n==1 || n==2)
return 1;
a=b=1; //對前兩項(xiàng)的值初始化
n=n-2; //因?yàn)槭菑牡?項(xiàng)開始記次數(shù)，所以減2
while(n > 0)
{
c=a+b;
a=b;
b=c;
n--;
}
return c;
}
//測試主函數(shù)
int main()
{
int n;
scanf("%d",&n); //輸入n
//printf("F(%d)=%lld\n",n,Fibonacci(n));
printf("F(%d)=%lld\n",n,Fibonacci2(n));
return 0;
}
//示例運(yùn)行結(jié)果
F:\c_work>a.exe
5
F(5)=5
F:\c_work>a.exe
6
F(6)=8
program fibo;var n,i:integer; rs:extended;function fib(m:integer):extended;var a,b:extended;
begin
a:=1;b:=1;if m<=2 then exit(1)else while m>3 do begin
fib:=a+b;a:=b;b:=fib;m:=m-1;end;exit(fib);end;
begin
read(n);writeln(fib(n));end.
擴(kuò)展資料：
從第二項(xiàng)開始，每個(gè)偶數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積少1，每個(gè)奇數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積多1。
如：第二項(xiàng)1的平方比它的前一項(xiàng)1和它的后一項(xiàng)2的積2少1，第三項(xiàng)2的平方比它的前一項(xiàng)1和它的后一項(xiàng)3的積3多1。
（注：奇數(shù)項(xiàng)和偶數(shù)項(xiàng)是指項(xiàng)數(shù)的奇偶，而并不是指數(shù)列的數(shù)字本身的奇偶，比如從數(shù)列第二項(xiàng)1開始數(shù)，第4項(xiàng)5是奇數(shù)，但它是偶數(shù)項(xiàng)，如果認(rèn)為5是奇數(shù)項(xiàng)，那就誤解題意，怎么都說不通）
證明經(jīng)計(jì)算可得：[f(n)]^2-f(n-1)f(n+1)=(-1)^(n-1)
參考資料來源：百度百科-斐波那契數(shù)列
c問題,fibonacci數(shù)列
該問題屬于fibonacci取余的問題
解法如下：
需要注意的是：
1：這道題目，建議用臨時(shí)變量，沒必要用數(shù)組存數(shù)列，因?yàn)轭}目不關(guān)心數(shù)列，只關(guān)心取余，也無法知道要設(shè)置多大的數(shù)組合適，設(shè)置小了，數(shù)組溢出，設(shè)置大了，影響內(nèi)存（特別是像這樣定義了這樣的大數(shù)組data[20000]，在之后的找工作，面試是很被動，很容易被刷）；
2：為了防止n太大，f(n)的值導(dǎo)致int存不下，可分步取余（c=(a+b)%10007），然后再加，再取余;
f(n-1)=( f(n-2)+f(n-3) )%10007
f(n-2)=( f(n-3)+f(n-4) )%10007
f(n)=( f(n-1)+f(n-2) )%10007
