SDUT2876_走楼梯(大数)

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

导读：走楼梯 Time Limit: 1000ms?? Memory limit: 65536K??有疑问？点这里^_^ 题目描述小虎发现走楼梯的时候一次上一个台阶比较惬意，一次上两个台阶比较高效，一次上三个台阶就很累人。小虎是一个即注重质量又注重高效的人，于是他就在上楼梯的时候每步就只跨

走楼梯

Time Limit: 1000ms?? Memory limit: 65536K??有疑问？点这里^_^

题目描述

小虎发现走楼梯的时候一次上一个台阶比较惬意，一次上两个台阶比较高效，一次上三个台阶就很累人。

小虎是一个即注重质量又注重高效的人，于是他就在上楼梯的时候每步就只跨上一个台阶或两个台阶，

现在小虎想知道他这样上n阶的楼梯一共有多少种走法，但是他又不想亲身经历，只好求助于会编程的你，帮他解决这个问题了。

输入

第一行是T，表示接下来有T组输入，每组输入一个N（2 <= N <= 1000)

输出

对应每组输入输出一共有多少种走法。

示例输入

示例输出

89
55
28657

提示

来源

?解题报告

学了近半年的acm，一次校赛的热身赛题竟然不知道用大数写。。。sad。。。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
char dsf[1001][500]= {"0","1","2","3"};
int main()
{
    int a[500],b[500],i,j;
    for(i=3; i<=1000; i++)
    {
        memset(a,sizeof(a));
        memset(b,sizeof(b));
        int l1=strlen(dsf[i-1]);
        int l2=strlen(dsf[i-2]);
        for(j=0; j<l1; j++)
            a[j]=dsf[i-1][l1-j-1]-'0';
        for(j=0; j<l2; j++)
            b[j]=dsf[i-2][l2-j-1]-'0';
        for(j=0; j<max(l1,l2); j++)
        {
            a[j]+=b[j];
            if(a[j]>9)
            {
                a[j]-=10;
                a[j+1]++;
            }
        }
        for(j=400; j>=0; j--)
        {
            if(a[j]!=0)
            {
                break;
            }
        }
        int l=j,ll=j;
        for(j=0; j<=l; j++)
            dsf[i][j]=a[ll--]+'0';
        dsf[i][j]=0;

    }
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<dsf[n]<<endl;
    }
    return 0;
}

（编辑：李大同）

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