数学建模社区-数学中国
标题:
python 解决母亲的奶牛问题
[打印本页]
作者:
2744557306
时间:
2024-3-20 11:38
标题:
python 解决母亲的奶牛问题
题目描述】
9 O. w9 ~' B5 q3 d; R& w; K& t% X
0 z6 y6 Z' Y+ g0 n0 ^5 d
农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的,而桶 C 里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。请你编写一个程序判断,当 A 桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。
' ^$ P/ _" P( J0 j- |
) B0 Z7 }, a& ^
【输入格式】
( M5 S6 l# {. z. t- r( e
+ g& i! I& W( Z0 Q- |, @4 L
共一行,包含三个整数 A,B,C。
0 z5 t; H& D: W' J+ i! Z
( h/ W. o# m7 S' ^2 j
【输出格式】
0 d4 _) I" |( d z/ f
2 ]! [/ f* y4 k* h! g. l8 A
共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。
* u, Q. b5 ?/ g5 W- D
4 W% e& C0 c* d4 _% v
【数据范围】
7 Y( D3 @8 L. \; \% M& o
4 |. {/ N v3 q% T& r' N
1≤A,B,C≤20
0 C9 d6 c6 V0 ?) w
. L* r) Y$ F# H% ~4 s
【输入样例】
6 N* a8 Y+ L7 [ U1 M1 R0 @
5 T, j- V! u) C4 a
8 9 10
0 p' R }* w7 D) ]6 L* b6 V$ j* v
【输出样例】
1 _) m* a+ R" {, F7 M
6 A/ P- t0 L8 L8 O1 u
1 2 8 9 10
: b" I2 W$ F v8 C! Y( c
【解题思路】
- f6 i; [1 G1 K9 S& |
' m" t$ ~1 d, e
BFS简答模拟一下倒牛奶的过程。
from collections import *
5 h- z' \$ P' T6 u
a,b,c = map(int,input().split())
: n7 m" K& l4 g( H
n = 22
1 ?9 t h" p9 i* ]
st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
% f; m) h$ o7 H6 B7 X
N* ?8 H! J6 b9 k0 U
q = deque()
) x& d+ ]! ]' C; t
def ins(a_,b_,c_):
& ~- m3 A2 a& a. t4 S9 U. x3 e& Z
global q
0 K" ^7 v0 V) C' |" ]& t
if st[a_][b_][c_]:return
7 m% \* d& b9 x6 |+ J9 j1 e1 u: q
q.append([a_,b_,c_])
1 Z+ Z7 b$ N% h; R Y# X
st[a_][b_][c_]=1
$ E6 K0 q# ^8 h' M- ]+ w: u* V
def bfs():
1 u) M; h9 Z2 F& @8 n# J
q.append([0,0,c])
, {1 A3 k1 M( @* Z8 K
st[0][0][c]=1
, @9 u# m. r6 f; Y+ x/ U% ~
while q:
+ j, n2 ]) s4 P, E/ E
a_,b_,c_ = q.popleft()
5 j% m, q/ h! I7 F) t! |
ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
0 r" }9 E z0 E3 {" c3 o/ c I
ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
6 M+ I2 L' q8 d* h
ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
5 ~9 V8 P/ q) T+ c `* x0 h& ]+ p' `
ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
; N$ A1 g* M* ^
ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
5 p. v, {$ T' W% m
ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
+ D3 u! d: \9 ^: e4 G+ z$ }% k
bfs()
3 Y* D$ d1 d9 E5 c
for c_ in range(c+1):
2 ^/ X% [3 A7 O# b& h. h
for b_ in range(b+1):
4 Q. E, v% P' g* l6 T
if st[0][b_][c_]:
! v) [2 F7 O8 \1 C4 p
print(c_,end=' ')
4 r' m+ B7 \$ \0 N! u
break
复制代码
0 ]+ _6 J) R. V
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5