首页 > itarticle > 商人过河问题的python递归解法

商人过河问题的python递归解法

admin 11月 11, 2020 0

最近上课老师提到商人过河这个经典的智力问题，留给我们作课后作业。直觉告诉我直接用python岂不是分分钟的事，于是就直接用python递归开始实现。由于深受C的影响，中途发现python递归比起C语言递归实现起来差别不小。趁热打铁，这里就把求解过程记录下来。

目录

问题描述

三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任意一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢？

求解思路

首先需要把这个问题用数学语言表示出来。商人与随从过河的过程，就是两岸人数状态不断变化的一个过程。我们可以用坐标(商人，随从)来表示源河岸当前的人数状态。
初始状态，设源河岸商人和随从均为N人，表示为：

1
 
start_point = [N,N]

中间过程，船往返于两岸之间一次，两岸的人数变化一次。这个步骤中的每一次往返都涉及到两个因素，一是船的方向direct，二是对该次上船人员的决策decision。当船的方向是从源河岸驶向对面目的地时，可以表示为：

1
2
 
derict = 1   # at source river bank
src_decision = [[-2,0], [-1,0], [-1,-1], [0,-1], [0,-2]]

当船返回源河岸时：

1
2
 
derict = -1     # at dst river bank 
dst_decision = [[1,0], [2,0], [1,1], [0,1],[0,2]]

成功渡河后，源河岸随从和商人均为0人。

1
 
END = [0, 0]        # destation point

递归搜索

船往返于两岸之间，岸上人数的变化对应与坐标上的一个个点。需要把已经到达过状态记录下来，防止后面再次重复已经搜索过的路线：

1
2
 
src_reached_list = []
dst_reached_list = []

已经搜索过的状态以参数的形式传入递归搜索。此外，还需要传入的参数有当前状态下源岸边的人数，当前方向以及该方向对应的可行的决策。递归代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# return 0: success
    #        1: not found
    #        2: error
def (start_p, derict, src_reached, dst_reached):
    s_reached = copy.deepcopy(src_reached)
    d_reached = copy.deepcopy(dst_reached)

    if derict == 1:
        if start_p not in s_reached:
            s_reached.append(start_p)

        for decison in src_decision:
            point = []
            for i in xrange(2):
                point.append(start_p[i]+decison[i])
            if point == END:
                print "It succesed !!"
                result_path.append(s_reached)
                result_path.append(d_reached)
                return 0
            elif (point in restrict_point_list) and (point not in d_reached):
                SearchCrossRiver(point, -1, s_reached, d_reached)
            else:
                pass
        return 1

    elif derict == -1:
        if start_p not in d_reached:            
            d_reached.append(start_p)

        for decison in dst_decision:
            point = []
            for i in xrange(2):
                point.append(start_p[i] + decison[i])
            if point == END:
                result_path.append(s_reached)
                result_path.append(d_reached)
                return 0
            elif (point in restrict_point_list) and (point not in s_reached):
                SearchCrossRiver(point, 1, s_reached, d_reached)
            else:
                pass
        return 1
    else:
        print "error"
        return 2

求解结果

可以得到四组结果。每组结果由source reached point序列和dst reached point序列构成。

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 [
 [[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [1, 1]],
  [[2, 2], [3, 0], [1, 1], [0, 2], [0, 1]],

  [[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [0, 2]],
  [[2, 2], [3, 0], [1, 1], [0, 2], [0, 1]],

  [[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [1, 1]],
  [[3, 1], [3, 0], [1, 1], [0, 2], [0, 1]],

  [[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [0, 2]],
  [[3, 1], [3, 0], [1, 1], [0, 2], [0, 1]]
]

附上源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
import os
import sys
import copy

N = 3               # Total people number
END = [0, 0]        # destation point

    # goble decison 
src_decision = [[-2,0], [-1,0], [-1,-1], [0,-1], [0,-2]]
dst_decision = [[1,0], [2,0], [1,1], [0,1],[0,2]]

    # global AVAIABLE point 
restrict_point_list = []

    # global list to record suceess path
result_path = []

def init_restrict_point():
    for y in range(0,N+1):
        a = [0,y]
        restrict_point_list.append(a)
    for x in range(1,N):
        a = [x,x]
        restrict_point_list.append(a)
    for y in range(0,N+1):
        a = [N,y]
        restrict_point_list.append(a)

    # return 0: success
    #        1: not found
    #        2: error
def (start_p, derict, src_reached, dst_reached):
    s_reached = copy.deepcopy(src_reached)
    d_reached = copy.deepcopy(dst_reached)

    if derict == 1:
        if start_p not in s_reached:
            s_reached.append(start_p)

        for decison in src_decision:
            point = []
            for i in xrange(2):
                point.append(start_p[i]+decison[i])
            if point == END:
                print "It succesed !!"
                result_path.append(s_reached)
                result_path.append(d_reached)
                return 0
            elif (point in restrict_point_list) and (point not in d_reached):
                SearchCrossRiver(point, -1, s_reached, d_reached)
            else:
                pass
        return 1

    elif derict == -1:
        if start_p not in d_reached:            
            d_reached.append(start_p)

        for decison in dst_decision:
            point = []
            for i in xrange(2):
                point.append(start_p[i] + decison[i])
            if point == END:
                result_path.append(s_reached)
                result_path.append(d_reached)
                return 0
            elif (point in restrict_point_list) and (point not in s_reached):
                SearchCrossRiver(point, 1, s_reached, d_reached)
            else:
                pass
        return 1
    else:
        print "error"
        return 2

def find_function():
    start_point = [N,N]     
    init_restrict_point()

    src_reached_list = []
    dst_reached_list = []

    result = SearchCrossRiver(start_point, 1, src_reached_list, dst_reached_list)
    print "result = ", result_path
    print 'n'

if __name__ == '__main__':
    find_function()
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能