说一说那些我也不太懂的算法之《百钱买鸡》

百钱买鸡

百钱买鸡问题是一个数学问题，出自中国古代约5—6世纪成书的《张邱建算经》
：今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？
简单解释：公鸡 5 文钱一只、母鸡鸡 3 文钱一只，小鸡 1 文钱 三只，现用 100 文钱去买 100 只鸡，要求公鸡、母鸡、小鸡都要有，求有几种购买鸡的组合方式

小学生式解题思路：

设：购买公鸡 x 只，购买母鸡 y 只，购买小鸡 z 只

列方程组：

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

分析：

x 的取值范围 [1, 20)，y 的取值范围：[1, 33)

通过 Python 实现方程组求解

# coding: utf-8

def buy():
    for x in xrange(1,20):
        for y in xrange(1, 33):
            z = 100 - x - y
            if ((z % 3 == 0) and (5 * x + 3 * y + z / 3 == 100)):
                print "公鸡：", x
                print "母鸡：", y
                print "小鸡：", z
                print '*********************************'

回看上面这个算法，我们使用了 2 层循环，时间复杂度为：o(n^2)，那么我们有没有可能继续优化这个算法呢？毕竟在实际应用中，我们对算法的性能要求还是很高的。

消元法优化

1. 通过加减消元法消除: z

   x + y + z = 100
   5x + 3y + z/3 = 100
   
   3 * ( 5x + 3y + z/3 = 100 ) 得到 15x + 9y + z = 300
   （15x + 9y + z = 300） - （x + y + z = 100）得到 14x + 8y = 200
   y = 25 - (7/4)x
   

2. 通过代入消元法将化二元方程转化为一元方程

   y = 25 - (7/4)x
   # 为了消除分母， 我们假设： x = 4k
   x = 4k
   y = 25 - 7k
   z = 100 - x - y = 75 + 3k
   
   根据开始的要求分析： x 的取值范围 [1, 20)，y 的取值范围：[1, 33)，z 的取值范围：[1, 300) 的自然数。
   通过：
   x = 4k
   y = 25 -7k
   z = 75 + 3k
   y >= 1
   判断得出：k 的取值范围为 ：1,2,3
   

Python 实现 优化后的算法：

def  buy_optimize():
    # k 的取值范围为 ：1,2,3
    for k in xrange(1, 4):
        x = 4 * k
        y = 25 - 7 * k
        z = 75 + 3 * k

        print "公鸡：", x
        print "母鸡：", y
        print "小鸡：", z
        print '*********************************'

回看上面这个算法，我们只使用了 1 层循环，时间复杂度为：o(n)，性能有很大提升。

---