Python|算法在程序设计中的作用——以百钱买百鸡为例

算法 + 数据结构 = 程序

好的程序取决于好的算法和优良的数据结构，因此在程序设计的过程中不仅需要考虑时间复杂度，而且需要考虑空间复杂度，即就是节约计算所需时间成本的同时，占用较少的内存资源。本文将以一个简单的例子来说明算法在程序设计的过程中所发挥的重要作用。

问题描述：

一个人只有100元钱，需要在花光所有钱的情况下购买公鸡、母鸡和小鸡共一百只（百钱买百鸡）。已知公鸡每只3元，母鸡每只1元，小鸡每只0.5元，请编写python程序求出共有几种购买方案以及每种方案下公鸡、母鸡和小鸡各几只。（要求购买的一百只鸡里面必须同时具有公鸡、母鸡和小鸡）

1 分析问题

首先分析单纯购买每种鸡，分别能够买多少只：
公鸡：100 / 3 ≈ 33(只)
母鸡：100 / 1 = 100(只)
小鸡：100 / 0.5 = 200(只)
既然是利用python编程，则可以借用计算机本身强大的计算能力进行循环遍历操作，尝试每一种可能的情况，直到满足条件后对可行的结果进行输出。

2 解决问题

2.1 在此附上python代码

# 三层循环
num = 1         # 用于计算有多少种方案
count = 0       # 用于计算循环的次数
for gj in range(1,34):
    for mj in range(1,101):
        for xj in range(1,201):
            count += 1
            if gj + mj + xj == 100 and 3*gj + mj + 0.5*xj ==100:
                print(f'公鸡{gj}只，母鸡{mj}只，小鸡{xj}只，花费{3*gj + mj + 0.5*xj}')
                num += 1
print(num)
print(count)

2.2 输出结果与结果分析

# 输出结果
公鸡1只，母鸡95只，小鸡4只，花费100.0
公鸡2只，母鸡90只，小鸡8只，花费100.0
公鸡3只，母鸡85只，小鸡12只，花费100.0
公鸡4只，母鸡80只，小鸡16只，花费100.0
公鸡5只，母鸡75只，小鸡20只，花费100.0
公鸡6只，母鸡70只，小鸡24只，花费100.0
公鸡7只，母鸡65只，小鸡28只，花费100.0
公鸡8只，母鸡60只，小鸡32只，花费100.0
公鸡9只，母鸡55只，小鸡36只，花费100.0
公鸡10只，母鸡50只，小鸡40只，花费100.0
公鸡11只，母鸡45只，小鸡44只，花费100.0
公鸡12只，母鸡40只，小鸡48只，花费100.0
公鸡13只，母鸡35只，小鸡52只，花费100.0
公鸡14只，母鸡30只，小鸡56只，花费100.0
公鸡15只，母鸡25只，小鸡60只，花费100.0
公鸡16只，母鸡20只，小鸡64只，花费100.0
公鸡17只，母鸡15只，小鸡68只，花费100.0
公鸡18只，母鸡10只，小鸡72只，花费100.0
公鸡19只，母鸡5只，小鸡76只，花费100.0
20
660000

Amazing! 所有20种结果一目了然，计算机果然强大！
不过66000的计算量放在谁的身上都将是不可承受之重啊！那有没有给计算机减负的方法呢？

3 算法优化

较多的循环次数是首先要解决的问题，因此可行的方法是努力减少计算时循环的次数。通过分析上面的程序，结合题目的要求，我们发现当购买的鸡在总的数量为100的要求下，循环第一、二层循环之后，第三种鸡的数量可以直接通过三者的定量关系求出来。因此我们依据该思路对程序进行优化：

3.1 第一次优化

num = 1
count = 0
for gj in range(1,33):
    for mj in range(1,100):
        xj = 100-gj-mj          # 已知公鸡和母鸡的数量，小鸡的数量便可以直接求出来
        count += 1
        if gj + mj + xj == 100 and 3*gj + mj + 0.5*xj ==100:
            print(f'公鸡{gj}只，母鸡{mj}只，小鸡{xj}只，花费{3*gj + mj + 0.5*xj}')
            num += 1
print(num)
print(count)

# 输出结果
公鸡1只，母鸡95只，小鸡4只，花费100.0
公鸡2只，母鸡90只，小鸡8只，花费100.0
公鸡3只，母鸡85只，小鸡12只，花费100.0
公鸡4只，母鸡80只，小鸡16只，花费100.0
公鸡5只，母鸡75只，小鸡20只，花费100.0
公鸡6只，母鸡70只，小鸡24只，花费100.0
公鸡7只，母鸡65只，小鸡28只，花费100.0
公鸡8只，母鸡60只，小鸡32只，花费100.0
公鸡9只，母鸡55只，小鸡36只，花费100.0
公鸡10只，母鸡50只，小鸡40只，花费100.0
公鸡11只，母鸡45只，小鸡44只，花费100.0
公鸡12只，母鸡40只，小鸡48只，花费100.0
公鸡13只，母鸡35只，小鸡52只，花费100.0
公鸡14只，母鸡30只，小鸡56只，花费100.0
公鸡15只，母鸡25只，小鸡60只，花费100.0
公鸡16只，母鸡20只，小鸡64只，花费100.0
公鸡17只，母鸡15只，小鸡68只，花费100.0
公鸡18只，母鸡10只，小鸡72只，花费100.0
公鸡19只，母鸡5只，小鸡76只，花费100.0
20
3267

果然不出所料，循环次数由原来的66000次下降到了3267次，计算机听了都想夸我长得好看。虽然3267次的运算量对计算机来说就是小case。
但是对我们这些凡人来说依旧是不可承受之重啊！那有没有更为简单的方法，让我等凡人也可以欣然接受？

3.2 第2次优化

结合我们初中时候学习的数学知识，考试的时候遇到这种问题肯定要先设未知数，联立方程组，先拿点卷面过程分，至于方程有没有具体的解，能不能解出来之后再说！
因此，我们设公鸡、母鸡和小鸡的数量分别为x,y,z只，因此结合已知的等式和不等式关系，得到的方程组为：

x + y + z = 100(只)
3x + y + 0.5z = 100（元）
0< x ≤ 33，0 < y < 100, 0 < z < 200
先求解等式方程，得到变量之间的关系为：y=100-5x,z=4x,x=x(x,y,z都大于0)

# 代码实现
公鸡1只，母鸡95只，小鸡4只
公鸡2只，母鸡90只，小鸡8只
公鸡3只，母鸡85只，小鸡12只
公鸡4只，母鸡80只，小鸡16只
公鸡5只，母鸡75只，小鸡20只
公鸡6只，母鸡70只，小鸡24只
公鸡7只，母鸡65只，小鸡28只
公鸡8只，母鸡60只，小鸡32只
公鸡9只，母鸡55只，小鸡36只
公鸡10只，母鸡50只，小鸡40只
公鸡11只，母鸡45只，小鸡44只
公鸡12只，母鸡40只，小鸡48只
公鸡13只，母鸡35只，小鸡52只
公鸡14只，母鸡30只，小鸡56只
公鸡15只，母鸡25只，小鸡60只
公鸡16只，母鸡20只，小鸡64只
公鸡17只，母鸡15只，小鸡68只
公鸡18只，母鸡10只，小鸡72只
公鸡19只，母鸡5只，小鸡76只
20
19

Unbelievable! 计算量瞬间降到了 19 次，貌似是常人能理解的计算量了。看来初中学习的求解方程组的知识完胜计算机的简单暴力。
大喊一声：初中大法好！

总结

实现目的千千万，吾独钟情于走走捷径！初中大法好，好在计算方法使多变量成单一变量。计算机能力属实强，合理应用是关键，正所谓："他强任他强，明月照大江。"
好算法，你可愿意成为我心中的那一轮月光？