智一面的面试题提供python的测试题
使用地址：http://www.gtalent.cn/exam/interview?token=09b2a6b63e829ef00c112d80fe78d1df
现有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次，三重就是100100100，太耗时间了，能不能有一种更好的解决方法呢？
方案二：
思路：买了一只公鸡，花掉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倍。
这个小小的程序可以说明算法的重要性，用不同的算法，时间复杂度是不一样的。在实现一个功能的基础上，还要兼顾效率的问题。
当然这个题目还可以用求不定方程整数解的办法来解决，这个算法用时会更短。
————————————————
我们的python技术交流群：941108876
智一面的面试题提供python的测试题
使用地址：http://www.gtalent.cn/exam/interview?token=c7dcd205a4fdab0d6e8ca200b31b3489