美文网首页Python 指南程序员首页投稿(暂停使用,暂停投稿)
说一说那些我也不太懂的算法之《百钱买鸡》

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

作者: 谢烟客 | 来源:发表于2017-12-01 16:06 被阅读128次

百钱买鸡

百钱买鸡问题是一个数学问题,出自中国古代约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),性能有很大提升。


相关文章

网友评论

  • x_zhaohu:简书主页的审核人员还是多点程序员好呀!
    谢烟客:@x_zhaohu 有一定道理👍
  • shanggl:膜拜一下
    谢烟客:从小学方程组开始复习:stuck_out_tongue_winking_eye:

本文标题:说一说那些我也不太懂的算法之《百钱买鸡》

本文链接:https://www.haomeiwen.com/subject/kjxwbxtx.html