数楼梯

数楼梯

题目描述

楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

1
4

样例输出 #1

1
5

提示

  • 对于60%的数据，N<50；
  • 对于100%的数据，1<N<5000。

分析

直接用简单的递归的话,数据过大栈会溢出
用数组的话也是超时
所以用高精度加法

高精度算法

算法核心:

也就是把个十百千位分别相加

1
2
3
c[i]=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std; 
int n,len=1,f[5005][5005];
void hp(int 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;
	cin>>n;
	f[1][1]=1;
	f[2][1]=2;
	for(i=3;i<=n;i++){
	hp(i);
	}
	
	for(i=len;i>=1;i--)
	{
		cout<<f[n][i];
	}
	return 0; 
	
}