HDU Hat's Fibonacci

2017-11-16 996

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Hat's Fibonacci

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 268 Accepted Submission(s): 112

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.

用二维数组模拟大数加法，每一行表述一个数，每一行的一个元素可以代表n位数，这个可以根据自己的需要自己定义。

其他的就和正常的加法一样了，注意进位处理。

#include <iostream>
#include <stdio.h>
using namespace std;
int s[7500][670];
void solve(){
    s[1][1] = 1;s[2][1] = 1;
    s[3][1] = 1;s[4][1] = 1;
    int i,j,k=0;
    for(i = 5;i<7500;i++)
    for( j = 1;j<=670 ;j++)
    {
        k += s[i-1][j]+s[i-2][j]+s[i-3][j]+s[i-4][j];
        s[i][j] = k%10000;
        k = k/10000;
    }
    while(k)
    {
        s[i][j++] = k%10000;
        k = k/10000;
    }
}
int main()
{
    int n,i,j;
    solve();
    while(cin>>n)
    {
        for(i = 670; i>=1;i--)
        if(s[n][i]!=0)break;
        printf("%d",s[n][i]);
        for(j = i-1;j>=1;j--)
        printf("%04d",s[n][j]);
        printf("\n");
    }
}

本文转自NewPanderKing51CTO博客，原文链接： http://www.cnblogs.com/newpanderking/archive/2011/07/31/2122528.html ，如需转载请自行联系原作者

HDU Hat's Fibonacci

Hat's Fibonacci

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HDU Hat's Fibonacci

Hat's Fibonacci

热门文章

最新文章

相关电子书