数学建模社区-数学中国

标题: 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/ f2 ]! [/ 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≤200 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简答模拟一下倒牛奶的过程。
  1. from collections import *5 h- z' \$ P' T6 u
  2. a,b,c = map(int,input().split()): n7 m" K& l4 g( H
  3. n = 221 ?9 t  h" p9 i* ]
  4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]% f; m) h$ o7 H6 B7 X

  5.   N* ?8 H! J6 b9 k0 U
  6. q = deque()
    ) x& d+ ]! ]' C; t
  7. def ins(a_,b_,c_):
    & ~- m3 A2 a& a. t4 S9 U. x3 e& Z
  8.     global q
    0 K" ^7 v0 V) C' |" ]& t
  9.     if st[a_][b_][c_]:return
    7 m% \* d& b9 x6 |+ J9 j1 e1 u: q
  10.     q.append([a_,b_,c_])
    1 Z+ Z7 b$ N% h; R  Y# X
  11.     st[a_][b_][c_]=1$ E6 K0 q# ^8 h' M- ]+ w: u* V
  12. def bfs():1 u) M; h9 Z2 F& @8 n# J
  13.     q.append([0,0,c]), {1 A3 k1 M( @* Z8 K
  14.     st[0][0][c]=1
    , @9 u# m. r6 f; Y+ x/ U% ~
  15.     while q:
    + j, n2 ]) s4 P, E/ E
  16.         a_,b_,c_ = q.popleft()5 j% m, q/ h! I7 F) t! |
  17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )0 r" }9 E  z0 E3 {" c3 o/ c  I
  18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    6 M+ I2 L' q8 d* h
  19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )5 ~9 V8 P/ q) T+ c  `* x0 h& ]+ p' `
  20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) ); N$ A1 g* M* ^
  21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    5 p. v, {$ T' W% m
  22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )+ D3 u! d: \9 ^: e4 G+ z$ }% k
  23. bfs()3 Y* D$ d1 d9 E5 c
  24. for c_ in range(c+1):2 ^/ X% [3 A7 O# b& h. h
  25.     for b_ in range(b+1):4 Q. E, v% P' g* l6 T
  26.         if st[0][b_][c_]:! v) [2 F7 O8 \1 C4 p
  27.             print(c_,end=' ')4 r' m+ B7 \$ \0 N! u
  28.             break
复制代码
0 ]+ _6 J) R. V




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