基于枚举算法的优化方法研究

梁 潘

（阿坝师范高等专科学校电子信息工程系，四川郫县 611741）

引 言

著名计算机科学家沃思（Nikiklaus Wirth）曾提出一个公式“数据结构+算法=程序”，实际上算法是程序的灵魂.[1]在程序设计中经常使用的算法有：枚举算法、递归算法、二分算法、贪心算法、二叉树算法等.枚举法，常常称之为穷举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的，能使命题成立者，即为问题的解，其优点是算法简单，结果准确、全面，在解决众多实际问题中被广泛使用，[2]但枚举法效率不高，为了更好地发挥它的优点，编写出高效的程序，必须对其进行优化，下面以“百钱百鸡”问题为例，分析使用枚举算法的程序的优化思路与方法.

1 枚举法

公元前5世纪，我国古代数学家张丘建在《算经》一书中提出了百鸡问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一.百钱买百鸡，问鸡翁、母、雏各几何?

1.1 传统枚举算法（算法一）

从数学分析来看，设变量cock、hen、chick分别代表鸡翁、鸡母、鸡雏，可以构建两个三元一次方程组：

1）cock + hen + chick = 100，2）cock*5 + hen*3 + chick/3 = 100，求cock、hen、chick的解，根据枚举法的特点结合题意，此题很显然使用枚举法，对鸡翁、鸡母、鸡雏的可能只数逐一进行测试，直到全部可能只数都试完为止.

通过分析，三个变量的取值范围是：0≤cock≤20，0≤hen≤33，0≤chick≤100，这样，cock、hen、chick的可能组合方式就有21*34*101 = 72 114种，对每一种组合再测试是否符合“百钱、百鸡”这两个条件，若符合，则该组合就是问题的一个解，[3]图1为算法一N-S流程图.

基于C语言的核心代码如下：

图1 ：算法一N--SS流程图

1.2 利用加强约束条件改进的枚举算法（算法二）

从上面的算法及C程序来看，虽然能够计算出每一个解，但是效率比较低，此时可以利用加强约束条件的方法改进枚举算法.由题可知，三种鸡的和恒为100，只要枚举两种鸡（cock，hen），第三种鸡（chick）就可以根据约束条件求得，由cock + hen + chick = 100方程可得chick = 100 - cock -hen，这样就可减少一层枚举循环缩小了搜索范围，cock、hen、chick的可能组合方式就只有21*34 = 714种，其组合方式不及传统枚举法的 1%，大大提高了程序的工作效率，[4]图2为算法二N-S流程图.

改进后的核心代码如下：

图2 ：算法二N-S流程图

1.3 利用数学分析改进的枚举算法（算法三）

在利用枚举算法解决实际问题的过程中，经常利用数学分析方法化简方程式，进一步减少枚举的次数提高工作效率.根据题意得到方程（1）cock + hen + chick = 100;（2）cock*5 + hen*3 + chick/3 = 100，观察其特点，消去一个未知数chick，得到一个二元一次方程：cock*7 + hen*4 = 100，通过分析，可进一步缩小两个变量的取值范围是：0≤cock≤14，0≤hen≤25；同时由该方程得到 hen = (100-cock*7)/4，因此，只要枚举cock就可根据约束条件求得hen和chick，进而将两层循环改进为单层循环，这样再次缩小了枚举范围，cock、hen、chick的可能组合方式就只有15种，极大的提高了程序的执行效率，算法三N-S流程图如图3.

改进后的核心代码如下：

图3 ：算法三N--SS流程图

2 结果比较

通过表1可以看出，三种程序使用不同的算法，但得到了相同的运行结果，经过改进后的算法枚举次数明显减少，时间复杂度也由O(n3)降低到O(n)，对循环工作量产生了极大的影响，程序的执行效率迥然不同，后面两个特别是第三个程序执行效率明显提高.

表1 各种算法比较结构图

3 结束语

程序=算法设计+数据结构+程序设计方法+语言工具，[1]从中我们可以看出，算法设计是整个程序设计的核心和灵魂，是解决实际问题的重要方法和步骤.在使用枚举算法解决实际问题时要想提高程序的执行效率，增强程序的可理解性和可读性，必须精心设计、优化算法，从研究效果看加强约束条件缩小枚举范围，结合数学分析减少循环嵌套正是行之有效的优化枚举算法的方法.

[1]谭浩强.C语言程序设计（第二版）[M].北京：清华大学出版社，2002.

[2]林小茶.C语言程序设计[M].北京：中国铁道出版社，2004.

[3]刘金祥.从“百钱百鸡”问题看如何进行 C语言程序设计[J].电脑学习，2007（5）：59-60.

[4]应进平.浅谈 C语言程序设计中算法设计的作用[J].科技情报开发与经济，2006（24）：261.