/*fibonacci: 1 1 2 3 5 8 13 21 ...*/
#include "stdio.h"
#include "sys/time.h"
#include "string.h"
#include "time.h"
/*遞歸法, O((3/2)^n)*/
int fibo1(int n){
if(n <= 2)
return 1;
else
return fibo1(n-1) + fibo1(n-2);
}
/*迭代法, O(n)*/
int fibo2(int n){
int x = 1, y = 1;
int i = 0;
for(i = 2; i < n; i++){
y = x + y;
x = y - x;
}
return y;
}
/*矩陣快速冪法, O(logn)
* |1,1|(n-1)
* F(n) = | | * F(1)
* |1,0|
*/
void multiply(int F[2][2], int M[2][2]){
int a = F[0][0] * M[0][0] + F[0][1]*M[1][0];
int b = F[0][0] * M[0][1] + F[0][1]*M[1][1];
int c = F[1][0] * M[0][0] + F[1][1]*M[1][0];
int d = F[1][0] * M[0][1] + F[1][1]*M[1][1];
F[0][0] = a;
F[0][1] = b;
F[1][0] = c;
F[1][1] = d;
}
void power(int F[2][2], int n){
if(n < 2)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if( n & 1)
multiply(F, M);
}
int fibo3(int n){
int F[2][2] = {{1,1},{1,0}};
if(!n)
return 0;
power(F, n-1);
return F[0][0];
}
int main(int argc, char *argv[]){
int n = 0;
unsigned int Fn = 0;
clock_t start, end;
printf("input number:\n");
scanf("%d", &n);
/*
struct timeval tv1, tv2;
unsigned long usecs = 0;
gettimeofday(&tv1, NULL);
Fn = fibo1(n);
gettimeofday(&tv2, NULL);
usecs = tv2.tv_sec*1000000 + tv2.tv_usec - tv1.tv_sec*1000000 - tv1.tv_usec;
printf("fibo1, f(%d):%u, us:%ld\n", n, Fn, usecs);
memset(&tv1, 0, sizeof(struct timeval));
memset(&tv2, 0, sizeof(struct timeval));
gettimeofday(&tv1, NULL);
Fn = fibo2(n);
gettimeofday(&tv2, NULL);
usecs = tv2.tv_sec*1000000 + tv2.tv_usec - tv1.tv_sec*1000000 - tv1.tv_usec;
printf("fibo2, f(%d):%u, us:%ld\n", n, Fn, usecs);
*/
start = clock();
Fn = fibo1(n);
end = clock();
printf("fibo1, f(%d):%u, sec:%f\n", n, Fn, (double)(end - start)/CLOCKS_PER_SEC);
start = clock();
Fn = fibo2(n);
end = clock();
printf("fibo2, f(%d):%u, sec:%f\n", n, Fn, (double)(end - start)/CLOCKS_PER_SEC);
start = clock();
Fn = fibo3(n);
end = clock();
printf("fibo3, f(%d):%u, sec:%f\n", n, Fn, (double)(end - start)/CLOCKS_PER_SEC);
return 0;
}
斐波那契數(shù)列算法
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)首尼，“玉大人，你說(shuō)我怎么就攤上這事软能。” “怎么了查排？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)跋核。 經(jīng)常有香客問(wèn)我，道長(zhǎng)砂代，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任泊藕，我火速辦了婚禮，結(jié)果婚禮上娃圆，老公的妹妹穿的比我還像新娘蛾茉。我一直安慰自己讼呢，他們只是感情好谦炬，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布节沦。 她就那樣靜靜地躺著，像睡著了一般础爬。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上看蚜，一...
- 那天，我揣著相機(jī)與錄音供炎，去河邊找鬼。 笑死音诫，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的竭钝。 我是一名探鬼主播，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼香罐，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了穴吹？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤港令，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后顷霹，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體咪惠，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡淋淀，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了朵纷。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
- 正文 年R本政府宣布，位于F島的核電站梗劫，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏猫妙。R本人自食惡果不足惜割坠，卻給世界環(huán)境...
- 文/蒙蒙 一敢朱、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧蚓哩，春花似錦岸梨、人聲如沸曹阔。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)园蝠。三九已至彪薛，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背豆茫。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長(zhǎng)得像祖很，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子假颇，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 原文發(fā)表于公眾號(hào) “l(fā)abuladong”坦冠，本文只是轉(zhuǎn)載，略有改動(dòng)哥桥，侵刪拟糕。 暴力遞歸 斐波那契數(shù)列的數(shù)學(xué)形式就是遞...
- 有一個(gè)大家都很熟悉的經(jīng)典數(shù)學(xué)問(wèn)題判呕，即斐波那契數(shù)列算法問(wèn)題送滞。這個(gè)經(jīng)典案例在算法中又會(huì)變成什么樣子呢？ int fib...
- ?斐波那契數(shù)列算法中究竟應(yīng)該使用哪種數(shù)據(jù)類型呢肥矢？ 總結(jié) unsigned long long端衰，能表示的最大斐波那契...
- 斐波那契數(shù)列簡(jiǎn)稱兔子數(shù)列十艾，是一道非常高頻的面試題抵代。 為什么它如此受面試官們的歡迎忘嫉？原因有三： 第一：這個(gè)題目的答案...
