C++（递推算法）

学习目标递推思想递推算法的应用高级编程语言根据程序的执行方式,高级编程语言可以分为编译型语言和解释型语言。编译型语言如C、C++需要通过编译器将源代码一次性编译成机器代码,执行效率高但通常只能在特定的操作系统和硬件平台上运行。解释型语言如Python则通过解释器逐行解释执行源代码,灵活性高但执行效率相对较低。递推算法● 递推就是“根据已有信息推出未知信息”● 从已知条件出发,依据递推关系,依次推出所求问题的中间结果和目标结果● 是人类常用的思考方式,比较直观,符合直觉● 递推算法就是用程序模拟人类用递推方法解决问题的过程● 递推算法的关键是找到初始条件和递推公式斐波那契数列斐波那契数列(Fibonacci)的第一个和第二个数都为1,接下来每个数都等于前面2个数之和,即:f(n)=f(n-1)+f(n-2)。问,第20个数是多少?最基础的递推题,我们只需要用一个f[]数组,初始化好f[1]和f[2],然后按照给定的公式循环计算就可以了。斐波那契数列的递推算法longlongf[25];intmain(){f[1]=f[2]=1;//初始条件for(inti=3;i=20;i++)f[i]=f[i-1]+f[i-2];//递推公式coutf[20];递推问题问题描述中明确给出初始条件和递推关系:按照递推关系依次进行计算即可问题描述中没有给出初始条件和递推关系:●想办法找出递推公式和初始条件● 再写代码爬楼梯上楼可以一步上一阶,也可以一步上二阶,20阶的楼梯共有多少种不同的走法?（递推关系未知,需要分析）用f[i]表示i阶楼梯的爬楼方案数● 1阶楼梯 只有1种走法 f[1]=1● 2阶楼梯 有2种走法 f[2]=2● 3阶楼梯最后一步有两种走法:①从2-3之前的2阶,有2种走法,所以这种情况有2种走法②从1-3之前的1阶,有1种走法,所以这种情况有1种走法总共有3种走法:f[3]=3递推分析中常用的分类讨论法上楼可以一步上一阶,也可以一步上二阶,20阶的楼梯共有多少种不同的走法?举一反三,i阶的楼梯的走法,继续用分类讨论法!最后一步也只有两种走法:●要么是从第i-1阶跨上来 f[i-1]●要么是从i-2阶跨上来 f[i-2]f[i]=f[i-1]+f[i-2] 递推公式初始条件f[1]=1f[2] = 2知道最初的两项就可以推到出后面的所有项。斐波那契数列的一种变形。longlongf[25];intmain(){//初始条件f[1]=1;f[2]=2;for(inti=3;i=20;i++)f[i]=f[i-1]+f[i-2];//递推公式coutf[20];//最终结果}由第1、2项开始,逐步依次求出第3~第n项● 递推算法一般离不开循环● 在循环的过程中使用数组或临时变量记录下来每一步递推的过程和结果● 当某个问题能确定初始条件,能找出递推公式,就可以考虑使用递推算法● 递推分为顺推和逆推两种●顺推法是从已知条件出发,逐步推算出要解决的问题的方法● 例如,求斐波那契数列第n项,由第1、2项开始,逐步依次求出第3~第n项,这就是顺推过程● 逆推法从已知结果出发,用迭代表达式逐步推算出问题的开始的条件,即顺推法的逆过程,称为逆推猴子吃桃-逆推法一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半,又贪嘴多吃了一个;接下来的每一天它都会吃剩余的桃子的一半外加一个。第4天早上起来一看,只剩下1个桃子了。请问小猴买了几个桃子?(第i天的数量是i-1天数量的一半还少1个)第n天剩1个桃子,问最初有多少个桃子?(1 = n = 20)#includeiostreamusingnamespacestd;intf[25]={0};//初始化f数组为全0;intmain(){