11.3　递归、穷举、回溯、排列

11.3.1　2、9、6能组成多少个两位数

这是一个小学一年级的算术题。题目很简单，以至于让人不忍心去编程。这里之所以选择这个简单的题目，主要是为了更清晰地说明C语言编程的某些原理和过程。

两位数由个位数和十位数组成。既然他们都是2、9、6中的一个，那么可以首先在2、9、6中任意选择一个作为个位数，然后再从中任意选择一个作为十位数，这样就组成了一个两位数。然后再重复这个过程，只要做到个位数在2、9、6中都选择过一次就可以了。

由于2、9、6这几个整数并没有什么规律，所以在代码中把它们组织为一个数组更便于描述选择的过程：“int sz[3]＝｛2 , 9 , 6｝;”。如果把个位、十位所选择的数在数组中的下标定义为i、j的话，那么这个选择的过程很容易用一个二重循环描述。

在涉及穷举的变量较多时，这种写法显得非常“笨拙”，况且编译器对循环嵌套的层数可能有限制（C标准只要求嵌套的层数必须不少于某个常数）。如果在穷举的过程中还涉及其他一些比较复杂的计算，那么不难想象，代码的结构将变得更为复杂。

在C代码中，完成这样的任务，还有其他的选择。

11.3.2　更自然地思考

C语言的函数容许我们以更自然、更抽象、更概括的方式思考程序的写法，事实上也应该如此，因为离开了抽象和概括，我们根本无法无法掌握复杂。

完成题目任务要求首先需要从数组“选择个位数”，因此两位数的个数可以看成是“选择个位数”函数得到的值。从中选择数的数组可以看成是函数的参数，也可以看成函数本身所拥有的一个局部的数据。假如以后一种方式看待问题，程序的代码应该是如下的结构。

//选择-个个位数；之后需要马上//选择十位数，这样两位数的个数就是每次选择个位数之后可以选得的十位数的个数累加。如果把//选择十位数也抽象为一个函数，那么可选择的十位数的个数就是这个函数的值。这样程序代码就成了：

结论是，循环嵌套的功能完全可以由上面两个函数的嵌套调用实现。

值得注意的是这段伪代码的执行顺序，这对理解后面紧接着要叙述的内容非常重要。这段代码的执行顺序如图11-2所示。这种从一个点（调用选择个位数()）出发，引申出若干节点（选择个位数函数中i的值为1，2，3），再从这1、2、3每个节点出发，又引申出若干节点（选择十位数函数中i的值为1，2，3），这种东西在计算机的术语里叫做“树”（Tree）。这是一种很常见的数据之间的关系，有时候也可以用来描述某些问题的算法。前面的伪代码恰恰可以用来在树中每个节点“游历”一次，这叫“树的遍历”。

图11-2　执行次序

练习

完成前面伪代码所描述算法的程序代码。

11.3.3　进一步的抽象和概括

正如程序员很难容忍在同一程序中写多个相同或类似的语句一样，在多数情况下写很多相同或类似的函数几乎也是一种标志着无能的耻辱。前面的伪代码就是如此。由于“int 选择个位数（void）”与“int 选择十位（void）”的功能和结构极其相近，所以事实上它们完全可以写成一个函数。

不过话说回来，“int 选择个位数（void）”与“int 选择十位数（void）”这两个函数毕竟还是有点区别的，区别之一就在于函数名中的“个”与“十”，没关系，把它们统一改成“某”，再把“个”与“十”移到“()”里作为参数就可以了。就如同这样：“int 选择某位数（int 个或十位）”。完成之后的代码如下。

程序代码11-3

程序输出结果如图11-3所示。

图11-3　进一步的抽象和概括

练习

一个5位可以被72整除的正整数，中间三位分别为6，7，9，仿照前面的代码思想编程求这个数。

11.3.4　回溯法

题目：下列加法算式中，A、B、C、D、E、F、G、H、M、N分别表示0～9的不同数字，且A、D、M不为0，编程求出这些数字并且输出由这些数字组成的算术计算竖式。

显然，这个问题可以用穷举的办法解决。

如果使用循环嵌套这种代码结构，大概需要7重循环嵌套，其中还要搀杂许多判断条件。这种写法相当笨拙，不利于修改，而且很可能效率很低。利用函数递归的方法，也可以完成这种穷举的任务，而且这种方法表达思想更自然、更灵活。

由于E、G、D、F、C、H、B、N、A、M分别表示0～9的不同数字，所以可以首先选择一个E的值（比如说0）进行试探。由于暂时看不出这个0有明显的不合理的地方，所以继续试选G的值。由于E的值可能为0～9之间所有可能的数，因此必须都选择一次，这样代码的大致结构应该如下所示。

选择G的过程与此类似，可以通过调用这个函数完成。但是为了提高程序的效率，G不应该选择已经选择过的数。这就要求这个函数必须能够知道前面选择过哪些数，因此需要一块内存空间记录已经选择过的数：int 选择过的数[10];，这里的10是由于最多有10个数被选择。问题在于把这个数组放在代码中的哪个位置并以何种方式让“选()”这个函数知道。这可以有下面两种方式实现。

1．放在“选()”这个函数之外。

2．放在“选()”这个函数之内。

第1种方式中，又分为放在所有函数之外和放在其他函数之内两种手段。前一种是所谓的外部变量，这种手段最容易，然而很可能是最坏的，理由将在后面关于外部变量的章节中详述。如果放在某个函数之内（比如main()），那么必然涉及向“选()”这个函数传递参数的问题，这会使这个函数更为复杂。所以在这里采用把“选择过的数”这个数组放在“选()”这个函数之内的解决方案。

然而，如果简单地把“选择过的数”这个数组作为“选()”这个函数的局部变量是不行的，因为每次调用“选()”这个函数，函数都会建立一个为本次调用所独有的一套局部变量（包括形参，参阅前面章节函数调用与递归部分）。由于程序功能要求“选择过的数”为各次函数调用共同参照使用的数据，所以应该把这个变量定义为“static”存储类别的变量。这种变量不但从程序执行到程序结束时始终存在，而且更重要的是它是唯一的，因此能够保证在每次调用时函数所使用的都是同一个数据。

另外要注意的一个细节是，“选择过的数”这个数组中的有效数据是在动态地“消长”，最初一个也没有，选完E之后其中有一个数据，选完G之后其中有两个有效数据。可以根据调用“选()”这个函数时的实参的值来判断“选择过的数”中有效数据的个数。

这个问题解决之后，还要考虑到，选择完前面某个字母的值之后，在选择下一个字母的值时，可能会发现0～9中没有合适的数据可选，这表明前面的选择有问题。此时不应该继续选择也无法继续选择，而是应该回到上一层再选一个数，这就是所谓的“回溯”。

由于没有合适的数据可以选择意味着循环的结束，而“回溯”意味着返回调用函数处，所以应该在描述选择过程的循环语句结束后加上“return”语句。也就是

最后还应该考虑到所有的字母都选择到了合适的值的情况，显然，此时应该输出结果，然后返回上一层。这可能导致找出其他的解并最终返回到最初的调用处。这样，这个函数最终的结构就是：

现在，程序大体上的思想已经讨论清楚，其他一些细节和技巧在代码中体现，在阅读代码时请加以注意。

程序代码11-4

练习

一个四位数的9倍仍是四位数，但数字次序相反，编程求此四位数。

11.3.5　排列问题

许多用穷举方法解决的问题，最后都可以抽象为排列或全排列问题。比如，2、9、6能组成多少个两位数这样的问题。

从n个不同元素中任取m (m⩽n)个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m等于n时所有的排列情况叫全排列。

排列问题通常可以通过函数递归的技术手段解决，这是一种比较通用的方法。事实上通过循环的嵌套，在很多情况下代码是几乎写不出来的。很难设想可以把几十层循环嵌套在一起的情况。

但是通过函数递归技术手段要求代码作者具有较高的抽象能力和熟练的表达能力，下面通过一道例题总结一下排列问题的思路和代码的写法。

考虑下面的题目：将1～6这6个数填在如图11-4所示的圆圈里，使每条线的3个数之和相等，共有多少种不同的填法？

图11-4　填数题目图

为了更清楚地说明代码的思想，我们把问题分成几个简单的问题逐个考虑并讨论。

首先必须考虑的是在代码中如何表示这个问题。由于这6个圆圈里的数据都是整数，性质相同，所以可以把这6个圆圈表示为一个数组：int yq[6];。把1～6这6个数填在圆圈里，对应着把这6个数据按照不同的次序组合写入数组，显然这是一个全排列问题。

求一组数据的全排列可以通过下面步骤完成。

首先把这6个数依次放在数组的最前面，然后对剩余的5个进行全排列。显然这是个递归的解决方法。依次类推，当一个数据的时候，全排列的方法只有一种。这样就为递归提供了终止的条件。

“把每个数据都放在数组的最前面”这件事可以通过把数组最前面元素与其他元素交换实现。这样排列的函数可以写成：

由于最初调用这个函数是对6个数进行全排列，之后对数组后面的5个数进行全排列……所以对这个数组中后面哪几个数据进行排序也是函数必须要知道的数据。换句话说，函数需要有一个表示对数组中哪几个数进行全排列的参数。

按照这个思想写出的代码如下所示。

程序代码11-5

由于排列的总数有6！种，因此输出过于占用篇幅。所以下面这个结果是把代码中的：

替换为：

时的运行结果。

此时的输出结果如图11-5所示，可以看到，程序满足要求地输出了全部的排列结果。

图11-5　排列问题1

然而，如果排列是如此简单，那么本书也就不必在此大费口舌了。事实上，这段代码使用了一个比较狡猾而且不常见的技巧：把数组封装在了一个结构体内部。这样带来的后果是，在函数之间传递的是结构体，换句话说，实现了在函数之间“整体”传递“数组”——实参把自己的值（包括数组整体）复制给了形参。然而这种做法通常是违背C语言一贯的风格的，因为在数据对象较大时，这种复制无疑要消耗许多时间。所以通常情况下，C程序在函数之间只传递数组的名称（指向数组起始元素的指针）和数组元素的个数。

如果把前面的代码改为下面样子是否可行呢？

程序代码11-6

这段程序的运行结果如图11-6所示。

图11-6　排列问题2

仔细观察一下输出结果会发现，尽管输出仍然是24种排列，然而其中不少排列是重复的，有些结果比如4321并没有输出。

造成这种现象的根本原因在于：前一个代码中，递归函数调用传递的是伪装成结构体类型的“数组”，在不同层次的递归调用函数之中，函数使用不同的“数组”数据；而后一个代码中，所有的函数调用使用的都是同一个数组，在递归调用的深层返回上层之后，看到的数组不再是当初发生函数调用离开函数时的那个样子，而是一个面目全非的同一个数组。

更具体地说，以前一个代码中的“pailie (yqz , GS );”调用为例，其中的循环语句能够保证提供数组的值依次为“1234”、“2134”、“3124”、“4123”，在向下一层调用时候，由于传递的是其副本，所以递归下层对本层没有影响。这就保证了1、2、3、4这4个数都在数组开头出现过。

然而，后一个代码中，由于深层调用和浅层调用使用的是同一个数组，在深层对数组元素位置的改变将会对浅层中数组有影响，相应的循环语句也就无法保证1、2、3、4都在数组开头出现一次了。这样的输出结果必然是不知所云的。

这同样提示我们代码应该如何修改：从深层回到浅层应该把数组恢复成原来的样子。由于从深层回到浅层的位置在“pailie(yq , pljg－1)；”之后，所以只要在其后面加上一句“jiaohuan( yq + bjh , yq + jh);”，从深层返回浅层后再把数组改为交换前的样子就可以了。

需要说明的是前面的代码解决的是全排列问题。如果问题不是全排列，也就是说当从n个不同元素中任取m（m<n时）个元素，那么排列的代码要更复杂一些，因为这时m也必须是函数的参数，这时递归的深度不同于全排列的情况。

至此，由于排列问题已经解决，问题也就基本解决了。只要在代码中适当的位置加上检查是否满足每条线上3个数之和相等这个条件就可以。如果需要考虑程序的效率，代码应该能够在不满足这个条件的情况下及时返回上一层，而不是无意义地作出一个徒劳的排列，亦即及时回溯。

前面的讨论并没有考虑到问题的对称性，因此按照前面的解法，会得到事实上的重解（旋转对称）。如果考虑到问题的对称性，问题的本质实际上并非是一个排列问题，而是一个排列与组合两个问题的结合。限于篇幅，这里就不一一讨论了。有兴趣的读者可以自己思考。