斐波那契数列
我也没有想到会遇到一道面试题斐波那契数列：0 1 1 2 3 5 8 13 21 34 55 89 144...
什么是斐波那契数列(Fibonacci sequence)，又称为黄金分割数列，或称为兔子数列，指的是1 1 2 3 5 8 13 21 34 55 ...
其实之前也遇到这种，当时在学习c语言的时候解决了，印象并不是那么深刻，太多东西理解不到位，太多东西需要学习，然后上网找了找，其实一看原理就懂了，无外乎前两数之和等于第三项、固定前面两项而已。
C++实现方法：
#include <iostream>
using namespace std;
int main(void)
{
int f1 = 0,f2 = 1;
int n = 0;
int temp = 0;
int m = 12;// 输出前12个
cout << “数列第1个数为”<<f1<<endl;
cout << “数列第2个数为”<<f2<<endl;
for (n = 3;n <=m;n++)
{
temp = f2;
f2 = f1+ temp;
f1 = temp;
}
cout << “数列第”<< n <<”个： “<<f2<<endl;
return 0;
}
这是输出斐波那契数列，当然可以封装函数。
0 当N=0
f(n)= 1当n=1
f(n-1)+ f(n-2),当n>1
c语言实现方式1：数组方式，
把整个斐波那契数列当成数组的值，下面是数组序号。
int fbiArray(int n){
if(n< 0)
{
printf(“输入错误\n”);
return 0;
}
inti = 0;
intarr[n];
arr[0]= 0;
arr[1]= 1;
//从第三个数开始规则
for(i= 2;i < n; i++){
arr[i] = arr[i-1] + arr[i-2];
//printf(“%d”,arr[i]);
}
returnarr[i];
}
c语言实现方式2：递归方式.
intfbiFunction(int i){
if(i< 2){
returni = 0?0:1;
}
returnfbiFunction(i – 1) + fbiFunction(i - 2);
}
当然也有别的方法实现，这是最简单两种的实现方式了。
