QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2517|回复: 0
打印 上一主题 下一主题

python 解决母亲的奶牛问题

[复制链接]
字体大小: 正常 放大

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-20 11:38 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
题目描述】
6 |, O* `9 a9 h* `  O3 {  t; L" w3 T2 M
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的,而桶 C 里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。请你编写一个程序判断,当 A 桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。0 L: z* `# c! G* a2 f8 c

: O; f8 M8 s7 |4 }9 |* q- Q【输入格式】
5 ~% L  S; p( b! _: F$ T' r  ^/ Y3 `6 C* w2 _
        共一行,包含三个整数 A,B,C。
1 w6 y! Q; |# v) {
7 J9 |& W" t% d6 H! L1 X【输出格式】
5 N/ }* E3 Y9 P5 L$ l# }, A1 C- D. |
        共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。0 R# A: T# m7 k/ s' J
- I% u$ e- h  v' |
【数据范围】9 E* G0 n& P0 S9 d. P* v

& T2 K, e1 v& h  V& [2 m7 ^" }, I: J        1≤A,B,C≤20
$ d3 f3 x4 e9 }
* T' m& `7 g: _【输入样例】
, i( P, |0 O9 t" l6 A- ?3 M5 p. C& G8 _
8 9 10
" V' v9 \3 b/ E  Q) G【输出样例】
- _; c0 U0 S' Y$ j& ]
5 @+ O4 V' f1 _: ]( j- _1 2 8 9 10# I% L9 r0 `# {- R0 }
【解题思路】
# w6 Z7 E3 ?$ M; h9 r
8 r+ Q6 O$ f1 z% V1 |2 X- b        BFS简答模拟一下倒牛奶的过程。
  1. from collections import *
    : S1 ]/ m6 m* R$ Z
  2. a,b,c = map(int,input().split())3 h, U8 G' L; v# L% D
  3. n = 22$ f1 T. x& \& M
  4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]\" p9 B3 l0 S/ Q, i$ d0 W+ z
  5. 6 i. l1 }! Z  k4 p\" K! b4 T6 v- O
  6. q = deque()0 T- D/ k8 m/ p* N% Q0 [
  7. def ins(a_,b_,c_):* w\" I4 G! I3 U/ u9 f, g
  8.     global q
    6 ~! c- ]\" }) G  B
  9.     if st[a_][b_][c_]:return/ K. g* H/ t  i; D
  10.     q.append([a_,b_,c_])
    & u3 I$ w0 W8 B/ {2 U4 y* g
  11.     st[a_][b_][c_]=15 |; R0 v) o8 O- p4 f
  12. def bfs():
    0 a\" {4 ~) E3 ~, o
  13.     q.append([0,0,c])
    ( Z1 a' ?& y! [# G- Z
  14.     st[0][0][c]=1
    # k) q1 \3 R9 r& ]* }
  15.     while q:
    ! P+ F$ c* i; A% A. F1 C/ ?  |
  16.         a_,b_,c_ = q.popleft()' b+ S& _  w& _0 w
  17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )) f: `$ J- Q: |- p
  18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    & d- c. q  C! S$ [: b
  19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
      x1 n5 m6 v7 I: K\" W
  20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )* v$ b' B/ Q# Z* C7 }3 h* M; o0 c
  21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    3 I2 E+ B2 s& C/ L1 R7 x
  22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    9 N. h8 F' z& m2 o$ I
  23. bfs()( y  X\" v\" H+ A  m8 s4 d; ~
  24. for c_ in range(c+1):
    & ?' a) s& b1 Y
  25.     for b_ in range(b+1):% K( ]; o5 l4 h: B5 Y% O8 u
  26.         if st[0][b_][c_]:, H( K/ f8 M1 z
  27.             print(c_,end=' ')9 @5 z! m4 O- @; P8 e) T
  28.             break
复制代码

( b2 b% P# I/ Z7 r, Y/ O
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-7-10 09:59 , Processed in 0.274775 second(s), 51 queries .

回顶部