建议大家在浏览这篇文章之前,先来回顾一下昨天的文章。(楼梯问题之递推)
今天要为大家介绍一种更为高效的递推算法。
核心算法
递推,斐波那契数列。
问题描述
爬楼梯问题,每次可以走1步或者2步,爬上n层楼梯的总方法。
递推思路
思考一下这样一个问题,现在一共有5层楼梯每次可以爬1或2层楼梯。那么达到第5层可以从第几层直接爬到呢?答案是第3层或第4层。那么第4层呢,又从2和3层来的;第3层呢,从1层或2层爬上来;至于第2层呢,从地面或1层可以爬到,故答案为2;第一层呢,就只剩下1种方式了。
简单的说第五层5来自于3层和4层,4层来自于2层和3层,以此类推。
于是我们就得到了一个数列1,2,3,5,8。
如果再首项加上1变成:1,1,2,3,5,8。我们就得到了斐波那契数列。正好我们可以把首项下标设为0,于是第i项就是爬到i层楼梯的方案了。
递推图解
代码
#include<cstdio>
long long a[5005],n;
int main() {
scanf('%lld',&n);
a[0] = 1;
a[1] = 1;
for(int i = 2; i <= n; i++) {
a[i] = a[i-1]+a[i-2];
}
printf('%lld\n',a[n]);
return 0;
}
分析
代码
#include<cstdio>
#include<algorithm>
#define MAX 5005
using namespace std;
int n;
struct big_int {
int num[MAX];
int len;
big_int() {
for(int i = 0; i < MAX; i++) {
num[i] = 0;
}
len = 0;
}
void clear() {
for(int i = 0; i < MAX; i++) {
num[i] = 0;
}
len = 0;
}
}a,b,c;
void evaluation(big_int x,big_int &y) {
y.len = x.len;
for(int i = 0; i <= x.len; i++) {
y.num[i] = x.num[i];
}
return;
}
void out(big_int x) {
for(int i = c.len; i >= 0; i--) {
putchar(x.num[i]+'0');
}
putchar('\n');
return;
}
int main() {
scanf('%d',&n);
if(n == 0) {
puts('0');
return 0;
}
a.num[0] = 1;
b.num[0] = 1;
for(int i = 2; i <= n; i++) {
c.clear();
c.len = max(a.len,b.len);
for(int i = 0; i <= c.len; i++) {
c.num[i] += a.num[i]+b.num[i];
if(c.num[i] > 9) {
c.num[i+1] = c.num[i]/10;
c.num[i] = c.num[i]%10;
}
}
while(c.num[c.len+1] > 0) {
c.len++;
}
evaluation(a,b);
evaluation(c,a);
}
out(a);
return 0;
}
例题推荐
【洛谷 P1255】https://www.luogu.org/problemnew/lists?name=1255
楼梯问题进阶
不光要知道爬楼梯问题应该怎么写代码,更应该理解这其中的递推思想,类似的我们可以推出每次可以爬1,2,3层的递推公式等等。这样才是真正的理解算法而不是简单的背诵了。
联系客服