python 解决母亲的奶牛问题

2744557306

题目描述】

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

: E  n& r7 P0 B2 }, L1 A【输入格式】

6 K( S' l5 E$ P1 z        共一行，包含三个整数 A,B,C。
# i" b' T/ F' x! ?
6 V$ Q* l& g% J) X: Y+ \; U【输出格式】

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

- ^; a8 @' x; D) h% L- {) s【数据范围】
; K0 O! O; V, O7 Q# ]$ N
# r# d; A# e" F  Q; O9 Q# \        1≤A,B,C≤20

' c. m3 _2 h. m/ G( O. ]( m【输入样例】
5 X  d  R, f; D) f5 Q7 s
) m5 y* H3 q( v6 ?9 R* B8 9 10
【输出样例】

1 2 8 9 10
【解题思路】
9 o, @: D0 X  I) [( B
9 i; u; @, S0 g2 K+ m9 Z, P' J        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   : |: {  V. N- @% O1 I% t; C# ~
2. a,b,c = map(int,input().split())4 }; S2 ^: v5 A& S( P& i
   
3. n = 22
   ; n8 Y6 a( G4 u\" y5 F
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]& R\" V2 Y2 s: Y
   
5. 
     Y( s\" r# J3 d' e# P
6. q = deque()7 W0 ?3 {. c9 I6 M. v) P. V
   
7. def ins(a_,b_,c_):! h, s1 y+ @* `- R4 c  z5 @0 b
   
8.     global q$ A/ G- K& t+ Y4 k9 ^6 o$ `
   
9.     if st[a_][b_][c_]:return! ?4 F5 ?$ O\" Z
   
10.     q.append([a_,b_,c_])( y7 Z  d! i$ @. h  L( h
    
11.     st[a_][b_][c_]=1( C. B& x5 v& w+ A
    
12. def bfs():3 B* M8 |7 J, d5 [, {
    
13.     q.append([0,0,c])2 c9 i\" F/ W- X: j( ^- b
    
14.     st[0][0][c]=1! r# O. L/ L( r2 J1 p; [2 X
    
15.     while q:
    6 m& }* g# T1 Z; \
16.         a_,b_,c_ = q.popleft()
    , {! ]8 V. w# q3 s
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )9 f7 e! o& w* n\" a0 Z1 }5 O% i3 X
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    3 H' z0 g( r; X4 ~4 d6 J+ @1 n! K3 N
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    0 R6 n1 G9 C3 V
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    : w/ T# ^' r( r
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )  G# _2 B7 {. Z7 E& x: o1 E3 t
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    ; q4 r6 G1 r9 B
23. bfs()% }; [. f/ e/ n- R9 a' ]
    
24. for c_ in range(c+1):
    \" `7 Z$ O- v$ B! T! {
25.     for b_ in range(b+1):; I; c# D) n0 {# a# z
    
26.         if st[0][b_][c_]:# r4 l/ \5 t. s7 U\" ~) l# |
    
27.             print(c_,end=' ')9 K( o' a! q/ L# W8 z: |  l
    
28.             break

复制代码

6 R( o, i$ q, `! E0 B