python 解决母亲的奶牛问题
题目描述】农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
【输入格式】
共一行，包含三个整数 A,B,C。
【输出格式】
共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
【数据范围】
1≤A,B,C≤20
【输入样例】
8 9 10
【输出样例】
1 2 8 9 10
【解题思路】
BFS简答模拟一下倒牛奶的过程。from collections import *
a,b,c = map(int,input().split())
n = 22
st = [[ for _ in range(n)] for _ in range(n)]
q = deque()
def ins(a_,b_,c_):
global q
if st:return
q.append()
st=1
def bfs():
q.append()
st=1
while q:
a_,b_,c_ = q.popleft()
ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
bfs()
for c_ in range(c+1):
for b_ in range(b+1):
if st:
print(c_,end=' ')
break
页:
[1]