洛谷P1255 数楼梯

Dear 丶 2022-05-26 08:11 156阅读 0赞

## 题目描述 ##

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

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

## 输入输出格式 ##

输入格式：

一个数字，楼梯数。

输出格式：

走的方式几种。

## 输入输出样例 ##

输入样例\#1： 复制

输出样例\#1： 复制

## 说明 ##

用递归会太慢，需用递推

（60% N<=50 ,100% N<=5000)

写法一：二维数组

#include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #define Maxn 5003
    int n, len = 1, f[Maxn][Maxn];//数组的第二位代表的应该是这一项的长度
    
    void Fibonacci()
    {
    	for (int i = 3; i <= n; i++)
    	{
    		int j;
    		for (j = 1; j <= len; j++)
    			f[i][j] = f[i - 1][j] + f[i - 2][j];//按位相加
    		for (j = 1; j <= len;j++)
    		if (f[i][j] >= 10)
    		{
    			f[i][j + 1] += f[i][j] / 10;
    			f[i][j] = f[i][j] % 10;
    			if (f[i][len + 1])len++;
    		}
    	}
    }
    
    int main()
    {
    	int i;
    	scanf("%d", &n);
    	if (n < 3)//特判
    	{
    		printf("%d\n", n);
    		return 0;
    	}
    	f[1][1] = 1; f[2][1] = 2;
    	Fibonacci();
    	for (int i = len; i >= 1; i--)
    		printf("%d", f[n][i]);
    	return 0;
    }

写法二：一位数组

参考：[https://www.luogu.org/blog/ljh/ti-xie-p1255-shuo-lou-ti-post][https_www.luogu.org_blog_ljh_ti-xie-p1255-shuo-lou-ti-post]

这就很巧妙了

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    #define Maxn 5010
    int n, ns = 1;
    int a[Maxn], b[Maxn], c[Maxn];
    
    void Fibonacci()
    {
    	a[1] = 1,b[1] = 2;
    	for (int i = 3; i <= n; i++)
    	{
    		for (int j = 1; j <= ns; j++) c[j] = a[j] + b[j];
    		for (int j = 1; j <= ns; j++)
    		{
    			if (c[j] > 9)
    			{
    				c[j + 1] += c[j] / 10;
    				c[j] %= 10;
    				if (j + 1 > ns)ns++;
    			}
    		}
    		//交换
    		for (int j = 1; j <= ns; j++)a[j] = b[j];
    		for (int j = 1; j <= ns; j++)b[j] = c[j];
    	}
    }
    
    int main()
    {
    	memset(a, 0, sizeof(a));
    	memset(b, 0, sizeof(b));
    	memset(c, 0, sizeof(c));
    
    	cin >> n;
    	if (n < 3)
    	{
    		cout << n;
    		return 0;
    	}
    	Fibonacci();//高精和递推合并
    	for(int i=ns;i>0;i--)printf("%d",b[i]);//逆序输出
    	return 0;
    }

[https_www.luogu.org_blog_ljh_ti-xie-p1255-shuo-lou-ti-post]: https://www.luogu.org/blog/ljh/ti-xie-p1255-shuo-lou-ti-post