本文主要是介绍SDUT2876_走楼梯(大数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
走楼梯
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
小虎发现走楼梯的时候一次上一个台阶比较惬意,一次上两个台阶比较高效,一次上三个台阶就很累人。
小虎是一个即注重质量又注重高效的人,于是他就在上楼梯的时候每步就只跨上一个台阶或两个台阶,
现在小虎想知道他这样上n阶的楼梯一共有多少种走法,但是他又不想亲身经历,只好求助于会编程的你,帮他解决这个问题了。
输入
第一行是T,表示接下来有T组输入,每组输入一个N(2 <= N <= 1000)
输出
对应每组输入输出一共有多少种走法。
示例输入
3 10 9 22
示例输出
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,0,sizeof(a));memset(b,0,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;
}
这篇关于SDUT2876_走楼梯(大数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!