编程解数学题——从A到B，有多少种最短走法？

4×3网格，从左下角A点到右上角B点，每次只能向上或者向右走一步，不重复的最短路径有多少条？（如图所示）

中学的同学，可以使用排列组合来完成这道题，我们考察下图，

通过对上图的观察，我们不难发现，最短的走法, 都由七步组成，其中向上走了三次，向右走了四次，从而得出，其总数是：

也可以通过Maxima 得出

load(functs);

combination(7,3);

35

作为练习，请同学读懂下面两个计算组合的程序，并写出相应的公式。

使用递归的实现

(define (combination m n )

(if (= n 0 )

1

(* m (/ n) (combination (- m 1 ) (- n 1 )))))

(combination 7 3 );;

35

使用迭代的实现

(define (combination m n p)

(if (= n 0 )

p

(combination (- m 1 ) (- n 1 ) (* p m (/ n )))))

(combination 7 3 1);;

35

小学同学可能还没学过排列组合，通常会用一种标格子的办法来解决。到某一个点的走法总数实际上是到它的左边相邻点的走法总数，与到它的下边相邻点的走法总数之和，另外到边界上的各点走法总数都是 1。

具体请看下面这个图：

实际上，这样的思路在编程时非常有用,可以通过递归不断减小问题的规模，最终求出答案。根据上面的思路我们可以写出下面的递归公式：

根据上面的递归公式，我们进一步得到这样的Scheme代码

(define (f x y )

(cond

( (= x 0) 1)

( (= y 0) 1)

(else (+ (f (- x 1) y) (f x (- y 1))))))

(f 4 3);;

35

学习Python的同学，可以得出这样的代码。

def f(x ,y) :

if x == 0 or y == 0 :

return 1

else :

return f(x-1, y) + f(x, y-1)

f(4,3);;

35

以上代码的程序的执行过程，可以用下面的树形图表示出来：

为了简明起见，上图求的是 f(3,2) , 也就 10。同学们可以注意到树形图的叶子结点数，即是计算的结果 10。

此外，使用程序，我们很容易列举其中所有的走法。

其基本思想是，到某处的所有走法，可以用如下方法获得：

1.在其左边的格子的所有走法的后面加上一个'右

2.在其下边的格子的所有走法的后面加上一个'上

3.将1. 2.的结果合并起来

Scheme代码如下：

(define (f x y )

(if (and (= x 0 ) (= y 0 ))

'(())

(append

(if (> x 0 ) (map (lambda (v) (append v '(右) )) (f (- x 1 ) y)) '())

(if (> y 0 ) (map (lambda (v) (append v '(上) )) (f x (- y 1) )) '()))))

(for-each displayln (f 4 3 ))

(上 上 上 右 右 右 右)

(上 上 右 上 右 右 右)

(上 右 上 上 右 右 右)

(右 上 上 上 右 右 右)

(上 上 右 右 上 右 右)

(上 右 上 右 上 右 右)

(右 上 上 右 上 右 右)

(上 右 右 上 上 右 右)

(右 上 右 上 上 右 右)

(右 右 上 上 上 右 右)

(上 上 右 右 右 上 右)

(上 右 上 右 右 上 右)

(右 上 上 右 右 上 右)

(上 右 右 上 右 上 右)

(右 上 右 上 右 上 右)

(右 右 上 上 右 上 右)

(上 右 右 右 上 上 右)

(右 上 右 右 上 上 右)

(右 右 上 右 上 上 右)

(右 右 右 上 上 上 右)

(上 上 右 右 右 右 上)

(上 右 上 右 右 右 上)

(右 上 上 右 右 右 上)

(上 右 右 上 右 右 上)

(右 上 右 上 右 右 上)

(右 右 上 上 右 右 上)

(上 右 右 右 上 右 上)

(右 上 右 右 上 右 上)

(右 右 上 右 上 右 上)

(右 右 右 上 上 右 上)

(上 右 右 右 右 上 上)

(右 上 右 右 右 上 上)

(右 右 上 右 右 上 上)

(右 右 右 上 右 上 上)

(右 右 右 右 上 上 上)

学习Python的同学可以这样写：

def f(x,y) :

if x == 0 and y==0 :

return [[]]

else :

r = []

if x > 0 : r += [v + ['右'] for vin f( x-1 , y )]

if y > 0 : r += [v + ['上'] for vin f( x , y-1 )]

return r

for v in f(4,3):

print(v)

['上', '上', '上', '右', '右', '右', '右']

['上', '上', '右', '上', '右', '右', '右']

['上', '右', '上', '上', '右', '右', '右']

['右', '上', '上', '上', '右', '右', '右']

['上', '上', '右', '右', '上', '右', '右']

['上', '右', '上', '右', '上', '右', '右']

['右', '上', '上', '右', '上', '右', '右']

['上', '右', '右', '上', '上', '右', '右']

['右', '上', '右', '上', '上', '右', '右']

['右', '右', '上', '上', '上', '右', '右']

['上', '上', '右', '右', '右', '上', '右']

['上', '右', '上', '右', '右', '上', '右']

['右', '上', '上', '右', '右', '上', '右']

['上', '右', '右', '上', '右', '上', '右']

['右', '上', '右', '上', '右', '上', '右']

['右', '右', '上', '上', '右', '上', '右']

['上', '右', '右', '右', '上', '上', '右']

['右', '上', '右', '右', '上', '上', '右']

['右', '右', '上', '右', '上', '上', '右']

['右', '右', '右', '上', '上', '上', '右']

['上', '上', '右', '右', '右', '右', '上']

['上', '右', '上', '右', '右', '右', '上']

['右', '上', '上', '右', '右', '右', '上']

['上', '右', '右', '上', '右', '右', '上']

['右', '上', '右', '上', '右', '右', '上']

['右', '右', '上', '上', '右', '右', '上']

['上', '右', '右', '右', '上', '右', '上']

['右', '上', '右', '右', '上', '右', '上']

['右', '右', '上', '右', '上', '右', '上']

['右', '右', '右', '上', '上', '右', '上']

['上', '右', '右', '右', '右', '上', '上']

['右', '上', '右', '右', '右', '上', '上']

['右', '右', '上', '右', '右', '上', '上']

['右', '右', '右', '上', '右', '上', '上']

['右', '右', '右', '右', '上', '上', '上']

细心的同学，可能会发现，计算步数的公式和杨辉三角形的公式是一样的。还没看出来的同学，可以参考一下下面这个图哦。