求解“百钱百鸡”问题的最优化算法

苏 琳

(山东科技大学 土木工程与建筑学院, 山东 青岛 266000 )

求解“百钱百鸡”问题的最优化算法

苏 琳

(山东科技大学 土木工程与建筑学院, 山东 青岛 266000 )

“百钱百鸡”问题是一个经典的穷举问题，虽然该问题比较简单，但是目前的算法并没有实现求解过程的最优化。本文充分利用数学模型中的隐含条件，减少未知量的个数，有效控制循环变量的范围与步长来优化循环次数，最终循环执行4次即可求解，使得算法的时间复杂度从降为，达到算法的最优化，为穷举类问题的求解提供一种新的思路。

穷举算法；百钱百鸡；优化；Matlab

1 概述

穷举法也称为枚举法，这种算法是把问题涉及的可能情况一一罗列出来，并且根据题目的条件和实际背景逐个给予判断，从中挑选出符合条件的解答。它适用的条件是：暂时找不出解决问题的更好途径的情况下；有明显的穷举范围且求解对象应该是有限的；可以按某种穷举规则列举对象[1]。在很多数学问题求解中，穷举法作为一种试探求解的方法有着广泛的应用[2]。

“百钱百鸡”问题是一个很经典的穷举问题。公元前5世纪，我国古代数学家张丘建在《算经》中提出：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何[3]？

在现行的计算机高级语言编程中，经常引用这个数学问题进行循环结构的讲解。在算法的设计中，时间复杂度有的是，也有的是,循环执行的次数有多达上万次，小则数百次[4]。本文在进一步分析隐含条件的基础上，提出一种新的穷举算法，在求解正确的前提下，使算法复杂度仅为,循环执行4次即可求解，最大程度地优化了问题的求解过程，并通过Matlab给出了算法实现[5]。

2 现行的求解算法

现行的求解算法主要有两种，一种是利用三重循环结构来实现的，另一种是利用二重循环结构来实现的，无论采用那一种算法都是基于下面的数学分析。

设鸡翁、鸡母、鸡雏的个数分别为x、y、z,由题意可得到下面的方程组：

题意要求用100钱买100只鸡，若全买公鸡最多买20只，显然x的值在0-20之间；同理，y的值在0-33之间，z的值在0-100之间。因此，x、y、z可能的组合方式有21*34*101=72114 种，对每一种组合方式，再测试是否符合“百钱、百鸡”这两个条件；若符合，则该组合就是问题的一个解。

上述思想可编写MATLAB程序如下：

clc;

clear all;

for cock=0:20

for hen=0:33

for chicken=0:100

if (5*cock+3*hen+chicken/3==100)&&(cock+hen+chick en==100)

[cock,hen,chicken]

end

end

end

end

对于上述求解我们称为算法1，该算法在一般的教科书中都有陈述，很明显该算法的时间复杂度为，最内层的if语句被执行了72114次。在答案仅有4中组合的情况下，将有72110次是无意义的重复执行，极大浪费了系统资源。

为了提高效率，减少循环次数，利用百鸡条件，有些研究者将上述算法进行了简单优化，变三重循环为二重循环，改进后的算法描述如下：

clc;

clear all;

for cock=0:20

for hen=0:33

chicken=100-cock-hen;

if (5*cock+3*hen+chicken/3==100)

[cock,hen,chicken]

end

end

end

对于上述求解方法我们称为算法2，该算法的时间复杂度为，最内层的if语句被执行了714次，与算法1相比执行次数明显减少，该算法是目前为止比较好的，也得到众多学者的赏识；但是，循环次数还是比较多的。

3 改进的穷举算法

为了进一步减少循环次数，我们从改变循环结构的循环重数、精确计算循环增量两个角度进行优化。

3.1 改变循环结构的重数

通过分析算法1、算法2知，循环重数是由未知数的数量决定的，减少未知数可以减少循环的重数，为此我们利用消元法将方程组化简以减少未知数，再用假设的变量来表示未知数，这样可以改变循环结构。

首先，将方程组(1)的式*3-(2)式，得：

即：

这样就可以用变量x表示变量y，改变算法2的二重循环为单层循环。

3.2 循环变量的范围与步长的精确设置

因为y≥0，且y为整数，所以25-7x/4≥0，即x≤1（当x=13时，不能使y为整数）

另由(3)式知，x必须为数4的整数才能使y为整数，所以在x初值为0时取其步长为4。

综合以上优化分析，提出新的穷举算法如下：

clc;

clear all;

for cock=0:4:12

hen=25-(cock/4)*7;

chicken=100-cock-hen;

[cock,hen,chicken]

end

4 结果分析为了比较算法的优劣，我们将所提新算法称为算法3，该算法在进一步分析隐含条件的基础上，继续消元，真正改变多重循环为单重循环，减少了时间复杂度，具体对比分析如表1所示。

表1 算法结果对比

通过对比可以发现，无论在时间复杂度还是在循环次数上，本文所提出的算法3都达到最优化状态（“百钱百鸡”问题有4中解），这为我们求解类似的穷举问题提供了一个很好的思路：应充分挖掘和利用已知条件，寻找隐含条件因素来限制穷举的次数以提高求解效率。

[1]李巍,徐爱功,赵亮,王昶,高良博.基于Matlab的测量坐标系统转换[J].煤炭学报,2014,39(01):88-92.

[2]吴文肖.穷举法在确定带电粒子在磁场中轨迹的应用[J].物理教学探讨,2017,35(500):36-38.

[3]黄隆华,陈志辉.算法设计与分析课程的“百钱买百鸡问题”趣用[J].计算机教育,2016(03):143-145.

[4]R.VenkataRao,G.G.Waghmare.A New Optimization Algorithm for Solving Complex Constrained Design Optimization Problems[J].Engineering Optimization,2017,49(01):60-83.

[5]呼娜.浅谈如何激发学习高等数学的兴趣[J].山东工业技术,2016(03):220.

10.16640/j.cnki.37-1222/t.2018.01.197

国家自然科学基金面上项目（61771231）

苏琳(1998-),女,山东栖霞人,本科,助教,研究方向：主要从事优化设计、材料力学等方面的研究。