跳至正文
View Categories

1 min read

主要内容 #

  1. 问题介绍
  2. 求解方法
  3. 编程计算

1. 问题介绍 #

从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
样例输入：N=2
样例输出：result=7
样例输入：N=3
样例输出：result=17

2. 求解方法 #

解题思路：要解决走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)之间的关系表达式，从而得出求解的结果。
(1) 当N=1时，绘出走法图

共有3种不同的走法，也就是黑色线条的数量，即f(1)=3
(2) 当N=2时，绘出走法图

共有7种不同的走法，也就是绿色线条的数量，即f(2)=7
(3) 当N=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)

3. 编程计算 #

#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;    
}
What are your Feelings