我的博客：MoeCode研究所

有些典型的程序设计问题可以用递归方法实现枚举策略来解决，我称之为递归枚举问题。探索一类问题的结构是解决问题的关键，本文举例分析该类问题。

走楼梯问题
跳马问题
分书问题
八皇后问题
人鬼渡河问题
练习1 - 狼/羊/蔬菜过河问题
练习2 - 分水问题

走楼梯问题

从楼上走到楼下共有h个台阶，每一步有三种走法，分别走1、2、3个台阶。问：一共可以⾛出多少种⽅案？即共要多少步？每一步走几级台阶？

显然是一个用枚举策略解决的问题。考虑其行为结构：初始剩余楼梯阶数为h，每一次都走一步，可能是1、2、3个台阶，如果走到剩余阶数小于零则退出枚举搜索过程，等于零表示找到一个新结果，大于零则需要继续走（搜索）。每一次的走法都有三种策略，这样可以生成一个典型的与或树，树形问题可以采用递归来解决。

与或树

考虑递归函数主体：分支的依据是不同的策略（可用for循环表示），每种分支下使用该策略需考虑其结果，有三种结果与对应的解决方法。

调用该策略后，剩余台阶数小于零（走之前剩余的台阶数height小于该策略的台阶数step，height < step），表示走超了，这不是正确的方法，不能继续走下去，所以什么都不用做。
调用后剩余台阶数等于零（height == step），表示刚好走完，需要记录当前策略并输出所有步数。
调用后剩余台阶数大于零（height > step），表示还没走完，需要记录当前策略并递归调用。

根据上述分析可以得到两种不同的程序（其实可以很多种），结构实际上都差不多，只是稍微有点变化。

方法1-1

方法1-2

方法2-1

方法2-2

考虑一个问题：这里的策略存储在一个数组中，为什么没有回溯的过程？这里不同递归函数虽然共用一个数组（全局变量），但是每次递归自己带有一个随着递归的深入单调递增的变量s或step，且其并不是全局变量，而是随着递归函数传值给下一层递归函数的局部变量。当一个递归函数退出时，其对应的步数变量自动释放，回到上一层后步数还是原来的数，相当于自动回溯了。所以这里递归调用时传入的是s + 1或step + 1而不是++s或++step。

数据的作用域特性（全局或局部变量）决定递归是否需要回溯。

要注意第二种方法的递归比第一种深入一层，所以用height == 0而不是height == step表示递归终止条件，其最后一个策略在上一层已经被记录下来。

跳马问题

在半张中国象棋的棋盘上，一只⻢从左下角跳到右上角，只允许往右跳，不允许往左跳，问能有多少种跳步方案。要求：输出方案数和各方案的具体跳法。

跳马问题的结构其实和走楼梯问题差不多，同样是连续使用不同的策略直至超出限制或者解决问题，只不过这里的关键是寻找合适方法来表述问题。

第一个需要将棋盘数字化，用一个整数对来表示马的位置，进而马的跳跃策略也就可以用坐标的变化量来表示。由于不能往左跳，所以共有四种跳法，可以用两个平行数组表示跳法的横纵坐标增量。注意：平行数组就是两个长度相同，共享一个索引的数组，当然也可以用结构体数组来处理。记录每一步则用一个二维数组，一个维度是跳步的次序，另一个维度是位置坐标，最后输出的是整个过程经过的点的位置，并不输出策略的序号（那只是为了解决问题临时编的）。

接下来展示的代码的递归函数体构成和走楼梯问题的第二种方法的代码类似，都是将判断是否结束提到前面来，接着再进一步调用策略。如下：

跳马-1

跳马-2

分书问题

有编号分别为 0、1、2、3、4 的五本书，准备分给A、B、C、D、E五个人。请你写一个程序，输出所有的分书方案，要求每个分书方案都能让每个人都皆大欢喜（即每人都分到感兴趣的书）。

阅读兴趣表如下：

十分明显这也是一个枚举/搜索问题，而且问题的结构和上面的例子也是一样的。与跳马问题相比较，这里的第几个人就相当于跳第几步，书本的编号就如同跳法序号，跳出界限就对应于分书方案超出书本数量限制或让某个人不满意，到达终点就类似于五个人都分完了。

所以解决问题的关键就是将问题数字化，这其实就是计算思维的关键。阅读兴趣表可以用一个二维数组来表示，like[i][j]表示第i个人喜欢第j本书；书籍的状态可以用一个一位数组表示assigned[book_id]表示第book_id本书被分配给第几个人，如果值为-1就表示这本书还没被分配（事实上也可以用数组表示人的状态，即某个人被分配了第几本书或还没分配。选一个数组即可，因为人和书可以说是“轮换对称”的）。

整个问题的解决可以看作是依次给五个人分书，每层递归函数就是给某个人分书，所以要将读者的序号传递下去。由于有全局变量所以要考虑要不要回溯，其实就是看不回溯是否会影响问题的结果。看完代码再来分析：

分书-1

分书-2

注意这里分书的条件：如果当前读者不喜欢这本书（循环指示变量i对应的书），或者当前的书已经被分出去了，那就什么都不做，也就是代码中展示的continue。而这个判断条件与assigned数组有关，也就是说如果这个数组不回溯的话，下一次循环时的判断条件就会受到上一次循环体的影响，而这种影响是不应当存在的。这里并不企图总结出用什么形式来判断是否需要回溯的所谓普遍规律，对于任何可以用递归解决的编程问题都应当结合具体问题去考虑，看不回溯的数据是否会影响下一次走不同路径的递归，如果会那就必须回溯。

既然数据的时间属性（不同时间点的数据）会影响递归的结果，从而需要利用回溯这一使得时间倒流的操作来消灭这种影响，那我们可以在具体的时间节点上将数据分成两块，一块对应变化前的状态，一块对应变化后的状态（需要输入下一层递归函数），如同分身一般，使得某个分支的递归操作不会影响另一个分支的递归操作。当然这样的代价就是程序所需的存储空间需要更大，以空间的消耗代替时间的消耗和程序复杂度的提升。不需要回溯的代码如下所示。

分书不回溯-1

分书不回溯-2

注意上面的代码中，需要拷贝成两块的数据就是assigned数组，由于数组的复制比较复杂，所以可以用一个结构体来封装数组，用结构体的复制代替数组的复制，这样使得程序的编写比较简单。而局部变量的作用域是代码块，也就是for循环的循环体，所以5个循环下来实际上已经创建了少于或等于5个的结构体（有if条件决定）。

八皇后问题

在国际象棋的棋盘（8 * 8）上摆上8个皇后棋子，使得两两之间互不攻击，也就是任何两个皇后之间要满足：不再棋盘的同一列；不在棋盘的同一行；不在棋盘的同一对角线上。

最简单的方法是暴力枚举。用一个一维数组表示皇后的位置，其下标为皇后序号或列号（皇后不能放在同一列），从1开始计数所以数组长度是9。设置八重循环遍历所有位置，最里面调用IsSafe函数判断整个格局是否安全，如果安全则输出该格局，否则什么都不做。

如何判断全局的安全性？可以采用两种思路：一是枚举皇后，看一个皇后与前面所有皇后是否会相互攻击，类似于插入排序；二是枚举位置，看每一行/列/对角线是否有两个或以上的皇后。

这种思路极简单的算法需要消耗巨大的时间代价，一个是八重循环，还有一个是对全局的安全性判断。该方法实际上做了很多无用功，比如开始的两个皇后同一行之后后面还会继续计算下去。我们需要聪明点的算法，能够避开行/列/对角线的冲突进行枚举，一步步地放置皇后，实际上就是带限制的搜索问题，同样可以用递归策略解决。

递归函数的每一层调用都企图将一个皇后放置在当前安全的位置（与前面的不冲突），所以递归函数的参数可以是皇后的序号（序号就是其列号，这里是一列一列地摆）。函数体一开始检测是否已经摆完，如果是就输出方案，否则摆下一个，也就是当前函数传入的参数。皇后的列已经确定，要对行进行枚举，对于某个行的值，如果安全则递归调用摆下一个皇后，摆完后视变量的设置进行回溯；如果不安全则什么都不做。

这里最重要的就是如何更快地判断当前摆放的位置是否安全。由于前面皇后的位置已经知道，所以最直接的方法就是，与它们一一比较，同样是枚举。另一种方法是从一开始维护一个微型数据库，指示当前哪些位置是安全的，当企图摆放棋子时，在这个数据库中查表即可知道是否安全。要维护哪些数据呢？我们先来看看某个位置安全性的数学表达。

安全性表达

左边图指示了行列冲突的表达式是横/纵坐标相等。右边图指示了对角线冲突的表达式是横/纵坐标相加或相减等于一定的值。所以可以用一个长度为9的一维数组表示行位置是否安全，为0的序号不用所以是9，因为是一列一列放的所以需要指示行位置的安全性。由于行列相加的值是2～16，所以可以用长度为17（下标从0到16）的数组表示该方向对角线的安全性，该方向共有15条对角线，每个棋子只能从中选一条。另一个方向的对角线同样有15条，坐标相减的值为-7～7，只需加上偏置常数9，坐标范围就和上面那条对角线完全一样了。

在放置棋子的时候只需用自己的横纵坐标计算相应的得数，在三个数组中一查，就知道自己的位置是不是安全的。如果是安全的，那么上面计算得到的三个得数作为下标，对应数组中的指示用的布尔值就要改成false表示不安全。

得到的程序如下所示。

八皇后-1

八皇后-2

八皇后-3

我们来思考一个问题：为什么数组Q不用回溯？注意该数组的下标对应皇后的序号或者其列号，元素的值对应行号。答案很简单，因为回不回溯根本不影响if条件判断，从而不影响其他递归分支。况且数组Q根本没有初始化，它们一开始就是随机值，难道回溯到一个随机数？

最后比较一下暴力枚举和后面的递归算法。暴力枚举的方法将参数8与程序的结构相挂钩，也就是8重循环，不利于将算法拓展到“N皇后问题”，因为传入参数不能轻易改变程序的结构。而后面的递归算法，递归多少层依赖于输入的参数，只需将原来的程序改造一下就可以推广到“N皇后”问题。

人鬼渡河问题

目标：将东岸的3人3鬼通过一只小船安全转移到西岸，希望摆渡次数尽可能少。
条件：

船的容量有限，一次最多只能坐2人（或2鬼或1人1鬼）。

无论是在河的东岸还是在河的西岸，一旦鬼数多于人数，则人将被鬼吃掉。

怎样渡河的大权掌握在人的手中。

说明：划船的时间忽略不计。船一靠岸即将船与岸视为一体，人和鬼即使还没有下船也视为已上岸。
任务：编写程序，求出⼀一种渡河⽅方案。

该问题与上面的问题具有同样的特性：满足一定的约束条件，从初始状态出发，在有限的策略中找到一条路径到达目的状态。这些问题都可以使用递归+枚举的方法来做。最关键的是将问题数字化。这个问题的“状态”的体现更为明显，可以直接使用一个结构体来表示状态，这个结构体代表了东岸的人和鬼的数量（表示西岸也可以）。其实就是一个数对，用数组也行。

struct state {
    int R, G;  //表示人和鬼
};

第二要表示策略，用自然语言表示就是船上有2人0鬼/1人0鬼/……，但是不能是0人0鬼。这些策略事实上是作为状态的增量存在的，所以也可以用state结构体表示，由于有5种策略，所以可以用数组来表示。下面将0人0鬼这种不合法的策略放置在数组的零序号处。

state d[6] = {{0, 0}, {2, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 2}};  //保存策略

还要表述路径，路径事实上就是状态的序列，或者策略的序列，这里我们把两个都记录下来。用state结构体构成的数组可以表示状态的序列，用整型数组可以表示策略的序列（用序号表示策略）。

state s[20];  //状态转移记录数组
int choice[20] = {0};  //决策记录数组

再来考虑所谓的约束条件，约束条件是状态发生变化时必须满足的条件。首先需要考虑数据的合法性，比如人的总数就是3个，所以state结构体中R域不能超过3，当然也不能是负数。其次还要考虑题目的约束条件：安全转移的条件以及次数尽可能少的条件。这里的次数尽可能少就意味着不能做无用功，也就是走着走着走回头了，甚至是在两个状态之间反复跳跃永远走不到终点。

约束条件

如图所示，总结起来就是：合法性、安全性、非重复性。

总结之前所求解的递归问题都大致有以下的递归函数结构：

递归函数(状态序号, 其他需要传递的变量) {
    if(终止条件) {
        输出当前路径;
        return;
    }
    
    for(策略数) {
        检查该策略是否满足约束条件;
        if(不满足约束条件) continue;
        
        状态序号++;
        执行策略;
        递归函数(新的状态序号, 其他需要传递的变量)；
        视情况回溯;
    }
    return;  //所有策略都不行
}

根据这个框架来分析。终止条件是东岸的人和鬼的数量都是0；输出当前路径可以创建一个子函数来执行；共有5种策略；分合法性、安全性、非重复性分别检查约束条件；执行策略就是将该策略对应存储在数组中的增量加到当前状态上。最终得到的代码如下：（该程序输出所有可能的结果）

#include <iostream>
#include <iomanip>
using namespace std;

struct state {
    int R, G;  //表示人和鬼
};

state s[20];  //状态转移记录数组
int choice[20] = {0};  //决策记录数组

state d[6] = {{0, 0}, {2, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 2}};  //保存策略

void display(int k);
void transfer_state(int k);

int main() {
    int k = 1;
    s[1].R = 3;
    s[1].G = 3;

    transfer_state(k);

    return 0;
}

void transfer_state(int k) {  //递归函数
    if(s[k].R == 0 && s[k].G == 0) {
        display(k);
        return;
    }
    int fx = 1;  //指示方向
    if(k % 2 == 1) fx = -1;  //如果是奇数则表示向西渡船

    for(int i = 1; i <= 5; i++) {
        int u = s[k].R + fx * d[i].R;
        int v = s[k].G + fx * d[i].G;

        if(u > 3 || v > 3 || u < 0 || v < 0) continue;  //数量不能越界
        
        bool AQ = (u == 3) || (u == 0) || (u == v);
        if(!AQ) continue;  //安全性判断

        bool CHF = false;  //是否重复
        for(int j = k - 1; j >= 1; j -= 2) {
            if(u == s[j].R && v == s[j].G) CHF = true;
        }
        if(CHF) continue;  //保证不重复

        k++;
        s[k].R = u;
        s[k].G = v;
        choice[k] = i;

        transfer_state(k);

        k--;  //回溯
    }
    return;
}

void display(int k) {
    for(int i = 1; i <= k; i++) {
        cout << setw(2) << i << ": choice = " << choice[i]
             << " {" << d[choice[i]].R << "," << d[choice[i]].G << "}"
             << " (" << s[i].R << "," << s[i].G << ") " << endl;
    }
}

有几点需要详细说明：

s和choice数组的关系：k是从1开始计数的，choice[k]策略调用后得到s[k]状态。所以在递归调用函数自身前面choice的下标是k自增后的下标。
由于增量有正有负，去的时候是负，来的时候是正，来去相交，所以可以用状态序号的奇偶性表示接下来的增量是正还是负，用变量fx来指示。
关于安全性判断条件的得出：调用策略后得到后来的人和鬼数目为u和v，要么人全在一边（u为3或0），要么人和鬼相等（u == v）才能保证安全。如果人是分开的，且人和鬼的数目不等，那么必有一边鬼大于人。
这里回溯只需改变k值即刻，与以前的分析一样。

补充人鬼渡河问题的循环解法代码，具有启发性。注意最后一张图输出结果中策略的序号是错误的。

循环-1

循环-2

循环-3

循环-4

练习1 - 狼/羊/蔬菜过河问题

题目描述

农夫(Human)过河。一个农夫带着一只狼(Wolf)，一只羊(Sheep)和一些菜(Vegetable)过河。河边只有一条船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过河?

输入格式

没有输入

输出格式

输出一行，为最终的过河方式，方案格式为过河人员、回来人员、过河人员、回来人员、...、过河人员。

过去和回来的人员之间，用空格隔开。

以四个生物英文的首字母代指对应的生物(H->Human,W->Wolf,S->Sheep,V->Vegetable)

具体见样例输出。

输出任意可行方案即可。

样例输入

无

样例输出

HS H HW H

注释

时间限制：1 s

空间限制：512 MB

样例输出仅用于解释输出格式，非答案。

在此样例输出描述的方案为：

人和羊过去，人回来，人和狼过去，人回来，此时对岸狼把羊吃了，不符合题目要求，故非正确答案。

AC代码

#include <iostream>
using namespace std;

int s[20][3];  //0-Wolf, 1-Sheep, 2-Vegetable
int choice[20];  //3表示谁都不带

int d[4][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {0, 0, 0}};  //几种策略的增量

void display(int k);
void transfer_state(int k);

int main() {
    int k = 0;
    s[0][0] = 1;
    s[0][1] = 1;
    s[0][2] = 1;

    transfer_state(k);

    return 0;
}

void transfer_state(int k) {
    if(k % 2 == 1 && s[k][0] == 0 && s[k][1] == 0 && s[k][2] == 0) {
        display(k);
        return;
    }

    int fx = -1;
    if(k % 2 == 1) fx = 1;

    for(int i = 0; i < 4; i++) {
        int u = s[k][0] + fx * d[i][0];
        int v = s[k][1] + fx * d[i][1];
        int w = s[k][2] + fx * d[i][2];

        if(u > 1 || v > 1 || w > 1 || u < 0 || v < 0 || w < 0) continue;  //数据越界

        int sum = u + v + w;
        bool is_safe = false;
        if(k % 2 == 0) {  //人将在彼岸
            if(sum <= 1) is_safe = true;
            if(sum == 2 && (u == 1 && w == 1)) is_safe = true;  //狼和菜在此岸
        }
        else {  //人将在此岸
            if(sum >= 2) is_safe = true;
            if(sum == 1 && (u == 0 && w == 0)) is_safe = true;  //狼和菜在彼岸
            //如果sum == 3,这不应当发生,也可视作不安全
        }
        if(!is_safe) continue;

        if(k > 0) {  //需要检测重复
            bool CHF = false;
            for(int j = k - 1; j >= 0; j -= 2) {
                if(s[j][0] == u && s[j][1] == v && s[j][2] == w) CHF = true;
            }
            if(CHF) continue;
        }

        //不越界,安全且不重复
        k++;
        s[k][0] = u;
        s[k][1] = v;
        s[k][2] = w;
        choice[k-1] = i;

        transfer_state(k);

        k--;
    }

}

void display(int k) {
    //k一定是奇数,因为人需要在对岸
    for(int i = 0; i < k; i++) {
        cout << "H";
        switch (choice[i]) {
            case 0: cout << "W"; break;
            case 1: cout << "S"; break;
            case 2: cout << "V"; break;
            case 3: break;
            default: cout << "Error!"; break;
        }
        if(i != k - 1) cout << " ";
    }
    exit(0);
}

练习2 - 分水问题

题目描述

有A、B和C三个杯子，容量依次为80mL、50mL和30mL。现在A杯中装满了80mL的水，B和C都是空杯。A中的水可以倒入B杯或C杯中，反之，B和C也可以往A中倒，还可以互相倒来倒去。为了计量，对于某一个杯子而言，不是被倒满，就是被倒空。也就是说，要么倒水的杯子空了，要么被倒水的杯子满了，这次倒水操作才会停止。请你编一个程序，将原来的80mL的酒分别倒入A和B两个杯子中，各有40mL。输出每一步的操作。

输入格式

没有输入

输出格式

第一行输出一个整数n，表示步骤的数量。

之后有n行，每行表示一个操作，包含两个字母 x 和 y，表示将 x 杯的酒，倒入y中。

输出任意可行方案即可。

样例输入

无

样例输出

4
A B
A C
B A
C B

注释

时间限制：1 s

空间限制：512 MB

样例输出仅用于解释输出格式，非答案。

在此样例输出描述的方案为：

一共有4步

最初状态：（A:80, B:0, C:0）

A 倒入 B。（A:30, B:50, C:0)
A 倒入 C。（A:0, B:50, C:30)
B 倒入 A。（A:50, B:0, C:30)
C 倒入 B。（A:50, B:30, C:0)

最终，A中有50ml，B中有30ml，C中有0ml，不符合题目要求，故非正确答案。

AC代码

#include <iostream>
using namespace std;

int s[50][3];
int choice[50] = {0};  //s和choice的关系是在第k个s采取第k个choice

int vol[3] = {80, 50, 30};  //表示水杯的容量
int d[6][2] = {{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}};  //策略的数字表述,字符表述如下行
string str[6] = {"\nA B", "\nA C", "\nB A", "\nB C", "\nC A", "\nC B"};

void display(int k);
void transfer_state(int k);

int main() {
    int k = 0;
    s[0][0] = 80;
    s[0][1] = 0;
    s[0][2] = 0;

    transfer_state(k);

    return 0;
}

void transfer_state(int k) {
    if(s[k][0] == 40 && s[k][1] == 40 && s[k][2] == 0) {
        display(k);
        return;
    }

    for(int i = 0; i < 6; i++) {
        int send = s[k][d[i][0]];  //倒水者的剩余水量
        int recv = vol[d[i][1]] - s[k][d[i][1]];  //接受水者的剩余容量
        int sended, recved;  //表示倒水之后二者的水量
        if(send > recv) {
            recved = vol[d[i][1]];
            sended = send - recv;
        }
        else {
            sended = 0;
            recved = s[k][d[i][1]] + send;
        }

        bool CHF = false;
        for(int j = 0; j <= k; j++) {  //等号表示不能和当前状态一样,表示不能空倒或者向满的里面倒
            if(s[j][d[i][0]] == sended && s[j][d[i][1]] == recved) CHF = true;  //只需比较两个,如果两个相等,那剩余一个一定相等
        }
        if(CHF) continue;

        k++;
        s[k][d[i][0]] = sended;
        s[k][d[i][1]] = recved;
        //此时还要修改剩余的那个杯子的值!
        s[k][3-d[i][0]-d[i][1]] = s[k-1][3-d[i][0]-d[i][1]];  //使用小技巧:三个下标的和为3
        choice[k-1] = i;  //注意减1

        transfer_state(k);

        k--;
    }
    return;
}

void display(int k) {
    cout << k;
    for(int i = 0; i < k; i++) {
        cout << str[choice[i]];
    }
    exit(0);
}

这里要注意如何实施倒水操作，可以通过比较倒水者的剩余水量和接受水者的剩余空间，确定是倒水者空了还是接受水者满了。特别注意执行策略时要将剩余一个杯子的值也复制过去（一开始本人就在此处出错）。求剩余杯子的下标有一个小技巧叙述如代码注释。

试探约束条件实际上都是先用u/v/w/sended/recved变量求出调用策略后的状态再看其是否满足约束条件，如果满足就将它们正式赋值给存储数据区。

最后提一句这类问题最重要的还是翻译题目！