【洛谷习题】P1255 数楼梯
习题 洛谷
2023-06-13 09:16:13 时间
题目描述
楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入格式
一个数字,楼梯数。
输出格式
走的方式几种。
输入样例
4
输出样例
5
说明/提示
60% N<=50 100% N<=5000)
思路与解法
根据题意会发现,到每阶楼梯的走法数量和斐波那契数列很相像,都是f[i] = f[i-2]+f[i-1],但基准情况有点不同,先总结出该题公式
于是完全按公式写出一个解法
#include<iostream>
using namespace std;
unsigned long long f[5005]; //存储走到第i阶楼梯有多少种走法的余数
int main(){
int n;
cin >> n;
f[1] = 1,f[2] = 2;
for(int i = 3;i <= n;i++)
f[i] = f[i-2] + f[i-1];
cout << f[n] << endl;
return 0;
}
但这个解法显然是会溢出的,即使是unsigned long long也不可能装下f(5000),这时可以考虑用数组来存储单个值,自己模拟一个高精度的加法。代码如下
#include<iostream>
#include<cstring>
using namespace std;
char f[5005][2000]; //存储走到第i阶楼梯有多少种走法的余数
inline void bigAdd(char *ret,const char *f1,const char *f2){
int flag = 0; //进位
int i;
for(i = 0;f1[i]!='\0'||f2[i]!='\0'||flag;++i){
int a = f1[i]?f1[i]-'0':0;
int b = f2[i]?f2[i]-'0':0;
if(a+b+flag >= 10){ //如果要进位
ret[i] = a+b+flag-10+'0';
flag = 1;
}
else{
ret[i] = a+b+flag+'0';
flag = 0;
}
}
}
int main(){
int n;
cin >> n;
strcpy(f[0],"0");
strcpy(f[1],"1");
strcpy(f[2],"2");
for(int i = 3;i <= n;i++)
bigAdd(f[i],f[i-2],f[i-1]);
for(int i = strlen(f[n])-1;i >= 0;--i)
cout << f[n][i];
cout << endl;
return 0;
}
上面用的是字符数组存储数值,也可以直接使用整型数组来存储,更加方便计算,同时在计算方面,可以直接遍历两数每位,存储相加的值先不进位,然后再第二遍遍历时来处理进位,最后依然是倒序输出。附上该题第一位题解的代码,该代码原地址。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数
void hp(int k)//高精度加法,k来存阶数
{
int i;
for(i=1;i<=len;i++)
f[k][i]=f[k-1][i]+f[k-2][i];//套用公式
for(i=1;i<=len;i++) //进位
if(f[k][i]>=10)
{
f[k][i+1]+=f[k][i]/10;
f[k][i]=f[k][i]%10;
if(f[k][len+1])len++;
}
}
int main()
{
int i;
scanf("%d",&n);
f[1][1]=1; f[2][1]=2; //初始化
for(i=3;i<=n;i++) //从3开始避免越界
hp(i);
for(i=len;i>=1;i--) //逆序输出
printf("%d",f[n][i]);
return 0;
}
相关文章
- 《Android移动应用基础教程》(Android Studio)(第二版)黑马程序员 课后习题答案
- 嵌入式系统原理课后习题练习
- c语言oj平台作业,OJ平台C语言习题答案.pdf
- 操作系统之进程管理习题[通俗易懂]
- 数据结构、算法与应用 习题6.1 p124
- Go语言圣经–Channel习题详解编程语言
- Go语言圣经-错误,函数值习题详解编程语言
- go语言圣经-声明,变量,赋值,类型,包和文件习题详解编程语言
- Linux习题解析:路过攻克Linux学习难题(linux习题解答)
- 【Linux教程课后习题解析】(linux教程课后习题答案)
- 深入浅出Linux C语言习题集(linuxc语言习题)
- MySQL查询练习: 练就精彩查询能力 (mysql查询习题)
- 解析oracle习题,超星平台助你一臂之力(oracle习题超星平台)