Python思考练习题2_三个水桶等分8升水问题（已公开答案）

大头目

玩法申明（借鉴每日一题）：

1. 楼主看情况提供答案（有可能是自己做不出，但觉得很好的题目）
2. 请大家先独立思考，再参考其他鱼油的解答，这样才有助于自己编程水平的提高。开始阶段是看不到其他人的回帖的，等答题完成，过几天后取消限制。
3. 鼓励大家积极答题，但楼主囊肿羞涩大部分情况无法奖励大家，除非遇到楼主非常想知道答案的题目或者代码写得很好且有说明注释的答案。
4. 纯属娱乐，大家如果希望知道题目出处的可以私聊我，互相推荐好书，交流看书心得。

题目：
有三个容积分别是3升、5升、8升的水桶，其中容积为8升的水桶中装满了水，容积为3升和5升的水桶中是空的。
三个水桶都没有体积刻度，现在需要将水桶中的8升水等分成两份，每份都是4升水，条件是只能使用另外两个空桶，不能借用其他辅助容器。
求一共由多少种方法
PS：本题实现对于新手来说太困难了，三天后公布答案，供学习参考

附加要求：
需要记录倒水流程

提示：
题目是个经典的简单问题，人脑算很简单，通过倒水凑出1升水空间就行。但是用计算机求解的话就要利用经典的状态转移和穷举搜索算法。
1，不能向自身倒水
2，倒出水的桶不能为空桶
3，接收水的桶不能为满桶
4，避免进入死循环

grf1973

1. import itertools
   
2. state0 = [0,0,8]   #水桶的初始状态
   
3. state1=[0,4,4]   #水桶最终状态
   
4. maxv = [3,5,8]    #每个水桶的对应的容积
   
5. allowed=list(itertools.permutations(range(3),2))   #1-->2,2-->1,1-->3,3-->1,2-->3,3-->2共6种可能
   
6. def nextstate(state0):    #对于状态state0，推出所有可能的下一状态   
   
7.     for i,j in allowed:
   
8.         a,b=state0[i],state0[j]   # a-->b
   
9.         if a>0 and b<maxv[j]:
   
10.                 nxtState = list(state0)
    
11.                 if a + b > maxv[j]:     #部分倒入:a=a-(maxb-b)
    
12.                     nxtState[i] -= (maxv[j] - b)
    
13.                     nxtState[j] = maxv[j]
    
14.                 else:          #a全部倒入b
    
15.                     nxtState[i] = 0
    
16.                     nxtState[j] = a+b
    
17.                 yield nxtState
    
18. 
    
19. n=0
    
20. def findway(ways):        
    
21.         global n  #多少种方法       
    
22.         for state in nextstate(ways[-1]):        #遍历下一状态（ways[-1]表示最后一个状态）
    
23.                 if state not in ways:         #当前状态未出现过。
    
24.                         ways.append(state)    #添加新结果
    
25.                         if state == state1:   
    
26.                                 n+=1
    
27.                                 print('第%d种，共%d步：' %(n,len(ways)),ways)    #输出结果
    
28.                         else:
    
29.                                 findway(ways)  #递归搜索
    
30.                         ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）
    
31. 
    
32. findway([state0])

复制代码

第1种，共12步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第2种，共9步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第3种，共16步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [3, 5, 0], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第4种，共14步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第5种，共13步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [3, 5, 0], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第6种，共12步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [3, 5, 0], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第7种，共10步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第8种，共10步： [[0, 0, 8], [3, 0, 5], [3, 5, 0], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第9种，共13步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第10种，共8步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [0, 4, 4]]
第11种，共15步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第12种，共16步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 4, 1], [3, 5, 0], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第13种，共15步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [0, 2, 6], [2, 0, 6], [2, 5, 1], [3, 5, 0], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第14种，共11步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第15种，共12步： [[0, 0, 8], [0, 5, 3], [3, 2, 3], [3, 5, 0], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
第16种，共11步： [[0, 0, 8], [0, 5, 3], [3, 5, 0], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [1, 0, 7], [0, 1, 7], [3, 1, 4], [0, 4, 4]]
[Finished in 0.1s]

大头目

网上找到的高人的答案：

1. initial_bucket_state = [0,0,8]
   
2. #水桶的初始状态
   
3. bucket_volume = [3,5,8]
   
4. #每个水桶的对应的容积
   
5. from collections import deque
   
6. record = deque()
   
7. record.append(initial_bucket_state)
   
8. #利用python的deque队列记录状态转移情况，初始化时加入水桶初始状态。deque是可以从头尾插入和删除的队列，在不指定大小时，为一个无边界的队列
   
9. 
   
10. 
    
11. def nextStateLawful(current_state, bucket_volume):
    
12.     next_action = [
    
13.         (from_, to_)
    
14.         for from_ in range(3) for to_ in range(3)
    
15.         if from_ != to_
    
16.             and current_state[from_] > 0
    
17.             and current_state[to_] < bucket_volume[to_]
    
18.     ]
    
19.     #通过列表推导式获得下一动作的二元组构成的列表，由（倒出水的容器编号，倒入水的容器编号）组成。
    
20.     #二重循环得到下一步的所有可能动作，然后通过
    
21.     ##1.倒入倒出不能为同一个2.倒出的捅中必须有水3.倒入的桶中不能为满 的条件判断是否合法
    
22.     for from_, to_ in next_action:
    
23.         #next_state = current_state #浅复制造成错误
    
24.         next_state = list(current_state)
    
25.         if current_state[from_] + current_state[to_] > bucket_volume[to_]:
    
26.             next_state[from_] -= (bucket_volume[to_] - current_state[to_])
    
27.             next_state[to_] = bucket_volume[to_]
    
28.         else:
    
29.             next_state[from_] = 0
    
30.             next_state[to_] = current_state[to_] + current_state[from_]
    
31.         yield next_state
    
32.         #再由所有可能的合法动作得出所有的下一个状态，通过yield产生供其它函数调用。
    
33. 
    
34. num = 0
    
35. record_list = []
    
36. #记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径
    
37. 
    
38. def searchResult(record, bucket_volume=[3,5,8], final_bucket_state=[0,4,4]):
    
39. 
    
40.     global num,record_list
    
41.     current_state = record[-1]
    
42.     #由record的末尾元素得到当前水桶状态
    
43.     next_state = nextStateLawful(current_state, bucket_volume)
    
44.     #得到关于当前状态的下一状态的可迭代生成器，供下一步循环使用
    
45.     for state in next_state:
    
46.     #遍历所有可能的下一状态
    
47.         if state not in record:
    
48.             #保证当前状态没在以前出现过。如果状态已经出现还进行搜索就会形成状态环路，陷入死循环。
    
49.             record.append(state)
    
50.             #添加新的状态到列表中
    
51.             if state == final_bucket_state:
    
52.                 print(record)
    
53.                 #打印出可行方案
    
54.                 #record_list.append(record)这样使用错误，导致加入列表的是record的引用，应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。
    
55.                 record_list.append(deque(record))
    
56.                 num += 1
    
57.             else:
    
58.                 searchResult(record, bucket_volume, final_bucket_state)
    
59.                 #不是最终状态则递归搜索
    
60.             record.pop()
    
61.             #去除当前循环中添加的状态，进入下一个循环，关键步，第一次实现的时候遗漏了
    
62. 
    
63. if __name__=='__main__':            
    
64.     searchResult(record)
    
65.     #开始
    
66.     print(num)
    
67.     #打印所有方案的数量
    
68.     print(min([len(i) for i in record_list]))
    
69.     #打印最短路径方案中的状态总数

复制代码

大头目

grf1973 发表于 2018-10-8 10:45
第1种，共12步： [[0, 0, 8], [3, 0, 5], [0, 3, 5], [3, 3, 2], [1, 5, 2], [0, 5, 3], [3, 2 ...

厉害，佩服

grf1973

我找的也是相同的高人。。。。。，自己改写了一下而已。