C语言程序设计基础：穷举方法程序设计

2023-11-20 理论教育版权反馈

【摘要】：在程序设计中，许多问题的解“隐藏”在多个可能之中。在一个集合内对集合中的每一个元素进行一一测试的方法称为穷举法。穷举方法的实现主要依赖于以下两个基本要点：·搜寻可能值的范围如何确定。程序设计中应据问题的描述具体分析，确定时应尽量缩小搜索范围，提高程序效率。编写程序找出所有的“水仙花数”。程序可以依次取出区间［100，999］之间的每一个数，然后将该数分解为3个数字，按照判定条件判定即可。

在程序设计中，许多问题的解“隐藏”在多个可能之中。穷举就是对多种可能的情形一一测试，从众多的可能中找出符合条件的（一个或一组）解或者得出无解的结论。在一个集合内对集合中的每一个元素进行一一测试的方法称为穷举法。穷举本质上就是在某个特定范围中的查找，是一种典型的重复型算法，其重复操作（循环体）的核心是对问题的一种可能状态的测试。穷举方法的实现主要依赖于以下两个基本要点：

·搜寻可能值的范围如何确定。

·被搜寻可能值的判定方法。

对于“被搜寻值”的判定，一般都是问题中所要查找的对象或者要查找对象应该满足的条件，在问题中都会有清晰的描述。但对于搜寻范围，有些问题比较确定，而另外一些问题则不确定。程序设计中应据问题的描述具体分析，确定时应尽量缩小搜索范围，提高程序效率。

【例4.9】　编写程序找出所有的“水仙花数”。“水仙花数”是指一个3位数，其各位上数字的立方之和等于这个数本身。如153＝13+53+33，所以153是“水仙花数”。

题目分析：这是一个典型的搜寻范围已定的穷举问题。依题意可以得出，搜寻可能值的范围为100～999；判定方法为各位上数字的立方之和等于被判定数。程序可以依次取出区间［100，999］之间的每一个数，然后将该数分解为3个数字，按照判定条件判定即可。

上面求取“水仙花数”的方法可以称为分离数据法，除此之外还可以使用组合数据的方法求取“水仙花数”。如果用a、b和c分别表示3位数的百位、十位和个位，则该3位数可以表示为：a*100+b*10+c，其中a的变化范围为［1，9］，b和c的变化范围均为［0，9］。使用3重循环结构，每层循环分别控制a、b和c的变化，组合出所有的3位数参加判断即可。(www.chuimin.cn)

【例4.10】　搬砖问题：36块砖，36人搬，男人一次可搬4块砖，女人一次可搬3块砖，两个小孩一次可抬1块砖。要求将所有的砖一次搬完，问需要男人、女人、小孩各多少人？

题目分析：这是一个典型的搜寻范围需要分析确定的穷举问题。

设男人、女人、小孩的数量分别为man、woman、child，依题意可以得出被搜寻值的判定方法可以用下式表示：4*man+3*woman+0.5*child＝36。

对于搜寻的范围，按照常识简单划分，men、women、child都应该为整数，而且男人的数量应该少于9人（36／4），女人的数量应该少于12人（36／3），当男人数量和女人数量一定的情况下小孩的数量可以用算式children＝36-men-women＆＆child%2＝＝0来确定。由此可以简单地确定搜寻范围表示如下：

程序中通过表达式（4*man+3*woman+child／2.0）＝＝36保证小孩人数为偶数，该表达式左边4*man+3*woman+child／2.0是实数，比较运算时右边的36自动转换为实数（36.0）进行比较，如果相等关系成立则表示左边表达式值的小数部分也为0，从而保证了小孩数一定是偶数。程序执行的输出结果为：

man＝3 woman＝3 child＝30

C语言程序设计基础：穷举方法程序设计

相关推荐