project euler problem 25 大数连加Fibonacci序列

发布时间：2020-12-14 03:58:20 所属栏目：大数据来源：网络整理

导读：1000-digit Fibonacci number Problem 25 The Fibonacci sequence is defined by the recurrence relation: F n ?= F n 1 ?+ F n 2 ,where F 1 ?= 1 and F 2 ?= 1. Hence the first 12 terms will be: F 1 ?= 1 F 2 ?= 1 F 3 ?= 2 F 4 ?= 3 F 5 ?= 5 F 6 ?=

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F _n?= F _n
1?+ F _n
2,where F ₁?= 1 and F ₂?= 1.

Hence the first 12 terms will be:

F ₁?= 1
F ₂?= 1
F ₃?= 2
F ₄?= 3
F ₅?= 5
F ₆?= 8
F ₇?= 13
F ₈?= 21
F ₉?= 34
F ₁₀?= 55
F ₁₁?= 89
F ₁₂?= 144

The 12th term,F₁₂,is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

这题算法类似POJ 1503，稍加改动就行了，容易。

#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#include<iostream>
#include<cstring>
char a[1010],b[1010];
using namespace std;
int main()
{
    int k=0,abc=2;  //前面有两个数了，故abc=2
    cin>>a>>b;  //输入第一第二个数即输入：1   1
    while(k!=1000)
    {
        int i,j,p,q,c[2000]= {0};
        p=strlen(a);
        q=strlen(b);
        for(i=p-1,j=p; i>=0; i--)
        {
            if(i-p+q>=0) c[j]+=(a[i]-48)+(b[i-p+q]-48);  //模拟加法运算
            else c[j]+=(a[i]-48);
            if(c[j]>9)
            {
                c[j-1]+=1;
                c[j]-=10;
            }
            j--;
        }
        strcpy(b,a);    //b字符串就取当前的a字符串
        for(i=0; i<=p; i++)
        {
            if(c[i]!=0)
            {
                int m=0;
                for(; i<=p; i++)
                    a[m++]=c[i]+'0';    //a字符串更新为当前结果
                a[m]='';
            }
        }
        k=strlen(a);   //这两个数相加的结果的位数
        abc++;
    }
    cout<<abc<<endl;
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!