python百钱买百鸡问题答案_python 百钱买百鸡 算法的重要性

百钱买百鸡：现有100钱，公鸡5文钱一只，母鸡3文钱一只，小鸡一文钱3只

要求：公鸡、母鸡，小鸡都要有，把100文钱花完，买的鸡的数量正好是100。

问：一共能买多少只公鸡，多少只母鸡，多少只小鸡？

穷举法：

方案一：

思路：

第一重循环公鸡从1只循环到100只

第二重循环母鸡从1只循环到100只

第三重循环小鸡从1只循环到100只

然后进行判断：

数量：公鸡+母鸡+小鸡 =100

钱：公鸡*5+母鸡*3+小鸡 =100

输出满足条件的情况

代码如下：for cock in range(1,101): # 公鸡

for hen in range(1,101): #母鸡

for chick in range(1,101): #小鸡

if cock * 5 + hen * 3 + chick == 100:

if cock + hen + chick * 3 == 100:

print("公鸡有%d只\t母鸡有%d只\t小鸡有%d只"%(cock,hen,chick * 3))

输出：

公鸡有4只 母鸡有18只 小鸡有78只

公鸡有8只 母鸡有11只 小鸡有81只

公鸡有12只 母鸡有4只 小鸡有84只

虽然能求出结果，但仔细一想，用了三重循环，每重循环要执行100次，三重就是100*100*100，太耗时间了，能不能有一种更好的解决方法呢？

方案二：

思路：买了一只公鸡，花掉5钱，还剩下100 - 5 = 95 钱，买母鸡和小鸡的钱只有95钱，而不是100钱。再买一只母鸡，还剩下100- 5 - 3 = 92钱，那么买小鸡的钱只有92钱……所以每重循坏次数不再是固定的100，而是变化的。

第一重 cock：100 / 5 = 20 次

第二重 hen：(100 - cock) / 3次

第三重：100 - cock -hen 次

代码如下：for cock in range(5,101,5): # 公鸡

for hen in range(3,101 - cock,3): #母鸡

for chick in range(1,101 - cock - hen): #小鸡

if cock // 5 + hen // 3 + chick * 3 == 100 and cock + hen + chick == 100:

print("公鸡有%d只\t母鸡有%d只\t小鸡有%d只" % (cock // 5, hen // 3, chick * 3))

下面做一个时间对比：import time

start = time.clock()

for cock in range(1,101): # 公鸡

for hen in range(1,101): #母鸡

for chick in range(1,101): #小鸡

if cock * 5 + hen * 3 + chick == 100 and cock + hen + chick * 3 == 100:

pass

end = time.clock()

time1 = end - start

print("方案一所花时间",time1)

start = time.clock()

for cock in range(5,101,5): # 公鸡

for hen in range(3,101 - cock,3): #母鸡

for chick in range(1,101 - cock - hen): #小鸡

if cock // 5 + hen // 3 + chick * 3 == 100 and cock + hen + chick == 100:

pass

end = time.clock()

time2 = end - start

print("方案二所花时间",time2)

print("方案一所花时间是方案二的%d倍"%(time1 // time2))

输出：

方案一所花时间 0.32884016429388524

方案二所花时间 0.0030011999201297046

方案一所花时间是方案二的109倍

经过多次测试，方案一所花时间差不多是方案二的100倍。

这个小小的程序可以说明算法的重要姓，用不同的算法，时间复杂度是不一样的。在实现一个功能的基础上，还要兼顾效率的问题。

当然这个题目还可以用求不定方程整数解的办法来解决，这个算法用时会更短。

本博客源码Github地址：

请随手给个star，谢谢！