求解“百钱百鸡”问题的最优化算法
2018-01-02苏琳
山东工业技术 2018年1期
关键词:优化
苏 琳
(山东科技大学 土木工程与建筑学院, 山东 青岛 266000 )
求解“百钱百鸡”问题的最优化算法
苏 琳
(山东科技大学 土木工程与建筑学院, 山东 青岛 266000 )
“百钱百鸡”问题是一个经典的穷举问题,虽然该问题比较简单,但是目前的算法并没有实现求解过程的最优化。本文充分利用数学模型中的隐含条件,减少未知量的个数,有效控制循环变量的范围与步长来优化循环次数,最终循环执行4次即可求解,使得算法的时间复杂度从降为,达到算法的最优化,为穷举类问题的求解提供一种新的思路。
穷举算法;百钱百鸡;优化;Matlab
1 概述
穷举法也称为枚举法,这种算法是把问题涉及的可能情况一一罗列出来,并且根据题目的条件和实际背景逐个给予判断,从中挑选出符合条件的解答。它适用的条件是:暂时找不出解决问题的更好途径的情况下;有明显的穷举范围且求解对象应该是有限的;可以按某种穷举规则列举对象[1]。在很多数学问题求解中,穷举法作为一种试探求解的方法有着广泛的应用[2]。
“百钱百鸡”问题是一个很经典的穷举问题。公元前5世纪,我国古代数学家张丘建在《算经》中提出:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、母、雏各几何[3]?
在现行的计算机高级语言编程中,经常引用这个数学问题进行循环结构的讲解。在算法的设计中,时间复杂度有的是,也有的是,循环执行的次数有多达上万次,小则数百次[4]。本文在进一步分析隐含条件的基础上,提出一种新的穷举算法,在求解正确的前提下,使算法复杂度仅为,循环执行4次即可求解,最大程度地优化了问题的求解过程,并通过Matlab给出了算法实现[5]。……
登录APP查看全文
