[算法]机器人走方格

mcard · 发表于 2016-10-30 15:34:57

本帖最后由 mcard 于 2016-10-30 15:41 编辑

问题描述 - 机器人走方格（http://suo.im/x4sqx）：
难度：☆
M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。
Input
第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000)Output
输出走法的数量。
Input示例
2 3
复制代码

Output示例
3
复制代码

涉及知识点：
1、取余数 —— 在易语言中对应“a % b”，例如：“20 % 3 = 6 余 2”
2、枚举算法
3、for循环 —— 在易语言中对应“变量循环”
4、二维数组

思路初涉：
1、为了一般化此问题，我们假设矩形大小为 “a*b”
2<1>、递归方式解题：矩阵中的格子(i, j)，假设从(1, 1)到它的路径数量为path(i, j)
path(i, j) = path(i-1, j) + path(i, j-1)
复制代码

很好理解，因为机器人只能向右或向下运动，因此它只能是从(i-1, j)或(i, j-1)
运动到(i, j)的，所以路径数量也就是到达这两个格子的路径数量之和。然后，
我们需要一个初始条件，也就是递归终止条件，是什么呢？可以发现，
当机器人在第一行时，不论它在第一行哪个位置，从(1, 1)到达那个位置都只有一条路径，
那就是一路向右；同理，当机器人在第一列时，也只有一条路径到达它所在位置。
2<2>、如果用纯数学的方法来解这道题目，大概也就是个高中排列组合简单题吧。
机器人从(1, 1)走到(m, n)一定要向下走m-1次，向右走n-1次，不管这过程中是怎么走的。
因此，一共可能的路径数量就是从总的步数(m-1+n-1)里取出(m-1)步，作为向下走的步子，
剩余的(n-1)步作为向右走的步子。

C(m-1+n-1, m-1)=(m-1+n-1)! / ( (m-1)! * (n-1)! )

复制代码

代码片段（非最优算法）：

子程序名	返回值类型	公开	备注
机器人走方格	整数型
参数名	类型	参考	可空	数组	备注
I1	整数型				>=2
I2	整数型

变量名	类型	静态	数组	备注
arr	整数型		0
i	整数型
j	整数型
time	整数型

time ＝取启动时间 ()
重定义数组 (arr, 假, I1, I2)

变量循环首 (1, I1, 1, i)

arr [i] [1] ＝ 1[/i]
[i].变量循环尾 ()[/i]
[i].变量循环首 (1, I2, 1, i)[/i]
[i] arr [1]  ＝ 1[/i]
[i].变量循环尾 ()[/i]
[i].变量循环首 (2, I1, 1, i)[/i]
[i] .变量循环首 (2, I2, 1, j)[/i]
[i]       arr  [j] ＝ arr [i － 1] [j] ＋ arr  [j － 1][/i]
[i]       arr  [j] ＝ arr  [j] ％ 1000000007[/i]
[i] .变量循环尾 ()[/i]
[i].变量循环尾 ()[/i]
[i]输出调试文本 (“费时：” ＋到文本 (取启动时间 () － time))[/i]
[i]返回 (arr [i － 1] [j － 1])[/i]
[i]

题目变式：
1、M * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。（原链接：http://suo.im/guo5y）难度：★★
2、四个机器人a b c d，在2 * 2的方格里，一开始四个机器人分别站在4个格子上，每一步机器人可以往临近的一个格子移动或留在原地（同一个格子可以有多个机器人停留），经过n步后有多少种不同的走法，使得每个毯子上都有1机器人停留。由于方法数量巨大，输出 Mod 10^9 + 7的结果。（原链接：http://suo.im/l4w0a）难度：★★★

这编辑器好垃圾呀。。。。。老是无故斜体，无故丢链接，无故改字体，无故改大小
我会不定时发几个算法，具体看个人时间和算法难度。
@junkboy

mcard · 发表于 2016-10-30 20:05:17

不知道易代码出问题还是我浏览器解析有问题，反正我看的代码格式不对。。

.版本 2

.子程序机器人走方格, 整数型
.参数 I1, 整数型, , >=2
.参数 I2, 整数型
.局部变量 arr, 整数型, , "0"
.局部变量 i, 整数型
.局部变量 j, 整数型
.局部变量 time, 整数型

time ＝取启动时间 ()
重定义数组 (arr, 假, I1, I2)

.变量循环首 (1, I1, 1, i)
arr [1] ＝ 1
.变量循环尾 ()
.变量循环首 (1, I2, 1, i)
arr [1] ＝ 1
.变量循环尾 ()
.变量循环首 (2, I1, 1, i)
.变量循环首 (2, I2, 1, j)
arr [j] ＝ arr [i － 1] [j] ＋ arr [j － 1]
arr [j] ＝ arr [j] ％ 1000000007
.变量循环尾 ()
.变量循环尾 ()
输出调试文本 (“费时：” ＋到文本 (取启动时间 () － time))
返回 (arr [i － 1] [j － 1])