python 解决母亲的奶牛问题

2744557306

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

【输入格式】
* d$ _! I: [! s4 v, q& q. T
        共一行，包含三个整数 A,B,C。
. {) F$ B6 F- R% E
/ C3 k& |2 Z3 a0 v6 ^. n【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】

9 f. P8 `8 X$ s$ H5 Z: c- E        1≤A,B,C≤20

【输入样例】

0 n- m& H4 O5 u& \, w. R- u. ?8 9 10
【输出样例】
5 c& y/ E+ V, o
1 2 8 9 10
7 Q# s  T7 |6 k/ i8 R' `6 _& q" n9 ` 【解题思路】
: O& K) A' s( P% m- D- t) G
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *6 e& H* V4 Y, g+ ]. I* g; f! ]
   
2. a,b,c = map(int,input().split())
   3 X1 H) W! Q0 G) N' M' |: m
3. n = 22
   4 i: a+ |5 X8 a! b: d
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   & K' R* f1 p7 a) Q/ S
5. 
   ! O( X$ X7 n  N
6. q = deque()2 u* G) Y% l9 v2 ~! V\" ^' @7 }
   
7. def ins(a_,b_,c_):
   ' v6 F\" M9 t* q  x\" h\" I
8.     global q2 K+ r5 C$ `) Y! f
   
9.     if st[a_][b_][c_]:return
   ; r8 j' U* \7 H
10.     q.append([a_,b_,c_])- i\" Z4 {9 N8 g& w- H. I: R! _7 t
    
11.     st[a_][b_][c_]=1$ U/ V# I$ v\" P& ^
    
12. def bfs():
    8 h% N; \, L) ~9 v
13.     q.append([0,0,c])
    # Q; [2 F  T* q+ y& }; t\" L' L
14.     st[0][0][c]=18 ?5 S4 i2 q& ~) f* s% i: a0 {
    
15.     while q:5 l; h: d. F0 k; p& ]: ?
    
16.         a_,b_,c_ = q.popleft()
    ; o6 }3 U\" R+ K1 {! E: G3 R) J' v
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )+ D! Z& S& J; S\" O) m
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    \" t+ N7 \1 c; o4 n( M
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )8 Z/ S\" q, C  z# J
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    , Q) A: Q; A1 [$ Q; [
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    \" Z7 x1 |# B/ E$ i& C' S% j2 ~
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
      \; S; Y; n' m: V1 Z\" V) {
23. bfs()
    + O* T6 P4 d- N# @3 K: o! Q
24. for c_ in range(c+1):
    : x# {0 ~; [: j5 g7 \, G& m
25.     for b_ in range(b+1):9 S0 e' A/ d4 ]# D1 ~8 T
    
26.         if st[0][b_][c_]:
    0 ?9 {& D7 f5 ?8 V! h2 E
27.             print(c_,end=' ')
    $ f4 _# k) j8 _8 Q, ^
28.             break

复制代码

. h* _$ V; o0 @