python 解决母亲的奶牛问题

2744557306

题目描述】
6 @' \4 t# i0 B( [  m: B
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
0 l, M5 W% D! q0 T1 v$ K
$ o( \+ \9 @! h+ \0 o% K5 i7 o【输入格式】

        共一行，包含三个整数 A,B,C。
3 t* j7 v7 O% _
【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
" H9 c' H6 v" t5 e
【数据范围】

        1≤A,B,C≤20
, I6 p1 s" Z0 X- d& ~& J2 `
【输入样例】

8 9 10
& U9 t+ d' E! k6 V- C3 T1 w【输出样例】

1 2 8 9 10
: [# E" s. o5 \; g8 a( m 【解题思路】
! w' v: V" l. k
' M, V6 ~0 K7 w& i% E        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   : T, k9 s+ i: H: h+ P/ ~- b5 F
2. a,b,c = map(int,input().split())
   & Z\" O9 d/ M. I& ]. a- I& \
3. n = 226 i+ F) x: j, N. J# v9 ]# f% G
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]% ~# U- _* W0 j. i$ x
   
5. 
   ; [/ V0 l8 M( E# T( g
6. q = deque()( U6 A2 }, G2 A5 I0 F
   
7. def ins(a_,b_,c_):
   - ?\" m  z$ h\" F9 N* b
8.     global q
   & f' V8 S1 q/ V. s5 \! F5 V/ @- s
9.     if st[a_][b_][c_]:return
   : R4 n8 z+ J9 E; Q
10.     q.append([a_,b_,c_])
    9 s4 R/ Q: O' \
11.     st[a_][b_][c_]=1
    5 X' K8 A' b% N' N, ]/ t  X( B! i+ \
12. def bfs():
    4 p' l$ d9 _: x0 w  A4 W3 |' ?: e( `
13.     q.append([0,0,c])8 E! j. E3 A8 T5 E! I
    
14.     st[0][0][c]=1
    ! k) @- v\" s* x  {+ R; a
15.     while q:
      w1 r) ~; s3 J# l) n% A# h! d
16.         a_,b_,c_ = q.popleft()
    * `8 G& C- \/ N\" j3 z
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    $ D: J0 _* y$ J9 y! \; O4 {
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    / i; e0 T- @% v' s& Z5 w
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )! V2 ?% @( c* i
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    . Q6 z- [( t1 J0 D' A0 K& \
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) ); ~8 b7 B: d- F( H
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    2 I3 s' V8 O' m* a
23. bfs()1 @$ J! g$ J2 Q% O! W4 U
    
24. for c_ in range(c+1):
    8 Q1 I# _2 g) m# y& g
25.     for b_ in range(b+1):
    3 ^% }* T; {: p. ~  p. s. u9 _
26.         if st[0][b_][c_]:
    4 D% t1 [! V; z. B7 e' R
27.             print(c_,end=' '), c4 e+ @' y, j' U6 W6 s* L- ?
    
28.             break

复制代码