买网站注册人数,广告投放方式,免费自建手机网站,wordpress使用模板【题目来源】 https://www.acwing.com/problem/content/5936/ 【题目描述】 树老师爬楼梯#xff0c;他可以每次走 1 级或者 2 级#xff0c;输入楼梯的级数#xff0c;求不同的走法数。 例如#xff1a;楼梯一共有 3 级#xff0c;他可以每次都走一级#xff0c;或者第…【题目来源】 https://www.acwing.com/problem/content/5936/ 【题目描述】 树老师爬楼梯他可以每次走 1 级或者 2 级输入楼梯的级数求不同的走法数。 例如楼梯一共有 3 级他可以每次都走一级或者第一次走一级第二次走两级也可以第一次走两级第二次走一级一共 3 种方法。 【输入格式】 输入包含若干行每行包含一个正整数 N代表楼梯级数。 【输出格式】 不同的走法数每一行输入对应一行输出。 【数据范围】 单个输入最多包含 30 组数据。 1≤N≤30。 【输入样例】 5 8 10 【输出样例】 8 34 89 【算法分析】 ● 递归https://oi-wiki.org/basic/divide-and-conquer/ 递归的基本思想是某个函数直接或者间接地调用自身这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题而不需要过分关注这个子问题是如何被解决的。 明白递归函数的作用并相信它能完成这个任务千万不要跳进这个函数里面企图探究更多细节 否则就会陷入无穷的细节无法自拔。 ● 递推 递推法recurrence method是一种根据递推关系进行问题求解的方法也是一种重要的数学方法常用来进行序列计算。递推法能够将复杂的运算化解为若干重复的简单运算充分发挥了计算机擅长重复处理的特点。 递推法通过初始条件根据递推关系式按照一定的规律逐项进行计算直至得到结果。递推法有正推和逆推两种形式。无论正推还是逆推关键都是要找到递推关系式。 ● 高精度https://blog.csdn.net/hnjzsyjyj/article/details/144703201 本题中 N≤30问题规模较小可以不用高精度。 但洛谷 P1255https://www.luogu.com.cn/problem/P1255与本题相比除了 N 很大外极其类似且需要用高精度。故用高精度也实现了一下此题。 【算法代码一递归】
#include bits/stdc.h
using namespace std;int f(int x) {if(x0 || x1) return 1;return f(x-1)f(x-2);
}int main() {int n;while(cinn) {coutf(n)endl;}
}
【算法代码二递推】
#include bits/stdc.h
using namespace std;const int maxn35;
int f[maxn];
int n;int main() {f[0]1,f[1]1;for(int i2; imaxn; i) {f[i]f[i-1]f[i-2];}while(cinn) {coutf[n]endl;}
}
【算法代码三高精度】
#include bits/stdc.h
using namespace std;string hiAdd(string a,string b) {string c;int t0;int ia.size()-1,jb.size()-1;while(i0 || j0) {if(i0) t(a[i]-0)t;if(j0) t(b[j]-0);c(t%100);t/10;i--,j--;}if(t!0) c(t0);reverse(c.begin(),c.end());return c;
}int main() {int n;while(cinn){string f[n5];f[0]f[1]1;for(int i2; in; i) {f[i]hiAdd(f[i-1], f[i-2]);}coutf[n]endl;}return 0;
}/*
in:
4out:
5
*/ 【参考文献】 https://www.acwing.com/solution/content/253657/ https://www.acwing.com/solution/content/254309/
