数学建模社区-数学中国

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

---

作者: 2744557306    时间: 2024-3-20 11:38
标题: python 解决母亲的奶牛问题
题目描述】
  g9 h2 K0 n3 F
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

+ K; e' d4 p5 j8 j【输入格式】
' Z  \; v8 L& j0 i( x
- e  w3 q1 A; o8 D        共一行，包含三个整数 A,B,C。

: C6 E! _/ x7 H. G0 H【输出格式】
8 q& ~) D+ w* C& L" h
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】
' k/ i- A- M2 t) @' d7 ?, t
4 Y# g, |7 @  ?+ {' P( I        1≤A,B,C≤20

【输入样例】

  Q2 X0 P* |& ^( F8 9 10
: X6 ~1 o" ~% p+ _! y【输出样例】
$ @( Y* @3 w' q" Q
1 2 8 9 10
【解题思路】

4 w1 ^1 d. Q( G. T: H9 H/ k: w        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   + I- S/ y8 _7 b( d2 a2 B
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)]
   8 ]  @; B" A- I- n' n2 f
5. 
   / u/ u# T7 x5 c
6. q = deque()
   . s$ u2 d# R# l( m& F4 m; `; ?% t
7. def ins(a_,b_,c_):
   
8.     global q
   
9.     if st[a_][b_][c_]:return
   2 v' @: U2 S# F, _' \' A. {6 M
10.     q.append([a_,b_,c_])
    0 z$ \- q8 M6 G8 k5 u2 D: O
11.     st[a_][b_][c_]=1
    . {" F; v- V7 `) r9 h* ~
12. def bfs():
    
13.     q.append([0,0,c])
    
14.     st[0][0][c]=1
    : `1 `0 e% `7 F/ t% i* o
15.     while q:
    - \+ B  Y7 c6 L2 x+ [5 ?2 k" f
16.         a_,b_,c_ = q.popleft()
    # B! f1 E2 U/ K! U& e
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    + q% v0 K2 A/ o6 p( i, n
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    * ^  M; c. R2 U" P. m$ f
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    5 g( a0 j5 o1 v9 I8 n8 ]
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    
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()
    
24. for c_ in range(c+1):
    
25.     for b_ in range(b+1):
    ) F) `) D; j( m* ?) l
26.         if st[0][b_][c_]:
    
27.             print(c_,end=' ')
    
28.             break

复制代码

---

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

Powered by Discuz! X2.5