关于斐波那契(Fibonacci)数列的代码

admin admin 2月16日

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用
(一上引用自百度百科https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145 斐波那契数列)
基本循环算法

# include <iostream>
# include <cstdio>
using namespace std;
int main(){    
    int a=0,b=1,c=1,n;    
    cin>>n;//输入n    
    for(int i=3;i<=n;i++){        
        a=b;        
        b=c;        
        c=a+b;    
    }    
    cout<<c; //输出最终结果     
    return 0
}

递归算法实现

# include <iostream>
# include <cstdio>
using namespace std;
int f(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    if(n>=2){
        return f(n-1)+f(n-2);
    }
}
int main(){
    int n;
    cin>>n;
    printf("%d",f(n));
    return 0;
}

递归算法优化(记忆化搜索)

# include <iostream>
# include <cstdio>
# define MAX (101)
using namespace std;
int a[MAX];
int f(int n){
    if(a[n]!=0) return a[n];
    else{
        a[n]=f(n-1)+f(n-2);
        return a[n];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<=MAX-1;i++){        //初始化 
        a[i]=-1;
    }
    a[0]=0;a[1]=1;
    printf("%d",f(n));
    return 0;
}

高精度计算

#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0,m=0,n;
int main()
{
    cin>>n;
    string s1,s2;
    int a[1200],b[1200];
    int he,i;

    s1="0";
    s2="1";
    for(m=2;m<n;m++)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0]=s1.length();
        for(i=1;i<=a[0];i++)
        {
            a[i]=s1[a[0]-i]-'0';
        }
        b[0]=s2.length();
        for(i=1;i<=b[0];i++)
        {
            b[i]=s2[b[0]-i]-'0';
        }
        he=(a[0]>b[0]?a[0]:b[0]);
        for(i=1;i<=he;i++)
        {
            a[i]+=b[i];
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
        he++;
        while((a[he]==0)&&(he>1))
        he--;
            for(i=he,s=0;i>=1;i--,s++)
            {
                sum[s]=a[i]+'0';
            }
        s1=s2;
        s2=sum;
    }
    cout<<s2<<endl;
    return 0;
}
expand_less