中职C语言中穷举法的编程方法探索

2023-01-24

在计算机编程语言的学习过程中, 我们会遇到一些穷举法的编程处理方法, 包括百钱百鸡问题、整钱化零问题、逻辑推理等等。当我们对这些问题进行分析时会发现, 它们中很多都可以用一种最原始的方法———穷举法来解决。而穷举法是最常用的一种方法, 是C语言中的一个重要知识点。本文主要以C语言编程为例, 对这些穷举法的编程方法进行探索, 希望给大家带来一定的帮助。

我们先来了解一下, 什么是穷举法。穷举法的基本思想是根据题目的部分条件确定答案的大致范围, 并在此范围内对所有可能的情况逐一验证, 直到全部情况验证完毕。下面通过几个实例, 来对穷举法编程处理方法进行探索。

1 百钱百鸡问题

例1:我国古代数学家张丘建在《算经》一书中提出的数学问题:鸡翁一值钱五, 鸡母一值钱三, 鸡雏三值钱一。百钱买百鸡, 问鸡翁、鸡母、鸡雏各几何?

分析:本题用数学列方程解应用题的方法, 3个未知数, 两个方程, 解决起来比较麻烦。在C语言中, 就是典型的穷举法的例子, 用100元来买鸡, 公鸡的数量 (用变量i表示) 的变化范围是0-20只, 母鸡的数量 (用变量j表示) 的变化范围是0-33只, 总共100只, 那么小鸡的数量 (用变量k表示) k=100-i-j, 知道了数量, 如果价钱正好是100元, 就是本题的答案。程序如下:

拓展:本题是3个未知数, 两个方程, 前两个未知数可以通过穷举的方法得到, 第三个未知数可以通过其中的一个方程解得, 另一个方程可以用来验证正确性。当然, 在本题中, 小鸡的数量也可穷举, 双100可以用来验证, 但这种算法让计算机循环的次数太多, 不够优化, 所以不提倡。类似的题目有很多, 如鸡兔同笼问题, 已知头的数目和脚的数目, 求鸡兔各有多少, 两个方程, 两个未知数, 答案唯一, 那么一个未知数用来穷举, 另一个未知数可以通过一个方程解得, 剩下的一个方程用来验证。

2 整钱化零问题

例2:将1元钱换成1角、2角、5角的零钱, 输出所有的换法。

分析:本题与上题的不同之处是, 本题只有一个限制条件就是10元, 对个数没有限制, 那么这个限制条件是用来验证的, 1角、2角、5角的数量必须通过穷举得到。程序如下:

拓展:如果需要兑换的整钱数额再大一些, 允许零钱的品种再多一点, 那就多加循环。类似的问题很多, 比如:?2*7?=3848, 等式中缺一个十位数和一个个位数, 编程求出这两个数。前一个数的十位数和后一个数的个位数都需要穷举, 等式满足即为找到。

3 逻辑推理问题

例3:甲、乙、丙、丁四人同时参加全国数学竞赛, 赛前甲乙丙分别做了预测:甲说:丙第一名, 我第三名。乙说:我第一名, 丁第四名。丙说:丁第二名, 我第三名。成绩揭晓后, 发现他们每人只对了一半, 输出他们的名次。

分析:这是小学逻辑推理问题, 人脑做起来相对简单。编程来讲, 可以用穷举法来解决, 也就是甲、乙、丙、丁四人都有可能1-4名 (名次不相同) 。具体是:甲 (用变量i表示) 名次范围1-4, 循环没问题;乙 (用变量j表示) 名次范围1-4, 与甲名次相同就跳过;丙 (用变量k表示) 的名次范围1-4, 与甲或乙相同就跳过;那么丁 (用变量m表示) 名次就是m=10-i-j-k (1、2、3、4名次各一, 总和是10) , 然后, 验证三人的答案, 答对一半可以用异或运算符 (^) 来计算。程序如下:

拓展:类似的逻辑推理题目很多, 要考虑的问题也很多, 本题中就考虑了不重复以及答对一半的判断方法, 用了多次循环和判断。这类问题解决方法, 就是充分考虑各种可能性, 有效用好其中的条件, 那么解决起来就简单了。

以上穷举法的处理方法是中职学生在实际应用中, 经常遇到的, 主要考查学生对循环和分支语句的灵活运用。它是把各种可能性充分过滤一遍, 从中找出符合条件的, 这是一种比较“笨”的方法, 是“没有办法的办法”, 很适用, 需要大家平时多注意积累, 多动脑筋, 中职学生包括广大编程爱好者要多总结, 从而对循环及分支语句的使用能有进一步的了解。

摘要:在计算机编程语言的学习过程中, 我们会遇到穷举法的编程处理方法, 包括百钱百鸡问题、整钱化零问题、逻辑推理等等。本文主要以C语言编程为例, 对穷举法的编程方法进行探索, 让大家对循环语句和分支语句有进一步的了解。

关键词:C语言,穷举法

参考文献

[1] 李秉璋.C语言程序设计与训练[M].大连理工大学出版社, 2011.

[2] 石远东.计算机专业综合理论复习用书 (上册) 第二版[M].原子能出版社, 2007.