数学建模社区-数学中国

标题: python 解决母亲的奶牛问题 [打印本页]

---

作者: 2744557306    时间: 2024-3-20 11:38
标题: python 解决母亲的奶牛问题
题目描述】
! s8 P  ^2 F/ _5 s" Q
5 q+ g2 q5 R: {3 E4 D" ]/ ]        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
9 k6 F$ Q& j% D
【输入格式】

9 S0 f7 `' }8 u        共一行，包含三个整数 A,B,C。

0 I! }1 _! \5 t6 B* _* R【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
) {% x6 n* J6 T+ u
【数据范围】
: ~* |9 e2 `4 t& f4 }6 {
3 |1 P, u+ {5 ^# ]) W0 p5 h6 b        1≤A,B,C≤20
1 P; @* W, }% Z: Z9 w/ U& {5 U
3 W, q+ n) |6 _1 v- U1 k1 @【输入样例】

1 X1 a+ d  W: s# {- H7 c8 f8 9 10
) D; w/ \% k' q# Q& r) L【输出样例】
5 L# I. ^  e( n8 Y5 _
1 2 8 9 10
9 ~3 j+ {. N8 Z- p& D) T  l+ g' g 【解题思路】
$ F# k- ~: p( W; d' l) c
5 v$ s0 E1 @9 p$ `        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   
2. a,b,c = map(int,input().split())
   
3. n = 22
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   . ?9 R4 V( D9 v& H; L
5. 
   
6. q = deque()
   
7. def ins(a_,b_,c_):
   $ C# j7 R) q5 G1 W
8.     global q
   * z, C; u/ k, j/ Z# d% ]% O. _/ Q
9.     if st[a_][b_][c_]:return
   
10.     q.append([a_,b_,c_])
    5 A, j; q7 p( Q" p6 E
11.     st[a_][b_][c_]=1
    
12. def bfs():
    
13.     q.append([0,0,c])
    
14.     st[0][0][c]=1
    
15.     while q:
    
16.         a_,b_,c_ = q.popleft()
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    , A* \2 G* k2 o1 ^- g4 r* O
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    / e' c3 g, P, A4 L1 m* ?6 P
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    ( j- R: R* ?  \% S% y" T0 D
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    
23. bfs()
    
24. for c_ in range(c+1):
    2 J9 c+ t. ~) L  k
25.     for b_ in range(b+1):
    4 O* X4 q' k  J
26.         if st[0][b_][c_]:
    - w) {6 o8 j4 r! I4 _: o" g, A5 e
27.             print(c_,end=' ')
    
28.             break

复制代码

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5