数学建模社区-数学中国

标题: python 解决母亲的奶牛问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:38
标题: python 解决母亲的奶牛问题
题目描述】
$ n& _2 F! |. }  D# u7 l* a0 S6 q/ w$ s2 z/ Q7 `2 h
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
& F. O7 H' u; Q5 U: Z& H2 T6 [2 {5 n; Y, y
【输入格式】
) y9 O1 z# _: D, y+ L* L4 d' o) [
        共一行，包含三个整数 A,B,C。* e0 L1 y& w8 e* Q
' b( |: n! G% k0 n& L
【输出格式】
8 _" ^( n! ~& G, j+ f2 B3 `9 k# [2 c+ |: |8 P. C% R
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
9 K" ~( k8 j& v3 M) V6 b' e' T0 x, c  ], n( j
【数据范围】
2 I8 f' Z1 P6 T8 @4 K" B$ ~
. F& x4 b  |6 }) p/ h/ B        1≤A,B,C≤203 R- a) ]. w2 S8 [

2 K+ H  y; o# \( U! L+ p+ P【输入样例】7 u- w+ [8 m  C5 i* ^0 j
; w+ ^/ u1 L1 N$ y
8 9 100 y' s/ u: B% i6 G# S6 Q( V  w3 o3 Y
【输出样例】" L  F) U+ ~7 r: t+ c
7 q* U$ d7 |% o! E# @1 p- l; b, h
1 2 8 9 10
& k& U9 s, A" H 【解题思路】0 a% G) d" q5 T3 j( u$ L

2 [+ P4 ~8 t! K- k        BFS简答模拟一下倒牛奶的过程。
  1. from collections import *! [( i$ m# K- M
  2. a,b,c = map(int,input().split())
    9 `' ]" a/ ]! q2 J1 i3 X9 N
  3. n = 225 G/ B1 L1 D4 T0 \- j
  4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]. i! b2 r6 T/ T) Z, l
  5. / F0 N. l' j9 z- p8 t
  6. q = deque(): v3 r- ~8 a1 K6 \1 S
  7. def ins(a_,b_,c_):
    + t" o* R  H% N3 |0 k
  8.     global q
    - S# R7 {5 o) O4 R) i
  9.     if st[a_][b_][c_]:return
      K3 y2 p3 U$ E* P3 I- R
  10.     q.append([a_,b_,c_])0 D6 h5 L( t* Z- Y
  11.     st[a_][b_][c_]=1+ U3 m) V  Y: q/ x. Q
  12. def bfs():4 }- `$ _  h4 O
  13.     q.append([0,0,c])" v; j# F! z1 q* b7 e( z( H
  14.     st[0][0][c]=1# J( H. z& H& T- O
  15.     while q:
    1 r) e, i, i  d% o
  16.         a_,b_,c_ = q.popleft(), J, S* f# {& N- v3 Z5 W1 N( @
  17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    ( Q, z% U: l. N
  18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ! @, D0 y) k% {
  19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )8 w9 W; }  `0 ^$ L6 D/ F% p4 ~3 e8 |
  20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    ; s) t$ V7 T; ^1 }' U
  21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )$ N( ]' \- ?7 r
  22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )& y. C: s" A% z2 ~1 Y
  23. bfs()
    ) }& }6 L3 b$ @- s( c' Q' |- Z; h
  24. for c_ in range(c+1):
    / s( N/ D% f3 \5 t
  25.     for b_ in range(b+1):) E/ y+ Q. o- ^: O  R
  26.         if st[0][b_][c_]:
    ) Q- L% n/ q3 p+ v2 R/ e: p5 x
  27.             print(c_,end=' ')
    5 P" A+ R% s( u. G9 D2 n6 g
  28.             break
复制代码
  ]% X; U3 M( M0 S




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