5.5　循环的嵌套与穷举法

5.5.1　循环的嵌套

循环语句的循环体也是循环语句或循环体中有循环语句的情况叫做循环嵌套。例如：

程序代码5-13

这段代码的执行过程如下。

首先求表达式i=0的值，这个值被放弃，副效应是i值变成了0。

求表达式i<3的值，由于这个值为1因而执行内层的循环语句。

求表达式j='A'的值，副效应是j值变成了65（'A'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句，输出0A。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了66（'B'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句输出0B。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了67（'C'）。

求表达式j<'C'的值，由于这个值为0因而内层循环语句结束。

求表达式i＋＋的值，这个值被放弃，副效应是i值变成了1。

求表达式i<3的值，由于这个值为1因而执行内层的循环语句。

求表达式j='A'的值，副效应是j值变成了65（'A'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句，输出1A。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了66（'B'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句输出1B。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了67（'C'）。

求表达式j<'C'的值，由于这个值为0因而内层循环语句结束。

求表达式i＋＋的值，这个值被放弃，副效应是i值变成了2。

求表达式i<3的值，由于这个值为1因而执行内层的循环语句。

求表达式j='A'的值，副效应是j值变成了65（'A'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句，输出2A。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了66（'B'）。

求表达式j<'C'的值，由于这个值为1因而执行内层的printf()函数调用语句输出2B。

求表达式j＋＋的值，这个值被放弃，副效应是j值变成了67（'C'）。

求表达式j<'C'的值，由于这个值为0因而内层循环语句结束。

求表达式i＋＋的值，这个值被放弃，副效应是i值变成了3。

求表达式i<3的值，由于这个值为0因而外层循环语句结束。

最后的输出是：

总的来说，程序执行的是外部的循环语句，在满足循环条件时，执行内部的循环语句，内部循环语句结束后继续执行外部循环语句，这可能会导致两种可能性：内部循环语句的再次执行或外部循环语句的结束。

因此，循环语句的嵌套从总的来说只是一个循环语句，但循环体内的任务又构成了另一个循环。由于这种本性，循环嵌套特别适宜描述使用这种方式解决问题方法的算法。例如，一程序要求在屏幕上输出乘法口诀表，从较为宏观的角度看，无非是一行一行的输出，一共输出9行。毫无疑问这是一个循环。用伪代码的描述可以是：

继续分析“输出一行”会发现其本质是输出若干列，而当前输出的列数取决于当时是在输出第几行，也就是说列数是当时行数的函数。这样“输出一行”的伪代码就是：

至此，不难写出程序代码。

程序代码5-14

练习

编程输出所有十位数为2、3、4之一的正偶数。

5.5.2　穷举法

所谓穷举法，泛指一类算法，即当问题的解属于一个有限集（穷的本意是有限个），把有限集中的所有元素一一罗列（举）出来，找出符合条件的解。用通俗的话来讲，想要知道一篮子鸡蛋中有哪些是坏蛋，一个一个拿出来看一下也就是的了。

下面是个美国小学数学奥林匹克竞赛的题目：一次数学测验共10道题，每做对一题得5分，每做错一题扣2分。史迪夫完成了全部10道题，共得29分。他做对了多少道题？

由于只有10道题目，所以史迪夫可能做对0道、1道……10道，这是一个有限集，解必然在其中。相应地他做错的题目可能是10-0道、10-1道……10-10道，他的分数也就是（做对的题目数）×5－（做错的题目数）×2。把所有的情况都计算一遍，看哪种情况下分数为29分，就可以找到答案。

程序代码5-15

结果如下：

穷举法看起来似乎很笨拙，然而十分有效。很多喜欢数学的人更迷恋数学公式，实际上数学公式所能解决的问题其实是有限的。在代码中应用数学的结论可能会提高程序的效率，但在数学无能为力的时候，管用的往往是这种朴素的思想方法。这种方法发挥了计算机内存比人脑大、计算速度比人类快的特点。

有时候问题的解的范围是受到多种因素联合制约的，换句话说，解是一个多种有限因素条件下的集合，这时候往往可以用循环的嵌套来给出解的结合。

比如这样一个问题，一角钱人民币换成零钱一共有多少种换法？一方面一角钱人民币只能换成1分、二分、五分3个币种（有限），另一方面1分、二分、五分的个数最多为10个、5个、2个（3种有限集合），符合要求的解属于其组合所构成的有限集。在这个思路下可以写出下面的代码。

程序代码5-16

结果如下：

由于1角能兑换零钱的种数不多，所以应该很容易验证结果的正确性，请读者自己验证。

由于穷举法需要根据问题给出的特定条件来判断是否是解，所以善于写出正确的判断表达式在穷举法中特别重要。C语言的表达式的表达能力特别强也特别灵活。

例题：某地发生一起凶杀案，凶手是a、b、c、d、e、f中某一人。L说不是a就是b，M说决不是c，N说案发时a、b都不在场。已知L、M、N中只有一人正确，请问谁是凶手。

如果用1表示某人是凶手、0表示不是，那么显然a、b、c、d、e、f的值显然只能为0或1，这样很容易列出所有可能。同时可以很方便地表示出L、M、N的判断是否正确，比如L的判断可以表示为（(a==1)‖(b==1)）&&(a !=b)，或者更简化地表示为a+b==1。当L的判断成立时，表达式a+b==1的值为1，否则为0。

程序代码5-17

结果如下：

对于我来说，表达式a?'a':b?'b':c?'c':d?'d':e?'e':'f'用得恰倒好处且极其自然简洁⁽³⁾，但我可能忽视了您的阅读感受。如果您阅读感到困难，请把它当作一个对表达式进行分析及对运算符结合性理解的一个练习。如果实在难以理解，把那句话换成另一种容易理解的语句（比如switch语句）输出结果也可以。

在应用循环嵌套这种结构写代码时，有一个问题特别需要注意。那就是多数情况下不要在循环体内改变循环变量的值。这是一个比较禁忌的做法（不是说绝对不可以，语法上没有任何问题）。在循环嵌套时，有时在内层循环时有时可能需要使用外层循环变量的值，但是否要改变这个值是要特别注意的，如果不希望改变，最好使用外层循环变量值的一个拷贝。外层循环变量名取得不好、含义不清晰时，初学者特别容易在内层直接使用外层循环变量名并改变它，而造成代码的逻辑错误。限于篇幅这里就不举例了。

学习完全部控制语句，理论上来说可以写任何程序了（其实有了if和goto就足以写出任何程序了），但还不是质量很好的程序。下一篇介绍如何把程序写得更好。

练习

1．一元人民币换成零钱有多少种兑换方法。

2．甲的年龄数字颠倒过来恰好是乙的年龄，二人年龄之和为99，甲比乙大9岁。求甲的年龄。列出各种可能性，不难发现甲的年龄为54。

3．艾丽斯和包博想买同样的尺，但艾丽斯差22分，包博差3分，二人将钱合在一起仍不够买一把尺。一把尺至少多少钱？

4．阿基米德得到圆周率的结果是3+10/71<π<3+1/7。中国古代的祖冲之（5世纪下半叶）得到的结果是3.1415926<π<3.1415927，而且给出了两个最接近的分数，22/7和355/113。请根据3.1415926这个圆周率的近似值，给出分母分别为1位数、2位数、3位数、4位数的与圆周率最接近的真分数。

5．4名专家对四款赛车进行了如下评论。

■　A说：2号赛车是最好的。

■　B说：4号赛车是最好的。

■　C说：3号赛车不是最好的。

■　D说：B说错了。

只有一款赛车最佳，且只有一名专家的评论是正确的。编程求出哪款车最佳。