算法竞赛入门经典算法实现pdf,算法竞赛专题解析
目录
第七章暴力解法【教学内容相关章节】引用7.1简单单提升7.1.1除法7.1.2最大乘积7.1.3分数拆分7.1.4双基回文7.2提升行7.2.1生成1 ~ n排列7.2.2生成可重复排列。7.2.3答树7.2.4下一次排列7.3子集生成7.3.1增量构造7.3.3二进制方法7.4.1八皇后问题7.4.2素数环7.4.3难串7.4.4带宽7.5隐式图搜索7.5.1隐式树的遍历示例示例7-2埃及得分。节点查找表
第七章暴力解法【教学内容相关章节】7.1简单枚举7.2枚举排列7.3子集生成7.4回溯法7.5隐式图搜索
[教学目标]
(1)掌握整数、子串等简单对象的枚举方法；
(2)掌握排列生成的递归方法；
(3)掌握用“下一个排列”枚举所有排列的方法；
(4)了解解树，估算典型解树的节点数；
(5)掌握子集生成的增量法、位向量法和二进制法；
(6)精通回溯法的框架，并能理解为什么它往往比生成-测试法更有效率；
(7)掌握解树的广度优先搜索和迭代深化搜索；
(8)了解倒水问题的状态图与八皇后问题的解树的本质区别；
(9)掌握BFS实施的八个数字问题；
(10)熟悉集合的两种典型实现：——哈希表和STL集合。
[教学要求]
掌握整数、子串等简单对象的枚举方法；掌握排列生成的递归方法；掌握用“下一个排列”枚举所有排列的方法；理解子集树和树的排列；掌握回溯法的框架；掌握解树的广度优先搜索和迭代搜索；掌握集合的两种典型实现：——哈希表和STL集合。
【教学总结】
本章主要讨论暴力法(也叫穷举法、蛮力法)，要求设计者找出所有可能的方法，然后选择其中一种，如果这种方法不可行，就尝试下一种可能的方法。介绍了置换生成的递归方法。在求解过程中，提出了解树(如子集树和树的排列)的概念。介绍了回溯法的基本框架。介绍了set的两种典型实现：——哈希表和STL set。
【教学重点和难点】
教学重点：
(1)掌握排列生成的递归方法；
(2)了解解树，估算典型解树的节点数；
(3)掌握子集生成的增量法、位向量法和二进制法；
(4)精通回溯法的框架，并能理解为什么它往往比生成-检验法更有效率；
(5)掌握解树的广度优先搜索和迭代搜索；
(6)掌握集合的两种典型实现，——哈希表和STL集合。
教学难点：
(1)掌握子集生成的增量法、位向量法和二进制法；
(2)精通回溯法的框架，并能理解为什么它往往比生成-测试法更有效率；
(3)掌握解树的广度优先搜索和迭代搜索；
(4)掌握集合的两种典型实现：——哈希表和STL集合。
[课时安排]
7.1简单枚举7.2枚举排列7.3子集生成7.4回溯法7.5隐式图搜索
引用单词
暴力法，又称穷举法、蛮力法，要求设计者找出所有可能的方法，然后选择其中一种，如果这种方法不可行，就尝试下一种可能的方法。
暴力也是直接解决问题的方式，往往直接基于对问题的描述和对所涉及概念的定义。
暴力不是最好的算法，但当我们想不出更好的算法时，也是解决问题的有效方法。
暴力法的优点是逻辑清晰，编程简洁。在程序设计竞赛中，时间是短暂的。相比高效巧妙的算法，暴力法写的程序简单，解题更快。同时，蛮力方法也是很多算法的基础，可以在蛮力方法的基础上进行优化，得到更高效的算法。
而且在某些情况下，算法的规模并不大，不需要使用优化后的算法。而且优化后的一些算法本身就比较复杂，在没有规模的情况下可能会因为算法复杂而浪费时间，但是还不如单纯的暴力搜索。
暴力通常用于以下情况：
(1)搜索所有解空间；
(2)搜索所有路径；
(3)直接计算；
(4)模拟与仿真。
7.1简单提升
在枚举复杂对象之前，先尝试枚举一些相对简单的东西，比如整数和子串。暴力枚举通过分析问题使算法更加简洁高效。
7.1.1除法输入正整数n，按照从小到大的顺序输出abcde/fghij=n形式的所有表达式，其中a ~ j只是数字0 ~ 9的排列，2n79。
样本输入：
62
样本输出：
79546/01283=62
94736/01528=62
[分析]
你只需要枚举fghij来计算abcde，然后判断是否所有的数都不一样。不仅程序简单，枚举器也是从10！=362.88万减少到1万以内。可见，即使采用暴力枚举，也需要仔细分析问题。
完整的过程如下：
#包括
使用命名空间std
Bootest (int I，int J){//使用数组T存储I和J的位数。
int t[10]={ 0 }；//初始化数组T，使每个数字都是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；
}
//判断A ~ J是否正好是数字0 ~ 9的排列。
for(int m=0；m m)
for(int n=m ^ 1；n n)
if(t[n]==t[m])返回false
返回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 10000满足题目的条件，f位输出0。
if(test(j，k)) {
cout j /；
if(k 10000)cout 0 ；
Couk= n7.1.2最大乘积输入n个元素组成的序列S，你需要找到一个具有最大乘积的连续子序列。如果这个最大乘积不是正整数，它应该输出-1(表示无解)。1n18，-10Si10 .
样本输入：
三
2 4 -3
五
2 5 -1 2 -1
样本输出：
八
20
[分析]
一个连续的子序列有两个元素：起点和终点，所以只需要枚举起点和终点。由于每个元素的绝对值不超过10，总共不超过18个元素，因此最大可能乘积将超过1018，可以存储在long long中。
完整的过程如下：
#包括
#包括
int main(){
int a[20]；//存储输入序列的每个元素
int 64 ans=0；//存储最大的产品
int n；//输入元素的数量
int64 tmp//存储产品的中间结果
while(scanf(%d ，n)！=EOF){ //输入序列中元素的数量n
for(int I=0；I)//输入序列中的元素
scanf(%d ，a[I])；
for(int I=0；i i ) {
//从序列的第0个元素开始枚举最大连续乘积，用ans存储
tmp=1；
for(int j=I；j j ) {
tmp *=a[j]；
if(tmp ans)ans=tmp；
}
}
如果(回答0)
printf(%I64d\n ，ans)；
其他
printf(%d\n ，-1)；
}
返回0；
}7.1.3分数拆分7.1.3分数拆分
输入一个正整数k，求所有正整数xy，这样。
样本输入：
2
12
样本输出：
2
1/2=1/6 1/3
1/2=1/4 1/4
八
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，因为xy，所以有，所以y2k。这样你只需要在2k的范围内枚举Y，然后试着根据Y计算X。
完整的过程如下：
#包括
int main(){
int k；
int x，y，count=0；//变量count计算等式的数量
while(scanf(%d ，k)！=EOF) {
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){
数数；
}
}
printf(%d\n ，count)；//输出满足条件的方程个数
for(y=k ^ 1；y=2 * k；Y ){ //输出满足条件的方程
x=(k * y)/(y-k)；
if(x * (y - k)==k * y){
printf(1/%d=1/%d 1/%d\n ，k，x，y)；
}
}
}
返回0；
}7.1.4双基回文如果一个正整数n至少有两个不同的进位系统b1和b2，且都是回文(2b1，b210)，则称n为双基回文(注意回文不含前导零)。输入正整数S 106，输出大于S的最小双基回文。
样本输入：1600000
样本输出：1632995
[分析]
最自然的想法是从n ^ 1开始依次判断每个数是否是双基回文，判断时列举所有可能的基数(2 ~ 10)。令人惊讶的是，对于S 106的“小规模数据”来说已经足够快了。——的回文数量太大太密。
完整的过程如下：
#包括
使用命名空间std
布尔汇文(整数){
int i，j，a[30]，s；
int total=0；//存放数s是回文的底数。
for(int base=2；基数=10；基础){
I=1；
s=n；
while(s) {
a[i]=s %基数；
s=s/base；
我；
}
I-；
for(j=1；j=I/2；J) //判断数字s是否是基基下的回文
if(a[j]！=a[I-j 1])break；
if(j i/2)合计；//数字s是底数底数下的一个回文，那么总数
if(total=2)返回true
}
返回false
}
int main(){
int s；
while(scanf(%d ，s)==1) {
for(s=S1；s ) {
if(汇文(s)) {
cout s endl打破；
}
}
}
返回0；
}
7块成行排列。
输入整数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，2)，3，2，1
7.2.1生成1 ~ n的排列这个问题是用递归的思想解决的：先输出所有从1开始的排列(递归调用)，然后输出从2开始的排列(递归调用)，再输出从3开始的排列，…，最后输出从n开始的排列。
以1开头的排列特点是：第一个数字是1，后面是字典顺序的2 ~ 9的排列。因此，在设计递归函数时需要以下参数：
(1)确定输出的“前缀”序列；
(2)需要完全排列的元素的集合，以便依次被选为第一个元素。
就这样，写出下面的伪代码：
Void print_permutation(序列A，集合S) {
如果(S为空)输出序列A；
Else按照从小到大的顺序考虑s的每个元素v {的。
Print _ license (a，S-{v})末尾加V得到的新序列；
}
}
在上面的递归函数中，递归边界是s为空的情况，可以直接输出序列A；如果s不为空，考虑s中的每个元素从小到大，每个递归调用都以a开头。
考虑以下程序的实现。数组用来表示序列A，集合S可以完全由序列A确定，——A中没有出现的元素都可以选择。C语言中的函数在接受数组参数时无法获取数组中的元素个数，所以需要传递若干个填充位置或者待确定元素的当前位置cur。声明一个足够大的数组A，然后调用print _ permission (n，A，0)按照字典顺序输出1 ~ n的所有排列。
完整的过程如下：
#包括
int A[100]；
//输出全排列1 ~ n的递归函数
void print_permutation(int n，int* A，int cur) {
int i，j；
If(cur==n) {//递归边界
for(I=0；i i ) printf(%d ，A[I])；
printf( \ n )；
}
else for(I=1；I){//尝试在A[cur]中填入各种整数I
int ok=1；
for(j=0；j curj)
if(A[j]==I)ok=0；//如果I已经出现在A [0] ~ A [cur-1]中，就不能再选择了。
如果(正常){
a[cur]=I；
print_permutation(n，A，cur 1)；//递归调用
}
}
}
int main() {
print_permutation(4，A，0)；
返回0；
}在递归函数print_permutation中，循环变量I是当前认为的A[cur]。为了检查元素I是否已经被使用，还使用了标志变量ok。初始值为1(真)，如果找到某个A[j]==i，则改为0(假)。如果最后ok还是1，说明序列里从来没有出现过我。把它加到序列的末尾(A[cur]=i)，递归调用。
7.2.2生成可重置的排列。如果把问题改成：输入数组A，按字典顺序输出数组A中元素的所有排列，就需要把上面的递归函数print_permutation修改3354，把P加到print_permutation的参数表中，然后把代码中的if (a [j]i)和A[cur]=i改成if(A[j]只把P的所有元素按从小到大的顺序排序，然后调用print _ permission (n，P，A，0)。
但是在上面的递归函数print_permutation中，数组A是禁止重复的，但是p中可能会有重复的元素，所以输出数组A时会有问题。
解决方法是统计P[i]在A [0] ~ A [cur-1]中的出现次数c1和P[i]在P数组中的出现次数c2。只要c1 c2，就可以递归调用。
枚举的下标I应该取所有P[i]值，没有重复或遗漏。既然P的数组已经排序，那么只需要检查P的第一个元素和所有“与前一个元素不同”的元素，也就是只在for(I=0；I)和它后面的花括号前面是if(！我P[i]！=P[i-1])。
完整的过程如下：
#包括
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 i ) printf(%d ，A[I])；
printf( \ n )；
}
else for(I=0；我我)
如果(！我 P[i]！=P[i-1]) {
int c1=0，C2=0；
for(j=0；j curj)if(A[j]==P[I])C1；
for(j=0；j 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(%d ，
for(I=0；我我)
scanf(%d ，P[I])；
print_permutation(n，P，A，0)；
返回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)个… 21=n！一个。
为了推导方便，把n(n-1)(n-2)……(n-k)写成n！/(n-k-1)！所有节点的总和为：
根据高等数学中的泰勒展开式，所以T(n) n！e=O(n！)。因为叶子有N！倒数第二层还有个N！节点，所以上面的层都来自最后一两层，所以上面的节点数可以忽略不计。
7.2.4另一种枚举下一个排列中所有排列的方法是从字典顺序中最小的排列开始，不断调用“寻找下一个排列”的过程。c语言的STL中提供了一个库函数next_permutation。
完整的过程如下：
#包括
#包括
使用命名空间std
int main() {
int n，p[10]；
scanf(%d ，
for(int I=0；i i ) scanf(%d ，p[I])；
sort(p，p n)；//排序得到p的最小排列。
做{
for(int I=0；i i ) printf(%d ，p[I])；//输出排列p
printf( \ n )；
} while(next_permutation(p，p n))；//找到下一个排列
返回0；
}描述：(1)1)STL中有一个排序函数，可以直接对数组进行随机快速排序。复杂度为n*log2n，效率高。要使用这个函数，您需要包含头文件：
#包括
使用命名空间std其功能原型如下：
模板void排序(RandomAccessIterator在先，RandomAccessIterator在后)；
这个排序函数可以传递两个参数。第一个参数是要排序的区间的第一个地址，第二个参数是区间结束地址的下一个地址。即排序的区间为[a，b]。简单来说，有一个数组int a[100]。要从a[0]到a[99]对元素进行排序，只需编写sort(a，a 100)。默认的排序方法是升序。
如果需要对数组T从0到len-1的元素进行排序，写sort(t，T len)；向量v(定义向量v；)进行排序并写成sort(v.begin()、v . end())；排序的数据类型不限于整数，只要定义小于运算的类型即可，比如string类string。
模板类RandomAccessIterator，类StrictWeakOrdering
void sort(random accessiterator first，RandomAccessIterator last，StrictWeakOrdering comp)；
这个排序函数可以传递三个参数。第一个参数是要排序的区间的第一个地址，第二个参数是区间结束地址的下一个地址。即排序的区间为[a，b]。简单来说，有一个数组int a[100]。要从a[0]到a[99]对元素进行排序，只需编写sort(a，a 100)。默认的排序方法是升序。
如果没有数据类型小于操作定义，或者如果你想改变排序顺序，你需要使用第三个参数3354比较函数。比较函数是自定义函数，返回值为bool，指定“小于”是什么样的关系。要按降序对整数数组进行排序，可以先定义一个比较函数cmp。
bool cmp(int a，int b) {
返回a
}排序时写sort(a，a 100，CMP)；
(2)C语言STL中定义的next_permutation和prev_permutation函数是非常灵活有效的方法，被广泛用于为指定序列生成不同的排列。next_permutation和prev_permutation函数需要包含algorithm.h头文件。注意“如果你想遍历所有的排列，你必须先对元素进行排序”。
(3)根据STL文档，next_permutation函数将按字母顺序生成给定序列的下一个更大的排列，直到整个序列按降序排列。Prev_permutation函数则相反，是给定序列的最后一个较小的排列(前一个排列)。两者原理相同，但遍历顺序相反。这两个函数可以对整数数组或字符数组进行操作。
(4)next _置换函数原型
模板bool next _ permutation(BidIt first，BidIt last)；
模板类BidIt，类Pred布尔next_permutation(BidIt first，BidIt last，Compare comp)；
Next_permutation函数获取由[first，last]标记的排列，并将其重新排序为下一个排列。如果下一个排列不存在，则为假；被返回；否则，返回true。第一个版本()使用基础类型的小于运算符来确定下一个排列，第二个版本()根据comp对元素进行排序。如果原字符串是有序的，会不断调用next _ permission函数，生成整个next_permutation集合。prev_permutation函数的原型类似于next_permutation函数的原型。
7.3子集生成
本节介绍子集生成算法：给定一个集合，枚举其所有可能的子集。为简单起见，本节讨论的集合中没有重复的元素。
7.3.1增量构造法的第一个思路是一次选择一个元素，放入集合中。完整的过程如下：
#包括
void print_subset(int n，int* A，int cur) {
int I；
for(I=0；我诅咒；i ) printf(%d ，A[I])；//打印当前收藏
printf( \ n )；
int s=cur？a[cur-1]1:0；//确定当前元素的最小可能值
for(I=s；i i ) {
a[cur]=I；
print_subset(n，A，cur 1)；//递归构造子集
}
}
int A[10]；
int main() {
print_subset(5，A，0)；
返回0；
}注意：由于A中元素的个数是不确定的，所以每次递归调用时都会输出当前集合。此外，递归边界不需要明确确定。3354如果不能继续添加元素，就不会递归。
上面的代码使用了排序的技术：如果集合A中所有元素的编号都是从小到大排列的，那么集合{1，2}就不会按照{1，2}和{2，1}输出两次。
这个解树有1024个节点，因为每个可能的A对应一个节点，N个元素的集合正好有2n个子集，210=1024。
7.3.2位向量方法
第二个想法是构造位向量B[i]而不是直接构造子集A本身，其中B[i]=1当且仅当I在子集A中，完整过程如下：
#包括
void print_subset(int n，int* B，int cur) {
if(cur==n) {
for(int I=0；我诅咒；我)
if(B[i]) printf(%d ，I)；//打印当前收藏
printf( \ n )；
返回；
}
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)；
返回0；
}它必须是所有元素被选中后的完全子集，所以当if(cur==n)成立时输出。所有部分解决方案(不完整的解决方案)也对应于解决方案树上的节点。
这是一棵有n-1层(cur从0到n)的二叉树。0层有1个节点，1层有2个节点，2层有4个节点，3层有8个节点，…，I层有2i个节点，总共1 ^ 2 ^ 4…2n=2n ^ 1-1。图7-2是答案树。最后几层的节点数占整个树的绝大部分。
图7-2位向量方法的解决方案树
7.3.3二进制方法用二进制表示{0，1，2，…，n-1}的子集S:从右向左第I位(从0开始编号)表示元素I是否在集合S中。图7-3显示了二进制01000110011011如何表示集合{0，1，2，4，
5,9,10,14}.
图7-3用二进制表示子集
注意：为了处理方便，最右边的位总是对应元素0，而不是元素1。
技巧7-2:子集可以用二进制表示，其中从右到左的第I位(从0开始编号)表示元素I是否在集合中(1表示“in”，0表示“out”)。
不仅要表示集合，还要对集合进行操作。集合上的运算可以简单地用位运算符来实现。最常见的二元运算是AND()，或者()，而不是(！)，异或()。
“异或”运算符，其规则是“若A和B不同，则AB为1，否则为0”。异或运算最重要的性质是“交换”。3354异或两次相当于没有异或，即a b b=a。
因为A B，AB，AB分别对应集合的交，并，对称差。另外，空集为0，完备集{0，1，2，
n-1}的二进制是n ^ 1s，也就是十进制的2n-1。程序中完备集定义为ALL_BITS=(1 n)-1，那么A的补码是all _ bits A，也可以直接用整数减法ALL_BITS-A表示，但速度比位运算慢。
提示7-3:当子集用二进制表示时，按位运算中的按位与、或、异或对应于集合的交、并、对称差。
输出对应于子集S的每个元素的完整程序如下：
#包括
Void print_subset(int n，int s) {//打印{0，1，2，n-1}
for(int I=0；我我)
如果(s (1
7.4追溯方法
无论是排列生成还是子集枚举，都有递归构造和直接遍历两种思路。直接遍历的优点是思路和过程非常简单，缺点是枚举——不能简单化简。必须生成所有可能的解决方案，然后逐一测试。
另一方面，在递归构造中，可以将生成和检查过程有机地结合起来，从而减少不必要的枚举，这也是本节——回溯的主题。
回溯法是一种解决问题的系统搜索方法。它的基本思想是：走一条路，能走就走，不能走就走，走回头路，换一条路再试试。回溯法是一种通用的解题方法。
应用回溯法时，首先明确问题的解空间。解决方案空间应该包含问题的至少一个解决方案。知道空间后，回溯法从起始节点开始，用深度优先法搜索整个解空间。
一般来说，回溯法可以通过递归来实现。
7.4.1八皇后问题将八个皇后放在棋盘上，使它们不会互相攻击。此时每个皇后的攻击范围都是同一行同一对角线，需要所有的解决方案，如图7-4所示。
(一)女王的攻击范围(二)可行的解决方案
图7-4八皇后问题
分析]
思路一：把问题变成“从64个网格中选择一个子集”，这样“子集中正好有8个网格，任意两个选择的网格不在同一行、列或对角线上”。这是一个子集枚举问题，不是一个好的模型。
思路二：把问题变成“64格8格”，这是一个组合生成问题。比思思路好，但还是不太好。
想法三：根据分析，每行每列正好有一个皇后。如果用C[x]来表示x行中皇后的列数，问题就变成了生成全排列的问题。
技巧7-4:在写递归枚举程序之前，有必要对问题进行深入分析，对模型进行精细化。一般情况下，应该有一个对解决方案树中节点数量的粗略估计，作为评估模型的重要依据，如图7-5所示。
图7-5:四皇之后问题的求解树
图7-5显示了四皇后问题的完整解决方案树。它只有18个节点，比4个还多！=24小。原因是有些节点无法继续扩展。
在所有情况下，递归函数将不再递归调用自身，而是返回到上一次调用，这称为回溯。
技巧7-5:当问题被分成几个步骤递归求解时，如果当前步骤没有合法的选择，函数将返回到之前的递归调用。这种现象被称为回溯。为此，递归枚举算法常被称为回溯法，其应用非常普遍。
在主程序中读取n，为tot清除0，然后调用search(0)得到解的个数tot。当n=8，tot=92，状态空间的节点数nc=2057时。完整的过程如下：
#包括
int C[50]，tot=0，n，NC=0；
无效搜索(内部当前){
int i，j；
NC；//nc状态空间中的节点数
if(cur==n)tot；//递归边界。只要你来这里，所有的女王都不会冲突。
else for(I=0；i i ) {
int ok=1；
c[cur]=I；//尽量把cur线的皇后放在I列。
for(j=0；j curJ) //检查是否与前面的皇后冲突。
if(C[cur]==C[j] cur-C[cur]==j-C[j] cur C[cur]==j C[j]){
ok=0；
打破；
}
if(ok)搜索(cur 1)；//如果合法，继续递归
}
}
int main() {
scanf(%d ，
搜索(0)；
printf(%d\n ，tot)；
printf(%d\n ，NC)；
返回0；
}注意：既然是逐行摆放，女王肯定不会横着攻击，只要检查一下是否竖着斜着攻击就可以了。条件cur-c [cur]==j-c [j] cur C[cur]==j C[j]用来判断皇后(cur，C[cur])和(j，C[j])是否在同一条对角线上。这个原理可以在图7-26中说明。
(a)网格(x，y)的y-x值标识主对角线；(b)网格(x，y)的x-y值标识次对角线。
图7-6棋盘中的对角线符号
上面的程序也可以改进：用二维数组vist[2][]直接判断当前尝试的皇后所在的列和两条对角线上是否有其他皇后。注意主对角线标记y-x可能是负数，访问时要加N。完整的过程如下：
包括
int C[50]，vis[3][50]，tot=0，n，NC=0；
无效搜索(内部当前){
int i，j；
NC；
if(cur==n)tot；
else for(I=0；i i ) {
如果(！vis[0][i]！vis[cur I]！vis[2][cur-in]{
//用二维数组直接判断
c[cur]=I；//如果不打印解决方案，可以省略整个C数组
vis[0][I]=vis[1][cur I]=vis[2][cur-I n]=1；//修改全局变量
搜索(cur 1)；
vis[0][I]=vis[1][cur I]=vis[2][cur-I n]=0；//记住！一定要改回来。
}
}
}
int main() {
scanf(%d ，
memset(vis，0，sizeof(vis))；
搜索(0)；
printf(%d\n ，tot)；
printf(%d\n ，NC)；
返回0；
}以上程序的重点是vis数组的使用。vis数组指示哪些列、主对角线和次对角线已经被放置的皇后占据。未来的皇后不应该修改这些值。一般来说，如果在追溯方法中修改了辅助全局变量，它们必须恢复到原始状态(除非有意保留修改)。另外，调试前别忘了清空vis数组。
技巧7-6:回溯法中如果使用了辅助全局变量，必须及时恢复到原来的状态。例如，如果一个函数有多个出口，修改后的值应该在每个出口被恢复。
7.4.2素数环输入正整数N，形成整数1，2，3，…，N的环，使两个相邻整数之和为素数。当输出从整数1开始时，按逆时针方向排列。同一个铃声应该只输出一次。n16 .
样本输入：
六
样本输出：
1 4 3 2 5 6
1 6 5 2 3 4
[分析]
其实素数问题的程序主要由求素数和整数1，2，3，…，n的排列组成，生成-测试法的完整流程如下：
#包括
#包括
使用命名空间std
is int is _ prime(int x){///判断整数x是否为素数
for(int I=2；我*我我)
if(x % i==0)返回0；
返回1；
}
int main() {
int n，A[50]，ISP[50]；
scanf(%d ，
for(int I=2；I=n * 2；I) //生成素数表，加速后续判断。
ISP[I]=is _ prime(I)；
for(int I=0；I I)A[I]=I 1；//第一种排列
做{
int ok=1；
for(int I=0；我我)如果(！ISP[a[I]a[(I 1)% n]]{//判断合法性
ok=0；
打破；
}
如果(正常){
for(int I=0；i i ) printf(%d ，A[I])；//输出序列
printf( \ n )；
}
}while(next_permutation(A 1，A n))；
返回0；
}跑了之后发现n=12的时候已经很慢了，但是n=16的时候根本出不去。下面采用回溯法来解决这个问题。追溯方法的完整过程如下：
#包括
#包括
#包括
使用命名空间std
is int is _ prime(int x){///判断整数x是否为素数
for(int I=2；我*我我)
if(x % i==0)返回0；
返回1；
}
int n，A[50]，isp[50]，vis[50]；
void dfs(int cur) {
If(cur==n isp[A[0] A[n-1]]) {//递归边界，不要忘记测试第一个数和最后一个数。
for(int I=0；i i ) printf(%d ，A[I])；
printf( \ n )；
}
else for(int I=2；I)//尝试放置每个数字I。
如果(！vis[i] isp[i A[cur-1]]) {
//如果I没有被使用，并且与前一个数的和是素数
a[cur]=I；
vis[I]=1；//设置标志
DFS(cur 1)；
vis[I]=0；//清除标志
}
}
int main() {
scanf(%d ，
for(int I=2；I=n * 2；I)ISP[I]=is _ prime(I)；
memset(vis，0，sizeof(vis))；
a[0]=1；
外勤支助部(1)；
返回0；
}经过测试，回溯法比生成测试法要快得多。回溯法是先按深度顺序遍历解树。
7.4.3难字符串如果一个字符串包含两个相邻的重复子字符串，则称为“易字符串”，其他字符串称为“难字符串”。
输入正整数n和l，输出一个由第k个最小字典顺序的前l个字符组成的难串。例如，当L=3时，前七个难弦是：A，AB，ABA，ABAC，ABACA，ABACAB，ABACABA。确保输入的字符答案不超过80个字符。
样本输入：
7 3
30 3
样本输出：
阿巴卡巴
阿巴卡巴卡巴巴
[分析]
从左到右考虑每个位置的字符。所以主要问题是如何判断当前字符串中是否有连续重复的子串。你只需要判断当前字符串的后缀，而不是所有的子字符串。
完整的过程如下：
#包括
int n，L，CNT=0；
int S[100]；
Int dfs(int cur) {//返回0表示已经得到解，不需要继续搜索。
if(cnt==n) {
for(int I=0；我诅咒；i ) printf(%c ， A S[I])；//输出方案
printf( \ n )；
返回0；
}
for(int I=0；i i ) {
s[cur]=I；
int ok=1；
for(int j=1；j * 2=cur 1；J) {//尝试长度为j*2的后缀
int equal=1；
for(int k=0；k)//检查后半部分是否等于前半部分
if(S[cur-k]！=S[cur-k-j]){ equal=0；打破；}
if(等于){ ok=0；打破；}//后半部分等于前半部分，方案不合法。
}
如果(ok)如果(！dfs(cur 1))返回0；//递归搜索。如果已经找到解决方案，直接退出。
}
返回1；
}
int main() {
scanf(%d%d ，n，
DFS(0)；
返回0；
}7.4.4带宽给出一个图G，有n个节点，一个节点的排列。定义节点I的带宽b(i)为I与排列中相邻节点的最远距离，所有b(i)的最大值为整个图的带宽。给定图G，找出带宽最小的节点排列。
[分析]
可以记录到目前为止找到的最小带宽k。如果发现某两个节点之间的距离大于等于k，那么无论怎么扩展，都不可能比当前解更好，就要强行切断，也就是剪枝解树。
除此之外，你还可以剪掉更多的枝叶。如果在搜索节点U时，U节点中仍有M个相邻节点的位置尚未确定，则节点U的理想情况是这M个节点紧跟在U后面，这类节点的带宽为M，而任何其他“非理想情况”的带宽至少为M-1。这样，如果mk，也就是“在最理想的情况下，得不到比当前最优解更好的解”，显然应该进行剪枝。
7.5隐式图形搜索
很多问题都可以用图遍历算法来解决，但是这些问题的图并不是事先给定并从程序中读取的，而是由程序动态生成的。
7.5.1隐式树的遍历到目前为止，本章所有的解树都有yes树，有严格的“层次”概念。——从根往下走，永远回不到根节点。
回溯法是深度优先顺序遍历，它的优点是节省空间：只需要保存递归栈中的节点。换句话说，回溯法的空间开销与所访问的最深节点的深度成正比。
树不仅可以在深度上遍历，也可以在宽度上遍历。好处是找到的第一个解一定是离根最近的解，但是空间开销大大增加(队列中节点很多)。
例7-1最佳程序。有一台计算机只有一个数据栈，支持整数的五种运算：加、除、乘、除、DUP。假设栈顶的三个元素分别是A、B、C，五个操作的效果如下：
加法：A和B依次从堆栈中出来，计算A和B，将结果堆栈。
Sub: A和B依次出栈，计算b-a，将结果堆栈。
Mul: A和B依次从堆栈中出来，计算ab，将结果堆栈。
Div: A和B依次从栈中出来，计算b/a并向下舍入，将结果推送到栈中。
Dup: A出栈，然后连续按下两个A。
以下情况之一，机器会产生错误：执行DIV操作时，栈顶元素为0；执行ADD、SUB、MUL、DIV操作时，堆栈中只有一个元素；运算结果的绝对值大于30000。
给定N个整数对(ai，bi)(ai互不相同)，你的任务是设计一个最短的程序，使得对于1到N之间的所有I，如果程序执行前堆栈中只有一个元素ai，那么执行后堆栈的顶元素就是bi。n5 .
[分析]
追溯的方法是没有办法解决这个问题的。这个问题的答案树是无限的，所有只要——的程序都是合法的。最简单可行的求最短方案的方法是先用宽度遍历解树。
例7-2埃及得分。在古埃及，人们用单位分数的和(如1/a，a是自然数)来表示所有的有理数。比如2/3=1/2 1/6，但是2/3=1/3 1/3是不允许的，因为在加数中同样是不允许的。
对于一个分数a/b，有很多种表达方式，其中加数越少越好。如果加数相同，分数越小越好。比如19/45=1/5 1/6 1/18就是最佳解。
输入整数a，b(0 a b 1000)，试着编程计算出最佳表达式。
[分析]
这个问题的解决方法是采用迭代深化搜索：从小到大枚举深度d的上限，一次只考虑不超过d的节点。这样，只要解的深度有限，就可以在有限的时间内枚举出来。
深度上限也可用于修剪。按照分母增大的顺序展开。如果扩展到I级时，前I个分数之和为c/d，第I个分数为1/e，那么至少需要(a/b-c/d)/(1/e)个分数才能达到a/b，利用上述算法，题目规模内的任何数据都可以快速求解。
7.5.2一般隐式图的遍历
有很多问题很难建立严格层次的解树，所以状态之间的关系只能理解为一般意义上的图。
例7-3倒水问题。
有装满水的6升杯子，3升杯子和空的1升杯子。三个杯子里都没有秤。不使用其他道具可以量4升水吗？
如图7-7所示。
图7-7倒水问题：一种方法是(6，0，0)(3，3，0)(3，2，1)(4，2，0)
注意：由于没有刻度，从X杯向Y杯倒水必须持续到Y杯满或X杯空，不能中途停止。
你的任务是解决一般问题：将大、中、小杯子的容量分别设为A、B、C。刚开始只有大杯装了水，其他两个杯子都是空的。在某个杯子里得到x升水至少需要多少步？你们
每次操作后，你需要打印出每个杯子里的水量(0 c b a 1000)。
[分析]
假设在某一时刻，大杯中有v0水，中杯有v1水，小杯中有v2水，此时的系统状态称为(v0，v1，v2)。把“状态”想象成图中的一个节点，就可以得到如图7-8所示的stata图。
图7-8倒水问题状态图
注意，图7-8所示的状态图和迷宫是不同的。在迷宫里，只有当你能成功上去的时候，你一定会回到你刚刚离开的地方，但是这个图不一样：从(4，2，0)的状态，把中杯的水倒进大杯里，你可以一步到达(6，0，0)，但是你不能从(6，0，0)一步到达(4，2，0)。换句话说，迷宫图是无向图，而反转状态图是有向图。
不管怎么倒，杯子里的水量都是一个整数(按倒的次数相加)，所以杯子里少量的水最多只有c 1种可能：0，1，2，…，c；同样，中杯的水量只有b 1种可能，大杯只有a 1种可能，所以理论上状态最多有(a 1)(b 1)(c 1)种可能。但是，由于水的量X永远不变，所以如果两种状态的小杯和中杯的小量相同，那么大杯的小量也相同。换句话说，最大可能状态数不会超过(b 1)(c 1)，所以节点数不会超过106。
完整的过程如下：
#包括
#包括
#定义MAXN 105
int cap[3]，x；
int vis[MAXN][MAXN]；
结构节点{
int v[3]；
int fa，dist，last _ op
};
节点q[MAXN * MAXN]；
void print_path(int idx) {
if(q[idx].法！=idx)
print_path(q[idx].fa)；
printf(%d %d %d\n ，q[idx])。v[0]，q[idx]。v[1]，q[idx]。v[2])；
}
void bfs() {
int front=0，rear=1，I，j，k；
q[0]。v[0]=cap[0]；
q[0]。v[1]=q[0]。v[2]=q[0]。dist=q[0]。fa=0；
vis[0][0]=1；
While(前面7.5.3八个数字问题
8个编号为1 ~ 8的方形滑块排成三行三列(一种格式留白)，如图7-9所示。每次你都可以将滑块移动到与该空间相邻的位置(只有当它有一个公共边时)到该空间，并且它的原始位置变成一个新的空间。给定初始情境和目标情境(0表示空间)，你的任务是计算最少的移动步数。如果无法达到目标情况，输出-1。
图7-9八个数字问题的例子
样本输入：
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
样本输出：
31
[分析]
八个数字的问题简化为图上的最短路径问题，其中每个状态都是九种格式的滑块数字(将它们从上到下、从左到右放入九个元素的数组中)。具体程序如下：
#包括
typedef int State[9]；//定义“状态”类型
const int MAXSTA
TE = 1000000;
State st[MAXSTATE], goal; //状态数组。所有状态都保存在这里
int dist[MAXSTATE]; //距离数组
//如果需要打印方案，可以在这里加一个“父亲编号”数组int fa[MAXSTATE]
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
//BFS，返回目标状态在st数组下标
int bfs() {
init_lookup_table(); //初始化查找表
int front = 1, rear = 2; //不使用下标0,因为0被看作“不存在”
while(front rear) {
State s = st[front]; //用“引用”简化代码
if(memcmp(goal, s, sizeof(s)) == 0) //找到目标状态，成功返回
return front;
int z;
for(z = 0; z z++) if(!s[z]) break; //找“0”的位置
int x = z/3, y = z%3; //获取行列位置（0～2）
for(int d = 0; d d++) {
int newx = x + dx[d];
int newy = y + dy[d];
int newz = newx * 3 + newy;
if(newx = 0 newx 3 newy = 0 newy 3) { //如果移动合法
State t = st[rear];
memcpy( t, s, sizeof(s)); //扩展新结点
t[newz] = s[z];
t[z] = s[newz];
dist[rear] = dist[front] + 1; //更新新结点的距离值
if(try_to_insert(rear)) rear++; //如果成功插入查找表，修改队尾指针
}
}
front++; //扩展完毕后再修改队首指针
}
return 0; //失败
}注意，此处用到了string.h中的memcmp和memcpy完成整块内存的比较和复制，比用循环比较和循环赋值要快。主程序很容易实现：
int main() {
for(int i = 0; i i++) //起始状态
scanf("%d", st[1][i]);
for(int i = 0; i i++) //目标状态
scanf("%d", goal[i]);
int ans = bfs(); //返回目标状态的下标
if(ans 0) printf("%d\n", dist[ans]);
else printf("-1\n");
return 0;
}注意，在调用bfs函数之前设置好st[1]和goal。对于上面的程序还有init_lookup_tab
le()和try_to_insert(rear)没有实现，这两个函数的功能是初始化查找表和插入元素。在查找表中，避免将同一个结点访问多次，所以要判重复，如果不判重复，时间和空间将产生极大的浪费。这两个函数将会在下节讲到。
7.5.4 结点查找表下面通过3种方法来解决空间浪费的问题，同时将它们用到八数码问题中。
（1）方法一
把排列“变成”整数，然后只开一个一维数组。即设计一套排列的编码（encoding）和解码（decoding）函数，把0～8的全排列和0～362879的整数一一对应起来。
int vis[36288], fact[9];
void init_lookup_table() {
fact[0] = 1;
for(int i = 1; i i++) fact[i] = fact[i-1] * i;
}
int try_to_insert(int s) {
int code = 0; //把st[s]映射到整数code
for(int i = 0; i i++) {
int cnt = 0;
for(int j = i+1; j j++)
if(st[s][j] st[s][i]) cnt++;
code += fact[8-i] * cnt;
}
if(vis[code]) return 0;
return vis[code] = 1;
}说明：上面尽管原理巧妙，时间效率也非常高，但编码解码法的适用范围不大：如果隐式图的总结数非常大，编码也将会很大，数组还是存不下。
（2）方法二
使用哈希（hash）技术。只需要设计一个所谓的哈希数h(x)，然后将任意结点x映射到某个给定范围[0,M-1]的整数即可，其中M是程序员根据可用内存大小自选的。在理想情况下，只需开一个大小为M的数组就能完成判重，但此时往往会有不同结点的哈希值相同，因此需要把哈希值相同的状态组织成链表。
const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE], next[MAXSTATE];
void init_lookup_table() { memset(head, 0, sizeof(head)); }
int hash(State s) {
int v = 0;
for(int i = 0; i i++) //随便算。例如，把9个数字组合成9位数
v = v * 10 + s[i];
return v % MAXHASHSIZE; //确保hash函数值不超过hash表的大小的非负整数
}
int try_to_insert(int s) {
int h = hash(st[s]);
int u = head[h]; //从表头开始查找链表
while(u) {
if(memcmp(st[u], st[s], sizeof(st[s])) == 0) //找到了，插入失败
return 0;
u = next[u]; //顺着链表继续找
}
next[s] = head[h]; //插入到链表中
head[h] = s;
return 1;
}哈希表的执行效率高，适用范围广，还可以用到其它需要快速查找的地方。在哈希表中，对效率起到关键作用的是哈希函数。
3）方法三
用STL的集合。setvis表示是声明了一个类型为State的集合vis。只需要if(
vis.count(s))来判断s是否在集合vis中，并用vis.insert(s)把s加入集合，用vis.remove
(s)从集合中移除s。STL要求set地元素类型必须定义“ ”运算符，如int、string或前面自定义的bign，但C语言原生的数组（包含字符数组）却不行。下面是一种使用int的方法：
set vis;
void init_lookup_table() { vis.clear(); }
int try_to_insert(int s) {
int v = 0;
for(int i = 0; i i++) v = v * 10 + st[s][i];
if(vis.count(v)) return 0;
vis.insert(v);
return 1;
}有很多情况下，数组是没有办法简单转化成整数的，自已声明一个结构体，并重载“括号”来比较两个状态。在下面的程序中，整数a和b分别是两个状态在状态数组st中的下标，在比较时直接使用memcpy来比较整个内存块。
struct cmp{
bool operator()(int a, int b) const{ //重新定义a vis; //使用新的“a说明：调用memcmp比直接比较两个整数要慢得多。使用STL集合的代码最简单，但时间效率也最低。所以建议在时间紧迫或对效率要求不太高的情况下使用，或者仅仅把它作为“跳板”——先写一个STL版的程序，确保主算法正确，然后把set替换成自己写的哈希表。
本 章 小 结
本章介绍了在解决实际问题中的一种方法是暴力法，就是把问题中所有可能性一一列举出来。但是对于有些问题的解空间非常大，要是只用暴力法在有限的时间求出解，不可能的。所以与剪枝函数相结合，剪去解空间树中不符合问题的解，从而减少程序的运行时间。这就是解决实际问题的另一种方法叫回溯法，它也是解决实际问题的一种方法。
对每一个内容进行了相关的题目的讲解，给出了分析过程和源程序，还给出在解决问题的一些小技巧，这对进行在线练习非常有用。
布 置 作 业
可以在UVaOJ上进行在线练习。如果能完成总题目的80%，说明对暴力法求解法的掌握就比较扎实。可以练习8道基础题、14道回溯法题、12道（难）回溯法题、6道隐式图搜索题、7道哈希表题。
Talk is cheap. Show me the code
© ©
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。