HDU1250 Hat's Fibonacci(大数)

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

导读：题目： Hat's Fibonacci Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11406????Accepted Submission(s): 3802 Problem Description A Fibonacci sequence is calculated by adding the prev

题目：

Hat's Fibonacci

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11406????Accepted Submission(s): 3802

Problem Description

A Fibonacci sequence is calculated by adding the previous two members the sequence,with the first two members being both 1.
F(1) = 1,F(2) = 1,F(3) = 1,F(4) = 1,F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input,and print that Fibonacci number.

Input

Each line will contain an integers. Process to end of file.

Output

For each case,output the result in a line.

Sample Input

Sample Output

  
  
   
   4203968145672990846840663646


Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data,ie. F(20) = 66526 has 5 digits.

Author

戴帽子的

思路：

比赛的题，用模板水一发，顺便存存代码~

代码：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
string num[8000];
string dashu(string a,string b)
{
    string s;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    int i = 0;
    int m,k = 0;
    while(a[i] && b[i])
    {
        m = a[i] - '0' + b[i] - '0' + k;
        k = m / 10;
        s += (m % 10 + '0');
        i++;
    }
    if(i == a.size())
    {
        while(i != b.size())
        {
            m = k + b[i] - '0';
            k = m / 10;
            s += m % 10 + '0';
            i++;
        }
        if(k) s += k + '0';
    }
    else if(i == b.size())
    {
        while(i != a.size())
        {
            m = k + a[i] - '0';
            k = m / 10;
            s += m % 10 + '0';
            i++;
        }
        if(k) s += k + '0';
    }
    reverse(s.begin(),s.end());
    return s;
}
void init()
{
    num[1]=num[2]=num[3]=num[4]="1";
    for(int i=5; i<=7800; i++)
        num[i]=dashu(dashu(num[i-1],num[i-2]),dashu(num[i-3],num[i-4]));
}
int main()
{
    int n;
    init();
    while(~scanf("%d",&n))
    {
        cout<<num[n]<<endl;
    }
    return 0;
}

（编辑：李大同）

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

HDU1250 Hat&#39;s Fibonacci(大数)

Hat's Fibonacci

HDU1250 Hat's Fibonacci(大数)