python 解决母亲的奶牛问题

2744557306

题目描述】

        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

+ C! L1 A8 t! f' L) F3 X1 L【输入格式】

        共一行，包含三个整数 A,B,C。

【输出格式】
% r% J- C" P9 U$ T  p
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
& s1 A& T8 i  _# ]- f
【数据范围】
' u. w0 C) S2 N: x
        1≤A,B,C≤20
4 k2 S. U. E. R8 L5 W, S6 |8 u; ^
6 d. O( {) T4 z7 y3 b- z) P【输入样例】

8 9 10
【输出样例】

1 2 8 9 10
/ ]1 {% b/ v. n  \# i5 U; I6 e0 c4 G 【解题思路】

        BFS简答模拟一下倒牛奶的过程。

1. from collections import *2 q, J* z' w; W5 _& c; n# b+ F2 E
   
2. a,b,c = map(int,input().split())
   9 I' R, t/ M; s3 P: \- Q2 S
3. n = 22
   \" j3 K4 d2 Q& N0 J, b
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]1 g  I2 o8 ~# }5 `8 n+ `
   
5. 
   0 Q9 }% X1 X6 `/ ~3 O
6. q = deque()( H  l  T0 r8 p7 r0 ]
   
7. def ins(a_,b_,c_):
   1 J: S. O0 J+ k7 q  g
8.     global q
   % m; z4 y5 g\" s
9.     if st[a_][b_][c_]:return
   + e; ?# k! v1 V4 H/ E\" I2 D8 ]' Z- C
10.     q.append([a_,b_,c_]): R; N& o. u! d/ O4 l
    
11.     st[a_][b_][c_]=1
    9 b4 E5 ~; q4 U/ `# V9 u6 p3 ]
12. def bfs():
    / ?3 t7 O  ~: x
13.     q.append([0,0,c])
    ) s4 r9 o\" P\" }7 e$ K
14.     st[0][0][c]=1. @6 D, k' U6 |4 V! j
    
15.     while q:  b# a: i\" W1 X4 f; U
    
16.         a_,b_,c_ = q.popleft(); m  K1 ~* k* @  o; b8 t
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
      Q! E3 a  G8 a% s* L9 B# B
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )( Y3 K9 B5 i' o% G+ ~
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )# c2 r9 _+ a( F- w+ P* j1 v
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )0 T\" ]) G: O4 Y6 U) C: @1 j  {
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
      N& V& D0 {6 J' \# `, @
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    1 m9 s; D) h) v' _0 E, _
23. bfs()  M3 ], B1 ]6 W4 I- ?  y/ L6 a- C
    
24. for c_ in range(c+1):
    ( I% Y3 _) P0 X, V8 Q
25.     for b_ in range(b+1):- i& c' u# A& F& f2 b: r
    
26.         if st[0][b_][c_]:
    & Y7 S& n& c0 {7 m5 D, e  Z# W! ~( r
27.             print(c_,end=' ')
    1 n$ I8 q( t+ E/ z6 h8 p
28.             break

复制代码