斐波那契數列的編程

2019-11-06 06:38:03

字體：大中小

來源：轉載

供稿：網友

在面試的時候有時候考官會出這個題，我在面試北京知春路一家號稱做機器人的公司（奇虎？忘了）的時候就遇到了，果然是常考類型。寫fibonacci數列的兩種算法：其中 f(n) = 0 n=0 f(n) = 1 n = 1 f(n) = f(n-1) + f(n-2）n>1 解法一當然是普通遞歸解法

// test.cpp : 定義控制臺應用程序的入口點。//#include "stdafx.h"#include "stdio.h"int fibonacci(int n){ if(n==0){ return 0; }else if(n==1){ return 1; }else{ return fibonacci(n-1) + fibonacci(n-2); }} int _tmain(int argc, _TCHAR* argv[]){ int res = fibonacci(10); 但是，這種效率不高，通常需要第二種解法，換成循環的

// test.cpp : 定義控制臺應用程序的入口點。//#include "stdafx.h"#include "stdio.h"long long fibonacci(unsigned int n){ if(n==0 || n==1){ return n; }else{ long long f1 = 0; long long f2 = 1; long long f3 = 0; for(int i=2;i<=n;i++){ f3 = f2 + f1; f1 = f2; f2 = f3; } return f3; }} int _tmain(int argc, _TCHAR* argv[]){ long long res = fibonacci(10); printf("the result is %d",res); getchar(); return 0;}

1.可以看到代碼片段用了long long 和unsigned int 數據類型，并不只是用了簡單的int，這是為了增大表示的數據范圍。 int : -2147483648 ～ 2147483647 unsigned int : 0 ～ 4294967295 long long : -9223372036854775808 ～ 9223372036854775807 2.上段程序只用了三個變量就把程序寫出來了，原來我還想用數組或者vector，看了參考答案，果然自己還有很多路要走。 3.似乎用到了變量的替換 a =b;b =c;c =a;

reference : [1] 劍指offer[M].p73,面試題9，斐波那契數列。 [2] long long 博客