算法1-4 数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例

输入 #1

4

输出 #1

5

说明/提示

• 对于 60% 的数据，N≤50；
• 对于 100% 的数据，1≤N≤5000。走法数量过大，int、long long都装不下，要使用高精度

阶数  走法  构造斐波那契数列：从第三项开始，每一项等于前两项之和
0         1   a
1         1   b     a
2         2   c     b     a
3         3          c     b
4         5                 c

暴力写法：

#include<iostream>
using namespace std;

int n; 
int a, b, c; 

int main() 
{
	cin>>n;
	
	a = 1, b = 1;
	for(int i=2; i<=n; i++)
	{
		c = a + b;
		a = b;  //更新数据 
		b = c;
	}
	
	cout<<c; 
	
	return 0;
}

高精度：

#include<iostream>
using namespace std;

int n; 
int a[5010]={0, 1}, b[5010]={0, 1}; 
int c[5010]={0, 1}; //存储结果 阶数是1输出1 
int len = 1;

void f()
{
	int d = 0;
	for(int i=1; i<=len; i++)
	{
		c[i] = a[i] + b[i] + d;
		d = c[i]/10;
		c[i] %= 10;
	} 
	if(d>0)  
    {
    	len++;
    	c[len]=d;
	}
	
	//更新数据 
	for(int i=1; i<=len; i++)
	{
		a[i] = b[i];
		b[i] = c[i];
	}
}

int main() 
{
	cin>>n;
	
	for(int i=2; i<=n; i++)  //从第二阶开始 
	{
		f();
	}
	
	for(int i=len; i>=1; i--)  //逆序输出c中的数 
	{
		cout<<c[i];
	}
	
	return 0;
}