猫史档案馆

这次，我们来解决百鸡百钱问题。百鸡百钱问题是在《算经》中提到，问题是：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，则翁、母、雏各几何？

看到这个问题时，我们先用普通算法。

#公鸡（gj）
#母鸡（mj）
#小鸡（xj）
#i 计算机算的次数
i=0
for gj in range(101):
    for mj in range(101):
        for xj in range(101):
            i=i+1
            if gj+mj+xj==100 and gj*5+mj*3+xj/3==100:
                print(gj,mj,xj)
print(i)

运行之后，我们会发现，这个程序计算机要算1030301，大约103万次，有没有更简洁的算法呢？

第一次，我们简化小鸡的次数，公鸡母鸡都求出来了，那就用100-公鸡和母鸡就得到了小鸡。

xj = 100-(gj+mj)

这一段代码可以替换  " for xj in range(101): "也可以删除    " gj+mj+xj==100 "

第2次,我们再一次简化小鸡，如果小鸡可以被3整除，那么小鸡也有可能成功。

if xj%3==0:

加到第一次之后。

第3次，我们看公鸡和母鸡，公鸡最高是100//5只，母鸡最高是100//3。所以，我们把for循环中的公鸡参数设100//5+1,for循环中是到参数以下的，所以要加一。

来看一下修改三次后的代码

i=0
for gj in range(100//5+1):
    for mj in range((100-gj*5)//3+1):
        xj=100-(gj+mj)
        if xj%3==0:
            i+=1
            if  gj*5+mj*3+xj/3==100:
                print(gj,mj,xj)
print(i)

这一次，计算机计算的次数只有238次，让我们在来简化。

第三行，我们可以把100先减去公鸡的值，在除以3。

这样第三行就成了

for mj in range((100-gj*5)//3+1):

这样，是不是最简了？121次？

我用”不“字来回答你。

我们用数学方程来解决一下这个问题。

x=公鸡

y=母鸡

z=小鸡

方程：

                               5x+3y+1/3z=100

             解： 3*5x+3*3y+3*1/3z=100*3

                 15x+9y+100-x-y-100=300-100

                                      14x+8y=200

                                14x/2+8y/2=200/2

                                        7x+4y=100

以这个方程，我们列出以下代码

i=0
for gj in range(100//7+1):
    i+=1
    if (100-gj*7)%4==0:
        mj=(100-gj*7)//4
        print(gj,mj,100-gj-mj)
print("计算机算了"+str(i)+"次")

你可以用海龟运行一下，发现了什么？

没错！15次！

从103万次到15次，从普通算发到高级算法！

还等什么？快关注我， 炼金树枝吧！