跳跃游戏

来自计算思维百科
跳转至: 导航搜索
跳跃游戏1.jpg

在5×5大小的棋盘中,每个格子都标有1到9当中的一个整数。游戏规则是,从棋盘的最左上角出发,最终到达最右下角。此过程中,按照方格中的数值大小向下或向右移动相应的方格数,但不能走出棋盘。要怎么样找到从左上角到右下角的这条路线呢?

 2 

5

1

6

6

1

1

2

7

2

3

2

1

1

3

 1 

解决方案

方案一-蛮力法

从左上角开始,对于每一格,接下来的走法都只有向右和向左两种,将所有可能的路线都走一遍,最终能够找出能够到达右下角的路线:

跳跃游戏2.png

我们用jump(x,y)表示从(x,y)起始能否到达终点,jumpsize表示(x,y)位置的方格中的数值,那么:运用的计算思维

方案一运用了蛮力法寻找跳跃游戏的通关路线,在没有更好的解决方法时,蛮力法是一种直观简洁的方式,通过蛮力法可以发现解决问题的思路,这是一种机械化的思维方式。

方案二-动态规划法

jump(x,y)=jump(x+jumpsize,y)|| jump(x,y+jumpsize)(x=0,1,2,3;y=0,1,2,3)。

因为从(x,y)出发,下一个点不是(x+jumpsize,y)就是(x,y+jumpsize),所以如果从下一个点出发能够到达终点,那么从初始点出发也一定能到达终点。这样,我们就把求解问题的递推关系式找到,并且该递推关系中包含了相同类型的更小的子问题的解。

例如从(0,0)起始能否达到终点取决于从(2,0)能否到达终点或者从(0,2)能否到达终点。

 2 

5

 1 

6

6

1

1

2

 7 

2

3

2

1

1

3

 1 

根据这个思路,我们可以画出如下所示的树状图,黄色的线路是可行线路:

跳跃游戏3.png

运用的计算思维

方案二利用动态规划的方法,通过分解将该问题变换为子问题集合,子问题可解,从而使原问题可解,这运用的是规约的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015