编程解数学题——从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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180113G0C4U300?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券