首页 > 代码库 > 百钱百鸡,用高中数学优化算法
百钱百鸡,用高中数学优化算法
背景介绍
学习算法的道路上总会有各种各样的感受,偶然间碰到一个源自我国的算法问题,百钱百鸡
问题,貌似很经典的问题了,可是我才刚刚知道,感觉自己太LOW
了。题目是出自古代的一本叫做算经
的书,原文是文言文就不往出贴了,贴了也看不懂,说大家能听懂的话就是:
有公鸡,母鸡,小鸡三种鸡,公鸡5块钱一只,母鸡三块钱一只,小鸡一块钱三只,要求用一百块钱买上面三种鸡(都要有),并且三种鸡总数是一百只,要求所有的解法。
分析
在感叹古人物价的同时,思考题目,其实很简单,只需要满足两个条件:
公鸡
+母鸡
+小鸡
= 100
买公鸡的钱
+买母鸡的钱
+买小鸡的钱
= 100
只需要满足上面两个条件即可,循环嵌套然后做判断就OK了,突然有了上大学Java期末考试时候的感觉。
写代码
因为有了上学时候的亲切感,所以就先使用Java
来实现这段代码吧:
public class MoneyBuyChicken { public static void main(String[] args) { // 定义各种鸡的价钱 int GONG_JI = 5; int MU_JI = 3; int XIAO_JI = 1/3; // 100块钱最多能卖20只公鸡而且要求各种鸡都要有 // 所以 公鸡的数量是小于20只的 for(int i = 1; i < 20; i++) { // 和公鸡同理,母鸡最多的数量为33只 for(int j = 1; j < 33; j++) { //计算出当前状态下小鸡的数量和剩下的钱 int remainMoney = 100 - (i * GONG_JI + j * MU_JI); int xiaoJiCount = remainMoney * 3; // 对需要满足的条件做判断 if(xiaoJiCount > 0 && i + j + xiaoJiCount == 100) { System.out.printf("公鸡%d只,母鸡%d值,小鸡%d只\n", i, j, xiaoJiCount); } } } }}
运行上述代码,得到结果:
公鸡4只,母鸡18值,小鸡78只
公鸡8只,母鸡11值,小鸡81只
公鸡12只,母鸡4值,小鸡84只
这在只检查结果的考试中已经OK了,交卷走人!但是,当我们看下这个算法的性能的时候,很明显就可以看到其中的问题。
上述代码使用了两层嵌套,那么它的时间复杂度为O(n^2)
,这个在我们的应用中基本是不可以接受的,虽然从100只鸡中体现不出性能问题,但是如果在量级很大的地方性能问题就很明显了,所以站在学习的角度上,必须对这个进行优化。
思考
现在想想,这样的题目,貌似使我们初中奥数,或者高中数学中很常见的题目,回想当时的方法,得出了以下三元一次方程组
,通过解方程组可以得到三种鸡之间的关系:
设:公鸡数量为x, 母鸡数量为y, 小鸡数量为z则: 5x + 3y + z/3 = 100 ① x + y + z = 100 ②解: 将①的等式两边都乘以3可以到的下列等式 15x + 9y + z = 300 ③ 将③-②可以得到以下等式 14x + 8y = 200 通过上面等式进而可以得到 y = (200 - 14x) / 8 ④ 同理将②的等式两边同时乘以3得到的等式减去①可以得到下列等式 8z/3 - 2x = 200 进而可以得到 z = (600 + 6x) / 8 ⑤
至此已经得出了y(母鸡)
,z(小鸡)
和x(公鸡)
之间的转化关系。~~(看着上面的解方程步骤感觉好亲切,虽然当时可能都不会写)
优化算法
上面我们通过数学方程的知识得到了三种鸡之间的关系,那么我们把这个结果应用到我们的代码中进行优化:
public class MoneyBuyChickenOptimize { public static void main(String[] args) { // 定义各种鸡的价钱 int GONG_JI = 5; int MU_JI = 3; int XIAO_JI = 1/3; // 100块钱最多能卖20只公鸡而且要求各种鸡都要有 // 所以 公鸡的数量是小于20只的 for(int i = 1; i < 20; i++) { // 将方程式中推导的结果带入得到各种鸡的数量 int gongJiCount = i; // 公鸡数量 int muJiCount = (200 - 14 * i) / 8; // 母鸡数量 int xiaoJiCount = (600 + 6 * i) / 8; // 小鸡数量 // 判定条件 if(muJiCount > 0 && xiaoJiCount > 0 && gongJiCount + muJiCount + xiaoJiCount == 100) { System.out.printf("公鸡%d只,母鸡%d值,小鸡%d只\n", gongJiCount, muJiCount, xiaoJiCount); } } }}
完成,上述代码时间复杂度为O(n)
,比之前的性能提升了很多,我们的目标也就达成了。
结束语
和上学时候的感觉一样,觉得学校学习的东西没有什么用;而这样一道题也一样,在工作中没有人会让写一个百钱百鸡的问题,但是我们应该从中了解到数学对于算法的帮助,在算法中有好多好的方法是不容易直接想到的,但是和这里一样,通过简单的高中数学思考一下,效果就完全不一样了。
本文由kenticny原创文章
转载请注明原文出处
http://www.cnblogs.com/kenticny/p/5932728.html
http://lyitlove.com/bai-qian-bai-ji-yong-gao-zhong-shu-xue-you-hua-suan-fa/
百钱百鸡,用高中数学优化算法