数学建模社区-数学中国

标题: 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) p% V( X( t  m( m' h
【输入格式】( f+ R, _& C1 K$ D0 X3 [5 e

9 S0 f7 `' }8 u        共一行,包含三个整数 A,B,C。( K: o: l% F( K+ ~

0 I! }1 _! \5 t6 B* _* R【输出格式】  [& @8 P- g+ t0 p
, Q7 F( D0 V; x- G' r
        共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。
) {% x6 n* J6 T+ u: t- O: L/ j1 w
【数据范围】
: ~* |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 @【输入样例】. d! g+ _% d! t! `+ M% p6 [+ L

1 X1 a+ d  W: s# {- H7 c8 f8 9 10
) D; w/ \% k' q# Q& r) L【输出样例】
5 L# I. ^  e( n8 Y5 _9 ], s5 ~" H- m  ]% \  N4 O$ H/ R
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 *, I0 ?1 N2 k& Q1 t' r7 ]
  2. a,b,c = map(int,input().split())( w4 C4 T) V/ |3 N6 V1 ?1 `( l+ C
  3. n = 225 E! `4 p# h+ q. F* l/ v
  4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
    . ?9 R4 V( D9 v& H; L
  5. / s0 w, ]* I! f$ y+ F5 K* o
  6. q = deque()$ y2 s% w6 _+ N/ q4 [) p7 i/ Q( M# [
  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# T4 Y8 d2 X% W* b* T+ w4 x) A
  10.     q.append([a_,b_,c_])
    5 A, j; q7 p( Q" p6 E
  11.     st[a_][b_][c_]=1+ X. c/ a( I5 U9 U  I7 ~
  12. def bfs():4 ?/ u# a( a" K- F# Q+ S5 d& [7 G
  13.     q.append([0,0,c])/ N0 k# a& a7 X8 s0 {1 O5 A
  14.     st[0][0][c]=17 q, [; D' L& H: `) y7 w
  15.     while q:: m9 y9 |# k- r# `' o. G6 t
  16.         a_,b_,c_ = q.popleft()+ j# Y5 ?' k! ?) k7 I* R1 x* }% w1 k
  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_ )2 y5 U! G1 D. L" I' F+ o8 ?( m
  20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )0 Z* m6 r" r- O5 O
  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_) ), j- a0 T5 \% e& h1 \, b7 [! \
  23. bfs()4 `8 k4 O; M$ Y0 G1 a
  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=' ')& f/ `8 ^9 g, h: y
  28.             break
复制代码
+ l# A/ y- r* E





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5