做的网站百度找不到了,超级优化残剑,合肥 网站建设公司哪家好,网站数据库是什么意思目录
递推的概念
训练#xff1a;斐波那契数列
解析
参考代码
训练#xff1a;上台阶
参考代码
训练#xff1a;信封
解析
参考代码
递推的概念
递推是一种处理问题的重要方法。
递推通过对问题的分析#xff0c;找到问题相邻项之间的关系#xff08;递推式斐波那契数列
解析
参考代码
训练上台阶
参考代码
训练信封
解析
参考代码
递推的概念
递推是一种处理问题的重要方法。
递推通过对问题的分析找到问题相邻项之间的关系递推式从起点出发首项或者末项然后使用循环不断地迭代得到最后需要的结果。
训练斐波那契数列
对于Fibonacci数列已知fib(1) 1 fib(2) 1; 从第三项开始满足公式fib(i) fib(i-1) fib(i-2)。输入一个整数n1n100求fib(n)的值。
【输入描述】一行一个整数n。
【输出描述】一行feibonacci数列第n项的值
【样例输入】5
【样例输出】5
解析
1.问题求的是斐波那契数列第i项的数值。
2.前两项的数值题目中已经给出分别为
fib(1) 1; fib(2) 1;3.从第3项开始满足如下规律
fib(i) fib(i-1) fib(i-2);即当前项由前两项之和构成。
4.我们可以根据题目给出的fib(1)、fib(2)推出fib(3),
再按照顺序由fib(2)、fib(3)推出fib(4)以此类推。
参考代码
#includebits/stdc.h
using namespace std;
int main()
{long long n,f1,f2,f3;cinn;f1f2f31;//初始化,f3表示第n项for(long long i3;in;i){f3f1f2;f1f2;f2f3;}coutf3;return 0;
}
训练上台阶
楼梯有n(1n100)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶编程计算共有多少种不同的走法。
【输入描述】输入的每一行包括一组测试数据即为台阶数n。最后一行为0表示测试结束。
【输出描述】每一行输出对应一行输入的结果即为走法的数目。
【样例输入】
1
2
3
4
0【样例输出】
1
2
4
7参考代码
#includebits/stdc.h
using namespace std;
long long a[105];
//a[i]表示i层楼梯方案数
int main()
{int n,t;a[1]1,a[2]2,a[3]4;//边界条件while(1){cint;if(!t) break;if(a[t]){ //如果已经计算过直接输出couta[t]endl;continue;}for(int i4;it;i)a[i]a[i-1]a[i-2]a[i-3];//从第4层楼梯开始//每一步有3种方案1阶、2阶、3阶//分别对应 a[i-1]、a[i-2]、a[i-3]couta[t]endl;}return 0;
}训练信封
现在有n封信和n个信封如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
【输入描述】1行输入一个整数n。
【输出描述】1行输出一个整数表示所有的情况数。
【样例输入】4
【样例输出】9
解析
先任取一封信此时可供选择的信封有n-1种情况。
每种情况下我们在放置这封信的时候有2种方案
这封信的位置不与剩余的任意一封信互换此时剩余的问题就是将n-1封信错放在n-1个信封里即f(n-1)这封信的位置与剩余的任意一封信互换此时会有2个信封被使用掉。剩余的问题就是将n-2封信,错放在n-2个信封里即f(n-2)得出递推式f(n)(n-1)*(f(n-1)f(n-2))。边界是f(1)0,f(2)1。
参考代码
#includebits/stdc.h
using namespace std;
long long f[25];
int main()
{int n;cinn;f[1]0,f[2]1;for(int i3;in;i){f[i](i-1)*(f[i-1]f[i-2]);}coutf[n];return 0;
} 从入门到算法再到数据结构查看全部文章请点击此处http://www.bigbigli.com/
