背景: #EDF0F5 #FAFBE6 #FFF2E2 #FDE6E0 #F3FFE1 #DAFAF3 #EAEAEF 默认  
阅读新闻

[推荐]递推算法的经典例子

[日期:2012-09-12] 来源:信息组  作者:欧亚鹏 [字体: ]

    递推算法是每年noip全国赛考察的重点,也是每个noip参赛选手必须掌握的基本算法。下面这个案例是09级奎光noip复赛培训时一个通过递推的算法得到求解的经典案例.我们的目标不是为了解决这个题目,而是通过这个例子让大家更好的理解递推算法的精髓和原理,在今后的考试中举一反三。(与2012、2013奎光noip学子分享)

 

【案例】从原点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?

样例输入:N=2

样例输出:result=7

 

样例输入:N=3

样例输出:result=17

 

解题思路:要解决走N步共有多少种走法,我们在拿到题目的时候最直接的想法就是先画出当N=1N=2N=3。。。。。N=n时对应走法的图例,由简单到复杂、由特殊到一般的推理过程,找出规律获得解题的思路。在数学上,我们称为归纳法。如果用编程的方法来求解这样的推理题,我们把这样的求解思路(算法)称之为递推法。递推的精髓在于fn)的结果一般由f(n-1)f(n-2)…..f(n-k)的前k次结果推导出来。我们在解决这类递推问题时,难点就是如何从简单而特殊的案例,找到问题的一般规律,写出fn)与f(n-1)f(n-2)…..f(n-k)之间的关系表达式,从而得出求解的结果。在历年noip的复赛当中,参赛选手对于这类题目都有这样的感受,往往花费了大量的时间来分析题目的一般规律,写出fn)的一般表达式,而编程实现可能只需要几分钟的时间。所以我们在平时训练的时候,对于这样的递推题目,就必须掌握如何分析问题,从特殊推导出一般的规律,写出想要的关系表达式,问题就迎刃而解了。下面是这道题解题的心得,供大家参考:

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),实际上转换为如果我们能够得到上一步即fn-1)有多少个终点是有3种走法的,有多少个点有2种走法的,那么问题就解决了。

 

a.       上一步,即fn-1)有多少个终点是有3种走法的。

       对于N=3时,f(n-1)=f(2), 3个点ABC可以走出3种不同走法的,这3个点是怎么得到的呢?它的存在与N值有没有必然的联系?如果我们能找到它与N之间的关系,问题也就解决了。有了这样的思路以后,我们不难找到这样的规律:如果fn-2)存在,即上上步存在,那么从上上步出发的线路里面必然会有一条向上走的线路,而这条向上走的线路在到达fn-1)之后,  fn)出发时也必然有左、上、右这三种走法,那么我们就得出了这样的结论:当fn-2)存在时,fn-2)的值实际上就等价于fn-1)有多少个终点是有3种走法。

         b.    fn-1)有多少个终点是有2种走法的

 对于N=3时,有4个点DEFG可以走出2种不同走法的,这4个点又是怎么得到的呢?它与N值有什么联系呢? 实际上我们在解决了上一个问题的时候,这个问题就变得相当容易了, fn-1)减掉刚才有3种走法的点,剩下的点不就是只有2种走法了吗?即fn-1-fn-2)。


    c.       得出fn)的一般关系式

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;
}




阅读:
录入:admin

推荐 】 【 打印
上一篇:
下一篇:[推荐]记数问题
相关新闻      
本文评论       全部评论
发表评论


点评: 字数
姓名:

  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款