递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法。
这种算法特点是:一个问题的求解需一系列的计算,在已知条件和所求问题之间总存在着某种相互联系的关系,在计算时,如果可以找到前后过程之间的数量关系(即递推式),那么,从问题出发逐步推到已知条件,此种方法叫逆推。
无论顺推还是逆推,其关键是要找到递推式。
这种处理问题的方法能使复杂运算化为若干步重复的简单运算,充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系(即递推关系)。递推算法避开了求通项公式的麻烦,把一个复杂的问题的求解,分解成了连续的若干步简单运算。一般说来,可以将递推算法看成是一种特殊的迭代算法。
例一:Fibonacci数列
已知有一个数列1,1,2,3……,满足前两项为1,后面每一项等于前两项之和,求出第n项。(n<=1000)
输入样例:6 输出样例:8
1 1 2 3 5 8
分析,本题递推式可以从题面中轻易得到:F[n]=F[n-1]+F[n-2];
故只需从3循环到n,依次递推求F[i]就可以了。
标程:
include[HTML_REMOVED]
using namespace std;
const int N=1009;
int f[N]={0,1,1};
int main(){
int n;
cin>>n;
for(int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];//递推关系式
}
cout<<f[n];
return 0;
}
例二:Hanoi塔问题
Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图3-11所示。
要求把a柱上n个圆盘按下述规则移到c柱上:
(1)一次只能移一个圆盘;
(2)圆盘只能在三个柱上存放;
(3)在移动过程中,不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上,总计需要移动多少次?
标程:
include[HTML_REMOVED]
using namespace std;
const int N=1009;
int f[N]={0,1};
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
f[i]=2f[i-1]+1;//递推关系式
}
cout<<f[n];
return 0;
}
练习(可发在评论区,下篇文章会给出标程):
跳级:小明共有n个年级要读,每一次他可以向上升1级,升2级或者升3级,请问共有多少种不同的升级方法。例如n=3时共有四种升级方法:可以先升1级再升2级,或者先升2级再升1级,或者每次都升1级,或者直接升3级。请问共有多少种升级方法可以正好走完n级。
输入输出格式
输入格式
输入文件level.in 输入一个正整数n(n<=50)
输出格式
输出文件level.out 输出一个正整数。
输入输出样例
输入样例#1:
3
输出样例#1:
4
输入样例#2:
4
输出样例#2:
7
贴代码呀,你这样看起来很难受的
你说的是哪个?
文章里的还是评论区的
文章和评论都可以贴代码的,
请大家将工具箱的名字改成bits/stdc++.h(评论区的代码),这个ACwing没法打工具箱,以后都一样
#include[HTML_REMOVED]
using namespace std;
const int N=1009;
int f[N]={0,1};
int main(){
freopen(____)
freopen(___)
int n;
cin>>n;
for(int i=2;i<=n;i++){
_//递推关系式
}
cout<<f[n];
return 0;
}
其实可以用别的颜色的
好,下次尽量
这个不能改吗
我没找到改颜色
抱歉没给你讲清楚,我的意思和他们一样哈,不过我想说这个不是可以原地修改吗
是的,我那条评论是说下次不改,直接就是你们想要的样子
麻烦你啦
没事,反正是第一次做