加载中...

POJ 3982 - The Fibonacci sequence

算法

原创

发布日期: 2011-04-21

更新日期: 2026-11-06

文章字数: 628

阅读时长: 3 分

阅读次数:

POJ 3982 - The Fibonacci sequence
Time: 1000MS
Memory: 65536K
难度: 初级
分类: 高精度算法

0x00 POJ 原题

题面据 POJ 3982 原文转载补录，并与另一份题面转载核对；保留原有中文题面，补齐 Markdown 排版。

Description

数列 A 满足 An = An-1 + An-2 + An-3, n >= 3。

编写程序，给定 A0、A1 和 A2，计算 A99。

Input

输入包含多行数据。

每行数据包含 3 个整数 A0、A1、A2，0 <= A0, A1, A2 <= 32767。

数据以 EOF 结束。

Output

对于输入的每一行，输出 A99 的值。

Sample Input

1 1 1

Sample Output

69087442470169316923566147

0x10 题目概述

变种的大数斐波那契数列

0x20 解题思路

水题，直接加就可以了，循环使用 4 个大数数组 a,b,c,ans 存放最新的和值，循环 25 次后的 ans 就是 A99 的值

0x30 AC 源码

//Memory Time
//216K   32MS 

#include<iostream>
#include<string>
using namespace std;

const int size=1000;   //大数位数

void add(char* aa,char* bb,char* cc,char* ans)
{
    int a[size+1]={0};
    int b[size+1]={0};
    int c[size+1]={0};
    int pa=0,pb=0,pc=0;

    int lena=strlen(aa);
    int lenb=strlen(bb);
    int lenc=strlen(cc);

    /*倒序*/

    for(int i=lena-1;i>=0;i--)
        a[pa++]=aa[i]-'0';
    for(int j=lenb-1;j>=0;j--)
        b[pb++]=bb[j]-'0';
    for(int k=lenc-1;k>=0;k--)
        c[pc++]=cc[k]-'0';

    int len=lena>lenb?lena:lenb;
    len=len>lenc?len:lenc;
    char* d=new char[len+2];  //倒序的ans

    int w=0;  //低位到高位的进位
    for(int x=0;x<=len;x++)  //'='为了处理最高位的进位
    {
        int temp=a[x]+b[x]+c[x]+w;
        d[x]=temp%10+'0';
        w=temp/10;
    }

    bool flag=false;
    bool sign=false;  //标记ans是否为全0
    for(w=0;len>=0;len--)  //w和len均作指针使用，已无意义
    {
        if(!flag && d[len]=='0')   //删除数字开头的0
            continue;
        else
            flag=true;

        sign=true;
        ans[w++]=d[len];
    }
    if(sign)
        ans[w]='\0';
    else
    {
        ans[0]='0';
        ans[1]='\0';
    }

    delete d;
    return;
}

char a[size+1];
char b[size+1];
char c[size+1];
char ans[size+1];
int main(void)
{
    while(cin>>a>>b>>c)
    {
        for(int i=1;i<=25;i++)
        {
            add(a,b,c,ans);
            add(b,c,ans,a);
            add(c,ans,a,b);
            add(ans,a,b,c);
        }
        cout<<ans<<endl;   //循环25次后，ans刚好是第99个数的值
    }
    return 0;
}