算法竞赛入门经典授课教案第7章 暴力求解法
-
第
7
章
暴力求解法
第
7
章
暴力求解法
【
教学内容相关章节
】
7.1
简单枚举
7.2
枚举排列
7.3
子集生成
7.4
回溯法
7.5
隐式图搜索
【
教学目标
】
（
1
）掌握整数、子串等简单对象的枚
举方法；
（
2
）熟练掌握排列生成的递归方法；
（
3
）熟练掌握用“下一个排列”枚举全排列的方法；
（
4
）理解解答树，并能估算典型解答树的结
点数；
（
5
）熟练掌握子集生成的增量法、位向量法和二进制法；
（
6
）熟练掌握回溯法框架，并能理解为什么它往往比生成
-
测试法高效；
（
7
）熟练掌握解答树的宽度优先搜索和迭代加深搜索；
（
8
）理解倒水问题的状
态图与八皇后问题的解答树的本质区别；
（
< br>9
）熟练掌握八数码问题的
BFS
实现；
（
10
）熟练掌握集合的两种典型实现——
hash
表和
STL
集合。
【
教学要求
】
掌握整数、
子串等简单对象的枚举方法；
熟练掌握排列生成的递归方法；
熟练掌握用
“下
一个排列”
枚举全排列的方法；
理解子集树和排列树
；熟练掌握回溯法框架；熟练掌握解答
树的宽度优先搜索和迭代搜索；熟练掌握集合的两
种典型实现——
hash
表和
STL<
/p>
集合。
【
教学
内容提要
】
本章主要讨论暴力法（也
叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，
然后选择其中的一种方法，
若该方法不可行则试探下一种可能的方法。
介绍了排列生成的递
归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的
基
本框架；介绍了集合的两种典型实现——
hash
表和
STL
集合。
【
教学重点、难点
】
教学重点：
（
< br>1
）熟练掌握排列生成的递归方法；
< br>（
2
）理解解答树，并能估算典型解答树的结点数；
（
3
）熟练掌握
子集生成的增量法、位向量法和二进制法；
（
4
）熟练掌握回溯法框架，并能理解为什么它往往比生成
-
测试法高效；
（
5
）熟练掌握解答树的宽度优先搜索和迭代搜索；
<
/p>
（
6
）熟练掌握集合的两种典型实现——
hash
表和
STL
< br>集合。
教学难点：
（
1
）熟练掌握子集生成的增量法、位向量法和
二进制法；
（
2
）熟练掌握回溯法框架，并能理解为什么它往往比生成
-
测
试法高效；
（
3
）熟练掌握解答树的宽度优先搜索和迭代搜索；
（
4
）熟练掌握集合的两种典型实现——
has
h
表和
STL
集合。
< br>
【
课时安排
】
7.1
简单枚举
7.2
枚举排列
7.3
子集生成
7.4
回溯法
7.5
隐式图搜索
第
199
页
第
7
章
暴力求解法
引
言
暴力法也称为穷举法、
蛮力法，
它要求
调设计者找出所有可能的方法，
然后选择其中的
一种方法，若该
方法不可行则试探下一种可能的方法。
暴力法也是一种直接解
决问题的方法，常常直接基于问题的描述和所涉及的概念定义。
暴力法不是一个最好的算法，
但当我们想不出更好的办法时，
它也是一种有效的解决问
题的方法。
暴力法的优点是逻辑清晰，编写程序简洁。在程序设计竞赛时，时间紧张，
相对于高效<
/p>
的、巧妙的算法，暴力法编写的程序简单，能更快地解决问题。同时蛮力法也是很多算法的
基础，可以在蛮力法的基础上加以优化，得到更高效的算法。
而且，
某些情况下，
算法规模不大，<
/p>
使用优化的算法没有必要，而且某些优化算法本身
较复杂，在规模
不在时可能因为复杂的算法浪费时间，反而不如简单的暴力搜索。
使用暴力法常用如下几种情况：
（<
/p>
1
）搜索所有的解空间；
（
2
）搜索所有的路径；
（
3
）直接计算；
（
4
）模拟和仿真。
7.1
简
单
枚
举
在枚举复杂对象之前，先尝试着枚
举一些相对简单的东西，如整数、子串等。
暴力枚举
对问题进行
一定的分析往往会让算法更加简洁、高效。
7.1.1
除法
输入正整数
n
，按从小到大的顺序输出所有形如
abcde/fghi
j=n
的表达式，其中
a
～
j
恰好为数字
0
～
9
的一个排列，
2
≤
n
≤
79
。<
/p>
样例输入：
62
样例输出：
79546/01283=62
94736/01528=62
【分析】
只需要枚举
fghij
就可以计算出
abcde
< br>，然后判断是否所有数字都不相同即可。不仅程
序简单，而枚举量也从
10!=3628800
降低至不到
1
万。由此可见，即使采用暴力枚举，也是
需要认真分析问题。
完整的程序如下：
#include
using
namespace std;
bool
test(int i,int j){ //
用数组
t
存放
i
，
j
的各位数字
int
t[10]={0}; //
初始化数组
t
< br>，使得各位数字为
0
，好处是使得
fghij<10000
时
f
位置为
0
int ia = 0;
while(i) { //
取
i
中
各位数字存放在数组
t
中
t[ia++] = i % 10;
i = i / 10;
}
while(j) {
//
取
j
中各位数字存放在数组
t
中
t[ia++] = j % 10;
j = j / 10;
}
//
判断
< br>a
～
j
是否恰好为数字的
0
～
9
的一个排列<
/p>
第
200
页
第
7
章
暴力求解法
for(int m = 0; m < 10; ++m)
for(int n = m+1; n < 10; ++n)
if(t[n] == t[m]) return
false;
return true;
}
int main(){
int n;
int k;
while(cin >> n && n >=2 && n <= 79) {
k = 1234;
while(k <= 98765) {
int j = k * n;
if(j < 100000) { //
若
fghij<10
000
，满足题目的条件，
f
位置输出
0
if(test(j,k)) {
cout << j <<
if(k < 10000) cout <<
cout << k <<
}
}
++k;
}
}
return 0;
}
7.1.2
最大乘积
输入
n
个元素组成的序列
S
，你需要找出
一个乘积最大的连续子序列。如果这个最大的
乘积不是正整，应输出
-1
（表示无解）
。
1
≤
n
≤
18
，
-10
≤
S
i
≤
10
。
样例输入：
3
2 4 -3
5
2 5 -1 2
-1
样例输出：
8
20
【分析】
连续子序列有两个要素：
起点和终点，
因此只需要枚举起点
和终点即可。
由于每个元素
18
的绝对
值不超过
10
，一共又不超过
18
个元素，最大可能的乘积示会超过
10
，可
以用
long
long
存下。
完整的程序如下：
#include
int main(){
int a[20];
//
存放输入序列的每一个元素
__int64 ans = 0; //
存放最大的乘积
int n;
//
输入元素的个数
__int64
tmp
；
//
存放乘积的中间结果
while(scanf(
输入序列中元素的个数
n
for(int i = 0;i < n; i++)
//
输入序列中的元素
scanf(
for(i = 0; i < n; i++) {
第
201
页
第
7
章
暴力求解法
//
从序列中的第
0
个元素开始，枚
举最大连续乘积，并用
ans
存储
tmp = 1;
for(int j = i; j < n; j++) {
tmp *= a[j];
if(tmp >
ans) ans = tmp;
}
}
if(ans>0)
printf(
else
printf(
}
return 0;
}
7.1.3
分数拆分
输入正整数
k
，找到所有的正整数
x
≥<
/p>
y
，使得
1
1<
/p>
1
。
k
x
y
样例输入：
2
12
样例输出：
2
1/2=1/6+1/3
1/2=1/4+1/4
8
1/12=1/156+1/13
1/12=1/84+1/14
1/12=1/60+1/15
1/12=1/48+1/16
1/12=1/36+1/18
1/12=1/30+1/20
1/12=1/28+1/21
1/12=1/24+1/24
【分析】
找出所有有
x
，
y
，枚举完成了就行了。
但是从
1/12=1/156+1/13
可以看出，
x
可以比
y
大很多。由于
x
≥
y
，有<
/p>
1
1
1
1
1
，因此
，即
y
≤
2k
。这样，只需要在
2k
范围内枚
k
y
y
< br>x
y
举
y
，然后根据
y
尝试计算出
x
即可。
完整的程序如下：
#include
int main(){
int
k;
int x, y, count = 0;//
变量
count
统计等式的个数
while(scanf(
for(y = k+1;y <= 2 * k; y++){ //
判断
1/k=1/x+1/y
等式的个数，
x=(k * y) / (y
- k);
if(x * (y-k) == k * y){
count++;
}
}
第
202
页
第
7
章
暴力求解法
printf(
输出满足条件的等式的个数
for(y = k+1; y <= 2 * k;
y++){ //
输出满足条件的等式
x=(k * y) / (y
- k);
if(x * (y - k) == k * y){
printf(
}
}
}
return 0;
}
7.1.4
双基回文数
如果一个正整数
n
至少有两个不同的进位制
b1
和
b2
下都是
回文数
（
2
≤
b
1
,b
2
≤
10
）
，
则<
/p>
称
n
是双基回文数（注意，回文数不以包
含前导零）
。输入正整数
S<106
，
输出比
S
大的最
小双基回文数。
样例输入：
1600000
样例输出：
1632995
【分析】
最自然的想法是：
从
n+1
开始依次判断每个数是否为双基回文数
，
而在判断时要枚举所
6
有可能的基数
（
2
～
10
）
。意外的是：对于
S<10
的“小规模
数据”来说是足够快的——双基
回文数太多太密。
完整的程序如下：
#include
using namespace std;
bool huiwen(int n){
int i,j,a[30],s;
int
total = 0; //
存放数
s
是回文数的基数个数
for(int base =
2; base <= 10; base++) {
i = 1;
s = n;
while(s)
{
a[i] = s % base;
s = s / base;
i++;
}
i--;
for(j =
1; j <= i/2; j++) //
判断数
s
在基
base
下是否是回文数
if(a[j] != a[i-j+1])
break;
if(j > i/2) total++;
//
数
s
在基
base
下是回文数，则
total++
if(total >= 2) return true;
}
return false;
}
int main(){
int s;
while(scanf(
for(s = s+1; s++) {
if(huiwen(s)) {
cout << s << endl; break;
}
第
203
页
第
7
章
暴力求解法
}
}
return 0;
}
7.2
枚
举
排
列
输入整数
n
，按字典序从大到小的顺序输出前
n
个数的所有排列。两个序列的字典序大
小关系等价于从头开始第一个不相同位置处的大小
关系。例如，
(1,3,2)<(2,1,3)
，字典序
最小的排列是
(1,2,3,4,
„
,n)
，最大的排列是
(n,n-1,n-2,
„
,1)
。
n
=3
时，所有排列的排序
结果是：
(1
,2,3)
、
(1,3,2)
、
(2,1,3)
、
(2,3,1)
、
(3,1,2)
、
(3
,2,1)
7.2.1
生成
1<
/p>
～
n
的排列
<
/p>
对此问题用递归的思想解决：先输出所有以
1
开头的排列（递归调用）
，然后输出以
2
< br>开头的排列（递归调用）
，接着以
3
开头的排列，„，最后才是以
n
开头的排列。
以
1
开头的排列的特点是
：第一位是
1
，后面是按字典序的
2<
/p>
～
9
的排列。所以在设计
递归函数需要以下参数：
（
1
）已经确定的“前缀”序列，以便输出；
< br>（
2
）需要进行全排列的元素集合，以便依次选做第一个
元素。
这样，写出以下的伪代码：
void print_permutation(
序列
A
，集合
S)
{
if(S
为空
)
输出序列
A;
else <
/p>
按照
从小到大顺序
依次考虑
S
的每个元素
v
{
print_permutation(
在
A
的末尾填加
v
后得到的新序列，
S-{v});
}
}
上面的递归函数中递归边界是
S<
/p>
为空的情形，可以直接输出序列
A
；若<
/p>
S
不为空，则按
从小到大的顺序考虑
S
中的每个元素，每次递归调用以
A
开头。
下面考虑程序的实现。用数组表示序
列
A
，集合
S
可以由序列
A
完全确定——
A
中没有
出现的元素都可以选。
C
语言中的函数在接受数组参数时无法得到数组的元素个数，所以需
要传一个已经
填好的位置个数，或者当前需要确定的元素位置
cur
。声明一
个足够大的数组
A
，然后调用
prin
t_permutation(n,A,0)
，即可按字典序输出
1
～
n
的所有排列。
完整的程序如下：
#include
int
A[100];
//
输出
1
～
n
的全排列的递
归函数
void
print_permutation(int n, int* A, int cur) {
int i, j;
if(cur == n) {
//
递归边界
for(i
= 0; i < n; i++) printf(
printf(
}
else for(i = 1;
i <= n; i++) { //
尝试在
A[cur]<
/p>
中填各种整数
i
int ok
= 1;
for(j = 0; j < cur; j++)
if(A[j] == i) ok = 0; //
< br>如果
i
已经在
A[0]
～
A[cur-1]
出现过，则不能再选
if(ok) {
A[cur] = i;
第
204
页
第
7
章
暴力求解法
print_permutation(n, A,
cur+1); //
递归调用
}
}
}
int main() {
print_permutation(4, A, 0);
return
0;
}
在递归函数
print_p
ermutation
中循环变量
i
是
当前考虑的
A[cur]
。为了检查元素
i
是否已经用过，
还用到了一个标志变量
ok
，初始值为
1
（真）
，
如果发现有某个
A[j]==i
时，
则改为
0
（假）
。如果最终
ok
仍为
1
，则说明
i
没有在序列中出现过，把
它添加到序列末尾
（
A[cur]=i
）后递归调用。
7.2.2
生成可重集的排列
如果把问题改成：
输入数组
A
，并按字典序输出数组
A<
/p>
各元素的所有全排列，则需要对
上述递归函数
print_permutation
修改——把
P
加到
print_permutation
的
参数列表中，
然
后把代码中的
if(A
[j]==i)
和
A[cur]=i
分
别改成
if(A[j]==P[i])
和
A[cur]=P[i]
。
只有把
P
的所有元素按从小到大的顺序排序，然后调用
print_pe
rmutation(n,P,A,0)
即可。
但是上述递归函数
print_permutation
中，
禁止
A
数组中出现重复，
而在
P
中可能就有
重复元素时，所以输出数组
A
时就会出现问题。
解决方法是统计
A[0]
～
A[cur-1]
中
P[i]
的出现次数
c1
，
以及
P
数组中
P[i]
的出现次数
c2
。只要
<
br>输出数组
c1
，就能递归调用。
枚举的下标
i
应不重复、不遗漏地取遍所有
P[i]
值。由于
P
数组已经排过序，所以只
需检查
P
的第一个元素和所有
“与前一个元素不相同”
的元素，
即只需在
for(i=0;i
和其后的花括号之前加上
if(!i||P[i]!=P[i-1])
即可。
完整的程序如下：
#include
int
P[100], A[100];
//
P
中元素的全排列。数组
P
中可能有重复元素
void
print_permutation(int n, int* P, int* A, int cur)
{
int i, j;
if(cur == n)
{
for(i = 0; i < n; i++)
printf(
printf(
}
else for(i = 0; i < n; i++)
if(!i || P[i] != P[i-1]) {
int c1 = 0, c2 = 0;
for(j
= 0; j < cur; j++) if(A[j] == P[i]) c1++;
for(j = 0; j < n; j++)
if(P[i] == P[j]) c2++;
if(c1 < c2) {
A[cur] =
P[i];
print_permutation(n, P, A, cur+1);
}
}
}
int main() {
int i, n;
scanf(
第
205
页
第
7
章
暴力求解法
for(i = 0; i < n; i++)
scanf(
print_permutation(n, P, A, 0);
return 0;
}
7.2.3
解答树
假设
n=4
，序列为
{1,
2,3,4}
，
如图
7-1
所
示的树显示出了递归函数的调用过程。其中，
结
点内部的序列表示为
A
，
位置
cur
用高亮表示，
另外，
由于从该处开始的元素和算法无关，
因此用星号表示。
图
7-1
排列生成算法的解答树
从图
7-1
可以看出，它是一棵二叉树。第
0
层（根）结点有
n
个儿子，第
1
层结点各有
n-1
个儿子，
第
2
层结点各有
n-2
个儿子，第
3
层结点各
n-3
个儿子，„，第
n
层结点都没
有儿子（即都是叶子）
，而每个叶子对应于一个排列，共有
n!
个叶子。由于这棵树展示的是
逐步生成完整解的
过程，因此将其称为解答树。
提示
7
-1
：
如果某问题的解可以由多个步骤得到，而每个步骤都有若
干种选择（这些候
选方案集可能会依赖于先前作出的选择）
，且
可以用递归枚举法实现，则它的工作方式可以
用解答树描述。
通过逐层查看，第
0
层有
1
个结点，第
1
层有
n
个结点，第
2
层有
n*(n-1)
个结点，第
3
层有
n*(n-1)*(n-2)
个结点，„，
第
n
层有
n*(n-1)*(n-2)
*
„
*2*1=n!
个。
为了推导方便，把
n*(n-1)*(n-2)*
„
*(n-k)
写成
< br>n!/(n-k-1)!
，则所有结点之和为：
n
1
n
1
n
!
1
1
T
(
n
)
n
!
<
/p>
n
!
k
0
(
n
k
1)!
k
0
(
n
k
1)!
k
0
k
!
n
1
1
根据高等数学中的泰勒展开公式
，
lim
e
，因此
T(n)
·
e=O(n!)
。由于叶子
x
k
0
k
!
n
1
有
n!
个，倒数第二层也有
n!
个结点，因此上面的各层全部来源于最后一两层，所以上面的
结点数可以忽略不计。
7.2.4
下一个排列
枚举所有排列的另一个方
法是从字典序最小排列开始，
不停调用
“求下一个排列”
的过
程，在
C++
的
STL
中提供了一个库函数
next_
permutation
。
完整的程序如下：
#include
#include
using namespace std;
int
main() {
int n, p[10];
scanf(
for(int i = 0; i < n; i++)
scanf(
sort(p, p+n); //
排序，
得到
p
的最小排列
do {
for(int i = 0; i
< n; i++) printf(
输出排列
p
printf(
}
while(next_permutation(p, p+n)); //
求下一个排列
return
0;
}
说明：
（
< br>1
）
STL
里面有个
sort
函数，可以直接对数组进行随机化快速排序，复杂度为
n*log
2
n
，效率高
。使用这个函数，需要包含头文件：
#include
using namespace std;
它的函数原型如下：
第
206
页
第
7
章
暴力求解法
①
template
void
sort(RandomAccessIterator first,
RandomAccessIterator last);
这个
sort
函数可以传两个参数。第一个参数是要排序的区间首地址，第二个参
数是区
间尾地址的下一地址。也就是说，排序的区间是
[a,b
)
。简单来说，
有一个数组
int <
/p>
a[100]
，
要对从
< br>a[0]
到
a[99]
的元素进
行排序，只要写
sort(a,a+100)
就行了，默认的排
序方式是升
序。
如果需要对数组
t
的第
0
到
len-1
的元素排序，就写
sort(t,
t+len);
，对向量
v(
定义
vector
进行排序，写成
sort((),());
，排序的数据类型不局限于
整数，只要是定义了小于运算的类型都可以，比
如字符串类
string
。
②
template
void
sort(RandomAccessIterator first,
RandomAccessIterator last,
StrictWeakOrdering comp);
这个
sort
函数可以传三个参数。第一个参数是要排序的区间首地址，第二个参数是区
间尾地址的下一地址。也就是说，排序的区间是
[a,b)
。简单来说，
有一个数组
int
a[100]
，
要对从
a[0]
到
a[99]
的元素进行排序
，只要写
sort(a,a+100)
就行了，默认的排序方式
是升
序。
如果是没有定义小于运算的
数据类型，
或者想改变排序的顺序，
就要用到第三参数——
比较函数。比较函数是一个自己定义的函数，返回值是
bool
型，它规定了什么样的关系才
是“小于”
。
想把刚才的整数数组按降序排列，可以先定义一个比较函数
cmp
bool cmp(int a,int b) {
return a>b;
}
排序的时候就写
sort(a,a+100,cmp);
。
（
2
）在
C++
的
STL
中定义的
n
ext_permutation
和
prev_permuta
tion
函数则是非常灵
活且高效的方法，它被广泛的应用于为
指定序列生成不同的排列。
next_permutation
和
prev_permutation
函数需要包含
algorithm.h
头文件。需要注意的是“如果要走遍所有的
排列，必须先将元素排序”
。
（
3
）按照
STL
文档的描述，
next_permutation
函数将按字母表顺序生成给定序列的下
一个较大的排列，直到整个序列为降序为止。<
/p>
prev_permutation
函数与之相反，是生成给<
/p>
定序列的上一个较小的排列（前一个排列）
。二者原理相同，仅遍
历顺序相反。这两个函数
据可以对整型数组或字符数组操作。
（
4
）
nex
t_permutation
函数原型
①
template
②
template
last, Compare comp);
next_p
ermutation
函数取由
[first,last)
标记的排列，
并将其重新排序为下一个排列。
如果不存在下一个排列，则返回
false
；否则，返回
true
。第一个版本（①）使用底层类型
的小于操作符来确定下一个排列，第二个版本（②）根据
comp
对元素进行排序。如果原始
字
符
串<
/p>
是
排
过
序
的
，
则
连
续
调
用
next_per
mutation
函
数
会
生
成
整
个
< br>排
列
集
合
。
prev_permutation
函数原型与
next_permutation
函数型类似。
7.3
子
集
生
成
<
/p>
本节介绍子集生成算法：
给定一个集合，
枚举它所有可能的子集。
为了简单起见，
本节
< br>讨论的集合中没有重复元素。
7.3.1
增量构造法
第一种思路是一次选出一个元素放到集合中，完整程序如下：
#include
void print_subset(int n, int* A, int
cur) {
int i;
第
207
页
第
7
章
暴力求解法
for(i = 0; i < cur; i++)
printf(
打印当前集合
printf(
int s = cur ?
A[cur-1]+1 : 0; //
确定当前元素的最小可能值
for(i = s; i < n; i++) {
A[cur] =
i;
print_subset(n, A, cur+1); //
递归构造子集
}
}
int A[10];
int main() {
print_subset(5, A, 0);
return 0;
}
注意：
由于
A
中的元素个数不确定，每次递归调用都要输出当前集合。另外，递归边界
也不需要显式确定——如果无法继续添加元素，自然不会再递归了。
上面的代码用到了定序的技巧：
规定集合
A
中所有元素的编号从小到大排列，
就不会把
集合
{1,2}
按照
{1,2}<
/p>
和
{2,1}
输出两次了。
这棵解答树上有
1024
个结点，由于每个可能的
A
都对应一个结点，而
n
元素集合恰好
n
10
有
2
个子集，
2
=1024
。
7.3.2
位向量法
第二种思路是构造一个位向量
B[i]
，而不是直
接构造子集
A
本身，其中
B[i]=1
当且仅
当
i
在
子集
A
中。完整程序如下：
#include
void print_subset(int n, int* B, int
cur) {
if(cur == n) {
for(int i = 0; i < cur; i++)
if(B[i]) printf(
打印当前集合
printf(
return;
}
B[cur] = 1;
//
选第
cur
个元素
print_subset(n, B, cur+1);
B[cur] = 0; //
不选第
cur
个元素
print_subset(n, B, cur+1);
}
int B[10];
int main() {
print_subset(5, B, 0);
return 0;
}
必须当
“所有元素是否选择”
全部确定完毕后才是一个完整的子集，
因此当
if(cur==n)
成立时才输出。所有部分解（不完整的解）也对应着解答树上的
结点。
这是一棵
n+1
层的二叉树（
cur
从
0<
/p>
～
n
）
，第
0
层有
1
个结点，
第
1
层有
2
个
结点，第
i
n
n+1
< br>2
层有
4
个结点，第
3
层有
8
个结点，„，第
i
层有
2
个结
点，总数为
1+2+4+
„
+2
=2
-1
。
图
7-2
就是这棵解答树。最后几层结点数占整棵树的绝大多数。
图
7-2
位向量法的解答树
7.3.3
二进制法
第
208
页
第
7
章
暴力求解法
用二进制来表示
{0,1,2,
„
,
n-1}
的子集
S
：从右往左第
i
位（各位从
0
开始
编号）表示
元素
i
是否在集合
S
中。
用图
7-3
展示了二进制
011
是如何表示集合
{0,1,2,4,
5,9,10,14}
的。
图
7-3
用二进制表示子集
注意：
为了处理方便，最右边那个位总是对应元素
0
，而不是元素
1
。
提示
7-2
：
可以用二进制表示子集，其中从右往左第
i
位（从<
/p>
0
开始编号）表示元素
i
是否在集合中（
1
表示“在”
，
0
表示“不在”
）
< br>。
不仅要表示集合，
还在对集
合进行操作。
对集合的运算都可以用位运算符简单实现。
最
常见的二元运算是与（
&
）
、或（
|
）
、非
(!)
、异或（∧）
。
<
/p>
“异或（
XOR
）
”运算符∧，它的规则是“如果
A
和
B
不相同，则
A
∧
B
为
1
，否则为
< br>0
”
。
异或运算最重要的性质就
是“开关性”——异或两次以后相当于没有异或，即
A
∧
B
∧
B=A
。
由于
A&B
、
A|B
、
A
∧
B
分别对应着集合的交、
并和对称差。
另外，
空集为
0
，
全集
{0,1,2,
„
,
n
n-1}
的二进制为<
/p>
n
个
1
，即十进
制的
2
-1
。在程序中把全集定义为<
/p>
解，然后一一检查（
ALL_BITS=(1<
，则
A
的补集为
ALL_BITS
∧
A
。也可以直接用整数减法
ALL_BIT
S-A
表示，但速度比位运算慢。
提
示
7-3
：
当用二进制表示子集时，位
运算中的按位与、或、异或对应集合的交、并和
对称差。
输出子集
S
对应的各个元素的完整程序如下
：
#include
void print_subset(int n,
int s) { //
打印
{0, 1, 2,
..., n-1}
的子集
S
for(int i = 0; i < n; i++)
if(s&(1<
//
这里利用了
C
语言“非
0
值都为真”的规定
printf(
}
int
main() {
int n = 5;
n
for(int
i
=
0;
i
<
(1<
i++)
//
枚举各子集所对应的编码
0,
1,
2,
...,
2
-1
print_subset(n, i);
return 0;
}
7.4
回
溯
法
<
/p>
无论是排列生成还是子集枚举，
两种思路：
递归构造和直接遍历。
直接遍历的优点是思
路和程序都很简单
，
缺点在于无法简便地减少枚举量——必须生成
（
generate
）
所有可能的
test
）
。
另一方面，
在递归构造中，
生成和检查过程可以有机结合起来，
从而减少不必要的枚举，
这就是本节的主题——回溯法（
backtracking
）
。
回溯法是一种系统的搜
索问题的解的方法。
它的基本思想是：
从一条路前行，
能进则进，
不能进则退回来，换一条路再试。回溯法是一种通用的解题方
法。
应用回溯法的时候，首先明确定义问题的解空间。解空间
至少应该包含问题的一个解。
确定了解空间后，回溯法从开始结点出发，以深度优先的方
法搜索整个解空间。
对于回溯法一般可以采用递归方式来实现。
7.4.1
八皇后问题
在棋盘上放置
8
个皇后，
使得它们互不攻击，
此时每个皇后的攻击范围为同行同列和对
角线，要求找出所有解，如图
7-4
所示。
Q
Q
Q
Q
第
209
页
-
-