python 解决母亲的奶牛问题

2744557306

题目描述】

        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
6 m7 ~0 ~4 z7 }# A5 k+ T- ^( D6 z
8 U  I7 i( g5 D3 \【输入格式】
( j0 d$ S! m/ x: I  V
9 K9 L8 @' N" T        共一行，包含三个整数 A,B,C。

【输出格式】

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

【数据范围】
- [; n- w+ L4 j7 }" Z' T# v; y" p
        1≤A,B,C≤20
  @! e1 s4 B6 g. ]1 l
【输入样例】

3 s' h/ C8 u( u: e# ?& J5 k8 9 10
【输出样例】
( R& F+ }, b; f8 ^* s1 k0 j
1 2 8 9 10
【解题思路】

1 {% i6 d# y2 d/ r        BFS简答模拟一下倒牛奶的过程。

1. from collections import *% n+ O. f' U+ ^! L, G- I& L7 a3 d0 E, o
   
2. a,b,c = map(int,input().split())
   + T! B. ?' r  K
3. n = 228 H+ Z+ F/ y! Z\" |  f\" v
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   $ @# E- N: j* L0 k9 @
5. 
   8 w3 c7 Z8 p) X- t! d9 r% A# Z
6. q = deque()
   , s1 j4 e\" R) O& _7 M% n# h
7. def ins(a_,b_,c_):
   ( y4 x$ ~7 g9 i& Y# |% d6 u9 e
8.     global q6 p& K; N% d) O
   
9.     if st[a_][b_][c_]:return1 F7 U- S6 J7 g
   
10.     q.append([a_,b_,c_])
    1 Y/ r\" _: n/ ?  T& u8 |
11.     st[a_][b_][c_]=1
    / p' w2 O! {\" R8 m% ]\" j
12. def bfs():6 P$ P6 W4 G4 s& X
    
13.     q.append([0,0,c])
    $ P& B9 }  D& u
14.     st[0][0][c]=1
    . l& ]9 ?& W  j\" L4 w
15.     while q:
    6 e5 A2 M( l+ y
16.         a_,b_,c_ = q.popleft()
    1 U# K1 Z4 f. G; B9 I
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ ). x3 v8 Z* O' X# i& U\" Z
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    * t  \2 Y( m) ]- G
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )# _) B/ q3 K. n& T! ^& @
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )/ e+ W& {6 ]# Q' f% [
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    2 c# w! |% I9 L  l  I# ^
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )) x) O# y: _9 i9 h
    
23. bfs()
    8 ~\" a0 _5 g: z. X( n
24. for c_ in range(c+1):# T1 O  o5 b0 Q' Q) n3 f
    
25.     for b_ in range(b+1):3 t9 ?* F7 Q) w# t, r( T) l
    
26.         if st[0][b_][c_]:
    ! ~$ Z1 M6 E3 t/ F; E+ x
27.             print(c_,end=' ')
    2 R$ {1 U: y% R, W+ s
28.             break

复制代码