递推算法
给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来,这样的式子就叫做递推关系。
递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。 递推算法分为顺推和逆推两种。
相对于递归算法,递推算法免除了数据进出栈的过程,也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值. 比如阶乘函数:f(n)=n*f(n-1) 在f(3)的运算过程中,递归的数据流动过程如下: f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6} 而递推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意。
顺推法
所谓顺推法是从已知条件出发,逐步推算出要解决的问题的方法叫顺推。 如斐波拉契数列,设它的函数为f(n),已知f(1)=1,f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。
逆推法
所谓逆推法从已知问题的结果出发,用迭代表达式逐步推算出问题的开始的条件,即顺推法的逆过程,称为逆推。
递推算法的经典例子
【案例】从原点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?
样例输入:N=2
样例输出:result=7
样例输入:N=3
样例输出:result=17
解题思路:要解决走N步共有多少种走法,我们在拿到题目的时候最直接的想法就是先画出当N=1、N=2、N=3。。。。。N=n时对应走法的图例,由简单到复杂、由特殊到一般的推理过程,找出规律获得解题的思路。在数学上,我们称为归纳法。如果用编程的方法来求解这样的推理题,我们把这样的求解思路(算法)称之为递推法。递推的精髓在于f(n)的结果一般由f(n-1)、f(n-2)…..f(n-k)的前k次结果推导出来。我们在解决这类递推问题时,难点就是如何从简单而特殊的案例,找到问题的一般规律,写出f(n)与f(n-1)、f(n-2)…..f(n-k)之间的关系表达式,从而得出求解的结果。在历年noip的复赛当中,参赛选手对于这类题目都有这样的感受,往往花费了大量的时间来分析题目的一般规律,写出f(n)的一般表达式,而编程实现可能只需要几分钟的时间。所以我们在平时训练的时候,对于这样的递推题目,就必须掌握如何分析问题,从特殊推导出一般的规律,写出想要的关系表达式,问题就迎刃而解了。下面是这道题解题的心得,供大家参考:
(1)当N=1时,绘出走法图
(图1)共有3种不同的走法,也就是黑色线条的数量,即f(1)=3
(2)当N=2时,绘出走法图
(图2)共有7种不同的走法,也就是绿色线条的数量,即f(2)=7
(3)当N=3时,绘出走法图
(图3)共有17种不同的走法,也就是红色线条的数量,即f(3)=17
由此,我们不难看出,对于任何一个起点,最多可以走出3种走法,但最少必须走出2种走法。那么我们要求出f(n),实际上转换为如果我们能够得到上一步即f(n-1)有多少个终点是有3种走法的,有多少个点有2种走法的,那么问题就解决了。
a. 上一步,即f(n-1)有多少个终点是有3种走法的。
对于N=3时,f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的,这3个点是怎么得到的呢?它的存在与N值有没有必然的联系?如果我们能找到它与N之间的关系,问题也就解决了。有了这样的思路以后,我们不难找到这样的规律:如果f(n-2)存在,即上上步存在,那么从上上步出发的线路里面必然会有一条向上走的线路,而这条向上走的线路在到达f(n-1)之后, 向f(n)出发时也必然有左、上、右这三种走法,那么我们就得出了这样的结论:当f(n-2)存在时,f(n-2)的值实际上就等价于f(n-1)有多少个终点是有3种走法。
b. f(n-1)有多少个终点是有2种走法的
对于N=3时,有4个点D、E、F、G可以走出2种不同走法的,这4个点又是怎么得到的呢?它与N值有什么联系呢? 实际上我们在解决了上一个问题的时候,这个问题就变得相当容易了, f(n-1)减掉刚才有3种走法的点,剩下的点不就是只有2种走法了吗?即f(n-1)-f(n-2)。
c. 得出f(n)的一般关系式
f(n)=3*f(n-2)+2*(f(n-1)-f(n-2) ) (n>=3)
化简:
f(n)=2*f(n-1)+f(n-2) (n>=3)
有一点需要补充的就是,任何递推题,都会有临界条件。当N=1时,f(n)=3;,当N=2时,f(n)=7,这些都可以看成是临界条件。只有当N>=3时,即上上步存在的情况下,就可以得出f(n)的一般通式:f(n)=2*f(n-1)+f(n-2)
(本题还有其他的解法,同学们可以继续挖掘!)
【参考程序】
#include <stdio.h>
#include <windows.h>
int main()
{ int n; int i; int fn_1,fn_2; printf("please input n="); scanf("%d",&n); //输入任意n值 int fn=0; if(n==1) fn=3; //初始化当n=1和n=2时的临界条件 else if(n==2) fn=7; else{ fn_1=7; fn_2=3; for(i=3;i<=n;i++) { fn=2*fn_1+fn_2; //当n>=3时fn的通式 fn_2=fn_1;//更新fn_1和fn_2的值 fn_1=fn; } } printf("一共有%d种走法!\n",fn); //输出结果 return 0;
}
复制
java递归算法分析
递归算法分析:就是把复杂的问题分解为若干个相对简单的子问题,一直分解下去,直到子问题有答案为止,也就是说到了递推的出口。 递归算法要注意的两点: (1) 递归就是在方法里调用自己; (2) 在使用递归算法时,必须要有一个明确的递归结束条件,称为递归出口。 先看一个简单的例子,求从1加到5的和,代码如下:
package com.juziku;/**
* 递归测试
* @author sunlightcs
* 2011-3-9
* http://hi.juziku.com/sunlightcs/
*/
public class RecursionTest {/*** 求从1加到n的和*/public static int sum(int n){if(n == 1){return 1;}else{return n + sum(n-1);}}public static void main(String[] args) {System.out.println(sum(5));}
}
复制
先分析一下执行的流程: n=5时,执行sum(5)方法,返回的结果为:5 + sum(4) n=4时,执行sum(4)方法,返回的结果为:4 + sum(3) n=3时,执行sum(3)方法,返回的结果为:3 + sum(2) n=2时,执行sum(2)方法,返回的结果为:2 + sum(1) n=1时,执行sum(1)方法,返回的结果为:1 再向上返回,依次执行: 2+1 3+(2+1) 4+(3+2+1) 5+(4+3+2+1) = 15 思路应该是这样的: 要知道从1加到5的和,先得知道从1加到4的和,即:5+sum(4) 要知道从1加到4的和,先得知道从1加到3的和,即:4+sum(3) 要知道从1加到3的和,先得知道从1加到2的和,即:3+sum(2) 要知道从1加到2的和,先得知道从1加到1的和,即:2+sum(1) 从而很容易看出,递归的出口为1也就是sum(1)的值为1 再看一个例子,求5的阶乘,代码如下:
package com.juziku;/**
* 递归测试
* @author sunlightcs
* 2011-3-8
* http://hi.juziku.com/sunlightcs/
*/
public class RecursionTest {/*** 求n的阶乘*/public static int multiply(int n) {if(n == 1){return 1;}else{return n * multiply(n - 1);}}public static void main(String[] args) {System.out.println(multiply(5));}
}
复制