7137 - 新大榭微课№:001 - 【案例】百钱百鸡问题（公开课）

admin

百钱百鸡是我国古代数学家 张丘建 在《算经》一书中提出的数学问题：
+ [6 l# f; n+ q鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。
百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

---

(*)注：本题出自浙江省普通高中《信息技术》（必修一）P100页第6题   →【传送门】

1. 温馨提示：该传送门需要一星及其以上会员才能正常显示！

复制代码

翻译成现代文是：

公鸡5元一只，母鸡3元一只，小鸡1元三只；
请问用100元买一百只鸡，那么公鸡、母鸡、小鸡各有多少只？

( [/ p2 ~  r8 {7 O6 m题目要求总共买 100 只鸡，由此可知，所买公鸡的数量肯定在 0～20 之间；
! J; l* D3 H( r1 ~3 J4 ~5 I) J+ Q: c
同理，母鸡的数量在 0～33 之间；

创建变量 cock 代替公鸡，hen 代替母鸡，chicken 代替小鸡；
, {; v* s3 T1 @: r+ s: T4 _
那么 cock+hen+chicken == 100，将百钱买百鸡问题就转化成解方程组。

$ o/ W' e; H( Y( |( u  O- V; k一旦可以写成公式，那么就可以用程序来代替。
" m, X& {( z8 g& |
" [0 F" j. M) c! i除了上面的条件，还有保证价格之和为100元：cock*5 + hen*3 + chicken/3 == 100
( `3 N1 e7 M6 T1 U3 K0 O" a
$ M1 r6 f& I) @+ m: H" j对于方程组，最简单粗暴的方式就是用 穷举循环 的方法来解决！

反正计算机最擅长的“傻算”，呵呵~

通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。
* |8 S9 q2 d. @7 t- H+ l
cock 的取值范围是 0～20，可用以下循环语句实现：
% J9 N- q6 l0 L
) u; c6 m  d5 Z( R# K, e

1. for cock in range(0,21)

复制代码

7 o1 V: r% ]- W钱的数量是固定的，要买鸡的总数量也是固定的！
# s! m) x6 V2 }
! }  r6 q# A( _1 G! @2 G1 W既然穷举完公鸡，就在其基础上穷举母鸡，然后再在其基础上再穷举小鸡。

每一次都傻算就好，我们可以利用三层循环的嵌套来解决：
( T* j7 j6 Q9 r4 Q' D6 G* u' V7 X

• 第一层循环控制公鸡的数量
• 第二层控制母鸡的数量
• 最内层控制小鸡的数量
  

6 E8 D5 @2 Q4 B每层循环的初值是 0（即买的 100 只鸡中，可能没有公鸡，也可能没有母鸡或小鸡）
! Q8 [9 D' v$ l4 m& Z1 ?5 m) d
循环的控制条件就是公鸡、母鸡和小鸡用百钱分别最多能够买到的数量！
& m: u( G: m: A# W. u
公鸡最多 20 只，母鸡最多 33 只，小鸡最多 100 只。
5 Y0 i" o) y. n8 \2 O1 O
! h! L1 k8 N6 l3 c! Q) p穷举循环的特点就是把所有情况都考虑到，因此每层循环执行一次，对应循环变量的值就要加 1 。
7 r- e* A, Q" ]1 @) y1 Z) I
很傻很粗暴的循环就好，很方便理解对吧！
: ], x9 a- a8 H( Y; S
↓↓↓ 化成流程图就是：（点击查看大图）
8 v, x) _" b& R1 @, j! Q7 ~1 u


根据流程图，构建程序框架，编写代码如下：

1. # -*- coding: utf-8 -*-
   - b8 ~8 F2 t1 {
2. """
   ) a" b- F1 B5 o3 M" p8 w
3. @Team: 新大榭论坛
   
4. @Author: 张黎斌
   % ^$ L3 u/ T0 L$ g  o
5. @update: 2021-07-25
   
6. @Version: v1.1
   
7. @BBSid: 7137
   8 ?5 b: N5 u; W7 z& R& J
8. @Level: A
   ( \, l4 B- H; A& i" w$ |  @
9. ---------------------------
   % i+ q0 w- C* U' |$ x
10. 古代经典《百钱百鸡》问题
    
11. ---------------------------
    1 D# Z) w- N5 {/ R; u. X( |* w
12. 
    
13. """
    
14. print("+----------------------------------------------------------+")
    
15. print(">>> 新大榭Python文件启动程序（py文件双击） V1.2.21.0727 ")
    
16. print("+----------------------------------------------------------+")
    
17. print(">>> 新大榭Web实验室 http://lab.daxie.net.cn/ ")
    
18. print("+----------------------------------------------------------+")
    0 m8 V6 N  F, c
19. print("↓↓↓ 古代经典《百钱百鸡》问题")
      d7 f# F0 `' G" p2 [
20. print("+----------------------------------------------------------+")
    % O! T+ Y# O( H2 u
21. 
    # v" [% b4 C1 J) ~! @% A9 W- p, g
22. # 以下为主程序核心代码 ↓↓↓
    
23. 
    
24. cock = 0
    
25. while cock <= 20:
    " Y: L$ N. |$ [$ r
26.         # 内层循环控制母鸡数量取值范围为0～33
    ' _" E7 W, N2 K2 W: m; n. O1 [
27.         hen = 0
      w# n% b9 j/ l$ V/ A
28.         while hen <= 33:
    
29.             # 内层循环控制小鸡数量取值范围为0～100
    
30.             chicken = 0
    0 F6 V0 W) `; E& L
31.             while chicken <= 100:
    8 Y8 q+ l* s" [, S
32.                 # 条件控制
    
33.                 if (5 * cock + 3 * hen + chicken / 3.0 == 100) and (cock + hen + chicken == 100):
    4 v' ~, E2 L! A3 f" L$ ]- p& t; {
34.                     print("cock=%d,hen=%d,chicken=%d\n" % (cock, hen, chicken))
    
35.                 chicken += 1
    
36.             hen += 1
    
37.         cock += 1
    ) w" Z' ^% k4 u1 X8 D1 M1 `$ ?3 j
38. 
    2 T. ?) r' i: T9 y/ K6 l
39. # ↓↓↓ 以下代码优化与答题无关，可屏蔽IDLE程序意外退出！
    
40. 
    ' Q3 e2 b" K# o( T/ c- b. `5 \8 v
41. print("┏----------------------------┓")
    ' q4 f2 p" |( X
42. print("┣--- 按下回车键即退出程序 ---┫")
    ' U) N! A9 g8 ^& L% [: [+ o
43. print("┗----------------------------┛")
    
44. input(">>>")

复制代码

  I3 A$ A+ X1 t/ e- l- ?" C7 N  好了，课间休息十分钟吧，咱们稍后回来 ...

admin

' O* V( x8 q% ^$ J( `1 O9 S. \' W好了，接下来我们开始继续咯！
3 y5 ~. ~6 O  t- [- L) w
' r7 W7 N! \2 v% X7 F: A; N同学们，老师在上一节课中使用了 while 循环语句进行穷举，

+ D( S3 z) e$ j6 p! g1 c2 a那同学们知道用while本题共要穷举多少次吗？（此处应该有举手）

没错，以上算法需要穷举尝试共 21×34×101=72114 次，算法的效率显然可以再优化！

对于本题来说，公鸡和母鸡的数量确定后，小鸡的数量就可以确定为 100-cock-hen，无须再进行穷举了！
# j" c5 d: [, e9 {
6 ?5 _3 d6 j& J  w' s% H) r此时约束条件也只有一个，即 5×cock+3×hen+chicken/3==100
! u, [+ a- g8 @: k, ]
思路框架有啦，具体敲代码就轻松了，代码如下：

1. """
   ( l9 \7 m0 c! B. F$ z5 y# ~
2. Team: 新大榭
   ( X3 k6 P) y% K; E
3. Author: 张黎斌
   0 G  {. K/ w" x0 ?$ V. X; u
4. update: 2021-07-18
   & o4 p' C9 [9 ?# Y5 M) X7 Z0 b- s
5. Level: A
   9 f3 c3 w. ?9 t
6. 
   
7. 古代经典的《百钱百鸡》解法二 for循环
   
8. """
   7 O6 g' @  M2 S' k- i
9. for x in range(0,21):  # x取值范围 0<=x<=20
   ! h. x/ q+ L& J
10.     for y in range(0,34):  # y取值范围 0<=y<=33
    2 j: q0 p1 C$ s9 E- D; q
11.         z = 100 - x - y
    
12.         if 5 * x + 3 * y + z / 3 == 100:
    6 A- {% V$ j1 _2 X! I
13.             print('公鸡: %d只, 母鸡: %d只, 小鸡: %d只' % (x,y,z))

复制代码

上面使用的算法我们称它为 穷举法，也称为 暴力搜索法，这种方法通过一项一项的列举备选解决方案中所有可能的候选项并检查每个候选项是否符合问题的描述，最终得到问题的解。这种方法看起来比较笨拙，但对于运算能力非常强大的计算机来说，通常都是一个可行的甚至是不错的选择，而且问题的解如果存在，这种方法一定能够找到它。

总结：方法1采用while循环，方法2采用for循环，通过算法对比，我们不难发现本题方法2更显简洁高效！

admin

最后，我们不仿来看看国内大学校园学哥学姐们对古代经典《百钱百鸡》问题的另类解法：

1. for cock in range(0,101,5):
   
2.     for hen in range(0,101 - cock,3):
   
3.         chicken=100-cock-hen
   
4.         if cock/5+hen/3+chicken*3==100:
   6 L  j" p/ z$ n0 o
5.             print("cock=%d,hen=%d,chicken=%d"%(cock/5,hen/3,chicken*3))

复制代码

比如这样：

1. cock, hen, chick = 0, 0, 0    #数量
   
2. 
   - e& j/ R& \# [* P$ B7 W
3. for cock in range(0,21):
   4 T9 u+ X9 B/ v+ P
4.     for hen in range(0,34):
   
5.         for chick in range(100 - cock - hen,101,3):
   
6. 
   $ N+ y0 B& \* Z, n
7.             total = cock + hen + chick
   : ~9 s  c, K) m1 w# r! s$ l
8.             total_price = cock*5 + hen*3 + chick/3
   , L% r+ R  n. \/ T4 f( F
9. 
   
10.             if total == total_price == 100:
    
11.                 print('cock = %d, hen = %d, chick = %d, 总数 = %d, 总价 = %d'
    1 w! g0 s- ^7 D- U
12.                       % (cock, hen, chick, total, total_price))

复制代码

再比如这样：
8 n  P2 }; C5 }" e3 }7 s# s

1. # Initiate the value
   : B  X" ]* u7 P/ K  y) s: Z1 D
2. hen = 0
   
3. rooster = 0
   , `: w& P" J# }4 E* ]1 L' N
4. chick = 0
   
5. 
   % T% D3 R" N3 \1 U% g
6. # start calculating
   + X9 \# `- `: d# K! f
7. for rooster in range(21):
   
8.     for hen in range(34):
   * r, B  L0 y+ X
9.         if (100 - 3 * hen - 5 * rooster) * 3 + hen + rooster == 100:
   
10.             chick = 100 - hen - rooster
    9 V% e8 K& J" B( K4 ?  r1 @
11.             print(f"rooster is {rooster},"
    0 W, g5 R6 o, E& r' p. |' ]
12.                   f"hen is {hen},"
    
13.                   f"chick is {chick}")

复制代码

总结：条条大道通罗马，希望同学们今后通过对算法不断学习，提升自己编程技能！加油！

---

预告：暑期公益开播第二讲  - 《查找女神手机号》（点击传送门）
% R  e* S) ]% E2 l. i- {