数学建模社区-数学中国

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

---

作者: 2744557306    时间: 2024-3-20 11:38
标题: python 解决母亲的奶牛问题
题目描述】

6 `5 _, I9 f2 o, ^# u0 k  P        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

【输入格式】
1 [, A$ f! n; o
        共一行，包含三个整数 A,B,C。
) M# B7 z! X8 w! n: C0 F
【输出格式】
& U6 g8 F) V0 Z8 Q
: C0 v. B% X6 P7 P; J2 J) v        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
- G" F; k6 Y/ ], o( q1 o# f
【数据范围】
4 d0 r4 g7 Y: i& S0 m
        1≤A,B,C≤20
' }; L* w- p0 ^% s/ e
0 G7 c- S0 B$ o, T, l) U2 B【输入样例】

8 9 10
( G' g0 N1 b: O5 T# s( Q【输出样例】
, w, V( V+ h1 s/ c8 m( |
' @5 L0 h4 O) Q, R: L$ A1 2 8 9 10
7 b  }" u- R+ E  ]2 i7 W" f 【解题思路】

        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   8 x: f+ A3 f  z4 c7 }
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)]
   + |1 i+ l7 A  R" c( C5 q0 ]4 h
5. 
   , Y" t3 ~. K* n* i+ J
6. q = deque()
   
7. def ins(a_,b_,c_):
   
8.     global q
   ' @4 m- x1 h7 \# ]8 B, p) g/ f
9.     if st[a_][b_][c_]:return
   
10.     q.append([a_,b_,c_])
    
11.     st[a_][b_][c_]=1
    
12. def bfs():
    
13.     q.append([0,0,c])
    3 Z; Y# F* _% }/ S
14.     st[0][0][c]=1
    
15.     while q:
    0 f- j0 |& z0 G  h0 l
16.         a_,b_,c_ = q.popleft()
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    0 N1 Q3 l) H+ N
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    , ]2 f8 a/ G% o) V  w$ s+ l+ j. Q1 E
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_) )
    ( q* k9 O  p$ N7 T( M& \* ^7 W$ k
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    
23. bfs()
    2 J4 J3 N1 @  ]" k5 @& a
24. for c_ in range(c+1):
    
25.     for b_ in range(b+1):
    
26.         if st[0][b_][c_]:
    
27.             print(c_,end=' ')
    
28.             break

复制代码

---

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

Powered by Discuz! X2.5