第7章暴力求解法
【教学内容相关章节】
7.1简单枚举 7.2枚举排列 7.3子集生成
7.4回溯法 7.5隐式图搜索
【教学目标】
（1）掌握整数、子串等简单对象的枚举方法；
（2）熟练掌握排列生成的递归方法；
（3）熟练掌握用“下一个排列”枚举全排列的方法；
（4）理解解答树，并能估算典型解答树的结点数；
（5）熟练掌握子集生成的增量法、位向量法和二进制法；
（6）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（7）熟练掌握解答树的宽度优先搜索和迭代加深搜索；
（8）理解倒水问题的状态图与八皇后问题的解答树的本质区别；
（9）熟练掌握八数码问题的BFS实现；
（10）熟练掌握集合的两种典型实现——hash表和STL集合。
【教学要求】
掌握整数、子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用“下一个排列”枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握解答树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现——hash表和STL集合。【教学内容提要】
本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的递归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的基本框架；介绍了集合的两种典型实现——hash表和STL集合。
【教学重点、难点】
教学重点：
（1）熟练掌握排列生成的递归方法；
（2）理解解答树，并能估算典型解答树的结点数；
（3）熟练掌握子集生成的增量法、位向量法和二进制法；
（4）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（5）熟练掌握解答树的宽度优先搜索和迭代搜索；
（6）熟练掌握集合的两种典型实现——hash表和STL集合。
教学难点：
（1）熟练掌握子集生成的增量法、位向量法和二进制法；
（2）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（3）熟练掌握解答树的宽度优先搜索和迭代搜索；
（4）熟练掌握集合的两种典型实现——hash表和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的一个排列，2≤n≤79。
样例输入：
62
样例输出：
79546/01283=62
94736/01528=62
【分析】
只需要枚举fghij就可以计算出abcde，然后判断是否所有数字都不相同即可。不仅程序简单，而枚举量也从10!=3628800降低至不到1万。由此可见，即使采用暴力枚举，也是需要认真分析问题。
完整的程序如下：
#include
using namespace std;
bool test(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 < 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<10000，满足题目的条件，f位置输出0
if(test(j,k)) {
cout << j << "/" ;
if(k < 10000) cout <<"0";
cout << k << "=" << n < } } ++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 【分析】 连续子序列有两个要素：起点和终点，因此只需要枚举起点和终点即可。由于每个元素的绝对值不超过10，一共又不超过18个元素，最大可能的乘积示会超过1018，可以用long long存下。 完整的程序如下： #include int main(){ int a[20]; //存放输入序列的每一个元素 __int64 ans = 0; //存放最大的乘积 int n; //输入元素的个数 __int64 tmp； //存放乘积的中间结果 while(scanf("%d",&n)!=EOF){ //输入序列中元素的个数n for(int i = 0;i < n; i++) //输入序列中的元素 scanf("%d",&a[i]); for(i = 0; i < n; i++) { //从序列中的第0个元素开始，枚举最大连续乘积，并用ans存储 tmp = 1; for(int j = i; j < n; j++) { tmp *= a[j]; if(tmp > ans) ans = tmp; } } if(ans>0) printf("%I64d\n",ans); else printf("%d\n",-1); } return 0; } 7.1.3 分数拆分 输入正整数k，找到所有的正整数x≥y，使得111 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，有11 x y ≤，因此 111 k y y -≤，即y≤2k。这样，只需要在2k范围内枚 举y，然后根据y尝试计算出x即可。 完整的程序如下： #include 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){ count++; } } 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); } } } return 0; } 7.1.4 双基回文数 如果一个正整数n至少有两个不同的进位制b1和b2下都是回文数（2≤b1,b2≤10），则称n是双基回文数（注意，回文数不以包含前导零）。输入正整数S<106，输出比S大的最小双基回文数。 样例输入：1600000 样例输出：1632995 【分析】 最自然的想法是：从n+1开始依次判断每个数是否为双基回文数，而在判断时要枚举所有可能的基数（2～10）。意外的是：对于S<106的“小规模数据”来说是足够快的——双基回文数太多太密。 完整的程序如下： #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("%d",&s) == 1) { for(s = s+1; ; s++) { if(huiwen(s)) { cout << s << endl; break; } } } 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～n的排列 对此问题用递归的思想解决：先输出所有以1开头的排列（递归调用），然后输出以2开头的排列（递归调用），接着以3开头的排列，…，最后才是以n开头的排列。 以1开头的排列的特点是：第一位是1，后面是按字典序的2～9的排列。所以在设计递归函数需要以下参数： （1）已经确定的“前缀”序列，以便输出； （2）需要进行全排列的元素集合，以便依次选做第一个元素。 这样，写出以下的伪代码： void print_permutation(序列A，集合S) { if(S为空) 输出序列A; else 按照从小到大顺序依次考虑S的每个元素v { print_permutation(在A的末尾填加v后得到的新序列，S-{v}); } } 上面的递归函数中递归边界是S为空的情形，可以直接输出序列A；若S不为空，则按从小到大的顺序考虑S中的每个元素，每次递归调用以A开头。 下面考虑程序的实现。用数组表示序列A，集合S可以由序列A完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法得到数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置cur。声明一个足够大的数组A，然后调用print_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("%d ", A[i]); printf("\n"); } else for(i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i int ok = 1; for(j = 0; j < cur; j++) if(A[j] == i) ok = 0; // 如果i已经在A[0]～A[cur-1]出现过，则不能再选 if(ok) { A[cur] = i; print_permutation(n, A, cur+1); // 递归调用 } } } int main() { print_permutation(4, A, 0); return 0; } 在递归函数print_permutation中循环变量i是当前考虑的A[cur]。为了检查元素i 是否已经用过，还用到了一个标志变量ok，初始值为1（真），如果发现有某个A[j]==i时，则改为0（假）。如果最终ok仍为1，则说明i没有在序列中出现过，把它添加到序列末尾（A[cur]=i）后递归调用。 7.2.2 生成可重集的排列 如果把问题改成：输入数组A，并按字典序输出数组A各元素的所有全排列，则需要对上述递归函数print_permutation修改——把P加到print_permutation的参数列表中，然后把代码中的if(A[j]==i)和A[cur]=i分别改成if(A[j]==P[i])和A[cur]=P[i]。只有把P 的所有元素按从小到大的顺序排序，然后调用print_permutation(n,P,A,0)即可。 但是上述递归函数print_permutation中，禁止A数组中出现重复，而在P中可能就有重复元素时，所以输出数组A时就会出现问题。 解决方法是统计A[0]～A[cur-1]中P[i]的出现次数c1，以及P数组中P[i]的出现次数c2。只要c1 枚举的下标i应不重复、不遗漏地取遍所有P[i]值。由于P数组已经排过序，所以只需检查P的第一个元素和所有“与前一个元素不相同”的元素，即只需在for(i=0;i 完整的程序如下： #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("%d ", A[i]); printf("\n"); } 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("%d", &n); for(i = 0; i < n; i++) scanf("%d", &P[i]); 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)写成n!/(n-k-1)!，则所有结点之和为： 1 11 000!11 ()!!(1)!(1)!! n n n k k k n T n n n n k n k k ---======----∑∑∑ 根据高等数学中的泰勒展开公式，1 01 lim ! n x k e k -→∞ ==∑，因此T(n) 有n!个，倒数第二层也有n!个结点，因此上面的各层全部来源于最后一两层，所以上面的结点数可以忽略不计。 7.2.4 下一个排列 枚举所有排列的另一个方法是从字典序最小排列开始，不停调用“求下一个排列”的过程，在C++的STL 中提供了一个库函数next_permutation 。 完整的程序如下： #include for(int i = 0; i < n; i++) scanf("%d", &p[i]); sort(p, p+n); // 排序，得到p 的最小排列 do { for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p printf("\n"); } while(next_permutation(p, p+n)); // 求下一个排列 return 0; } 说明：（1）STL 里面有个sort 函数，可以直接对数组进行随机化快速排序，复杂度为n*log 2n ，效率高。使用这个函数，需要包含头文件： #include 它的函数原型如下： ①template void sort(RandomAccessIterator first, RandomAccessIterator last); 这个sort函数可以传两个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。 如果需要对数组t的第0到len-1的元素排序，就写sort(t,t+len);，对向量v(定义vector ②template 这个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中定义的next_permutation和prev_permutation函数则是非常灵活且高效的方法，它被广泛的应用于为指定序列生成不同的排列。next_permutation和prev_permutation函数需要包含algorithm.h头文件。需要注意的是“如果要走遍所有的排列，必须先将元素排序”。 （3）按照STL文档的描述，next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。 prev_permutation函数与之相反，是生成给定序列的上一个较小的排列（前一个排列）。二者原理相同，仅遍历顺序相反。这两个函数据可以对整型数组或字符数组操作。 （4）next_permutation函数原型 ①template ②template next_permutation函数取由[first,last)标记的排列，并将其重新排序为下一个排列。如果不存在下一个排列，则返回false；否则，返回true。第一个版本（①）使用底层类型的小于操作符来确定下一个排列，第二个版本（②）根据comp对元素进行排序。如果原始字符串是排过序的，则连续调用next_permutation函数会生成整个排列集合。prev_permutation函数原型与next_permutation函数型类似。 7.3 子集生成 本节介绍子集生成算法：给定一个集合，枚举它所有可能的子集。为了简单起见，本节讨论的集合中没有重复元素。 7.3.1 增量构造法 第一种思路是一次选出一个元素放到集合中，完整程序如下： #include void print_subset(int n, int* A, int cur) { int i; for(i = 0; i < cur; i++) printf("%d ", A[i]); // 打印当前集合 printf("\n"); 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}和{2,1}输出两次了。 这棵解答树上有1024个结点，由于每个可能的A都对应一个结点，而n元素集合恰好有2n个子集，210=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("%d ", i); // 打印当前集合 printf("\n"); 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～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展示了二进制010001100011011是如何表示集合{0,1,2,4, 5,9,10,14}的。 图7-3 用二进制表示子集 注意：为了处理方便，最右边那个位总是对应元素0，而不是元素1。 提示7-2：可以用二进制表示子集，其中从右往左第i位（从0开始编号）表示元素i 是否在集合中（1表示“在”，0表示“不在”）。 不仅要表示集合，还在对集合进行操作。对集合的运算都可以用位运算符简单实现。最常见的二元运算是与（&）、或（|）、非(!)、异或（∧）。 “异或（XOR）”运算符∧，它的规则是“如果A和B不相同，则A∧B为1，否则为0”。异或运算最重要的性质就是“开关性”——异或两次以后相当于没有异或，即A∧B∧B=A。 由于A&B、A|B、A∧B分别对应着集合的交、并和对称差。另外，空集为0，全集{0,1,2,…, n-1}的二进制为n个1，即十进制的2n-1。在程序中把全集定义为ALL_BITS=(1< 提示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< } int main() { int n = 5; for(int i = 0; i < (1< return 0; } 7.4 回溯法 无论是排列生成还是子集枚举，两种思路：递归构造和直接遍历。直接遍历的优点是思路和程序都很简单，缺点在于无法简便地减少枚举量——必须生成（generate）所有可能的解，然后一一检查（test）。 另一方面，在递归构造中，生成和检查过程可以有机结合起来，从而减少不必要的枚举，这就是本节的主题——回溯法（backtracking）。 回溯法是一种系统的搜索问题的解的方法。它的基本思想是：从一条路前行，能进则进，不能进则退回来，换一条路再试。回溯法是一种通用的解题方法。 应用回溯法的时候，首先明确定义问题的解空间。解空间至少应该包含问题的一个解。确定了解空间后，回溯法从开始结点出发，以深度优先的方法搜索整个解空间。 对于回溯法一般可以采用递归方式来实现。 7.4.1 八皇后问题 在棋盘上放置8个皇后，使得它们互不攻击，此时每个皇后的攻击范围为同行同列和对 图7-4 八皇后问题 【分析】 思路一：把问题转化为“从64个格子中选一个子集”，使得“子集中恰好有8个格子，且任意两个选出的格子都不在同一行、同一列或同一个对角线上”。这是子集枚举问题，不是一个好的模型。 思路二：把问题转化为“从64个格子中选8个格子”，这是组合生成问题。比思路一好，但是仍然不是很好。 思路三：由分析可得，恰好每行每列各放置一个皇后。如果用C[x]表示第x行皇后的列编号，则问题变成了全排列生成问题。 提示7-4：在编写递归枚举程序之前，需要深入分析问题，对模型精雕细琢。一般还应对解答树的结点数有一个粗略的估计，作为评价模型的重要依据，如图7-5的所示。 图7-5 在四皇后问题的解答树 图7-5中给出了四皇后问题的完整解答树。它只有18个结点，比4!=24小。原因是有些结点无法继续扩展。 在各种情况下，递归函数将不再递归调用本身，而是返回上一层调用，称这种现象为回溯（backtracking）。 提示7-5：当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。正是因为这个原因，递归枚举算法常称为回溯法，它的应用十分普遍。 在主程序中读入n，并为tot清0，然后调用search(0)，即可得到解的个数tot。当 n=8，则tot=92,状态空间结点数nc=2057。完整的程序如下： #include int C[50], tot = 0, n, nc = 0; void search(int cur) { int i, j; nc++; //nc状态空间结点数 if(cur == n) tot++; //递归边界。只要走到了这里，所有皇后必然不冲突 else for(i = 0; i < n; i++) { int ok = 1; C[cur] = i; //尝试把cur行的皇后放在第i列 for(j = 0; j < cur; j++) //检查是否和前面的皇后冲突 if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]) { ok = 0; break; } if(ok) search(cur+1); //如果合法，则继续递归 } } int main() { scanf("%d",&n); search(0); printf("%d\n", tot); printf("%d\n", nc); return 0; } 注意：既然是逐行放置的，则皇后肯定不会横向攻击，因此只需检查是否纵向和斜向攻击即可。条件cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]用来判断皇后(cur,C[cur])和 图7-6 棋盘中的对角线标识 上面的程序还可改进：利用二维数组vist[2][]直接判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。注意到主对角线标识y-x可能为负，存取时要加上n。完整的程序如下： Include int C[50], vis[3][50], tot = 0, n, nc = 0; void search(int cur) { int i, j; nc++; if(cur == n) tot++; else for(i = 0; i < n; i++) { if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) { //利用二维数组直接判断 C[cur] = i; //如果不打印解，整个C数组都可以省略 vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1; //修改全局变量 search(cur+1); vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; //切记！一定要改回来 } } } int main() { scanf("%d",&n); memset(vis, 0, sizeof(vis)); search(0); printf("%d\n", tot); printf("%d\n", nc); return 0; } 上面的程序关键的地方是vis数组的使用。vis数组表示已经放置的皇后占据了哪些列、主对角线和副对角线。将来放置的皇后不应该修改这些值。一般地，如果要回溯法中修改了辅助的全局变量，则一定要及进把它们恢复原状（除非故意保留修改）。另外，千万不要忘记在调试之前把vis数组清空。 提示7-6：如果在回溯法中使用了辅助的全局变量，则一定要及时把它们恢复原状。例如，若函数有多个出口，则需在每个出口处恢复被修改的值。 7.4.2 素数环 输入正整数n，把整数1,2,3,…,n组成一个环，使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n≤16。 样例输入： 6 样例输出： 1 4 3 2 5 6 1 6 5 2 3 4 【分析】 素数环问题的程序实际上主要由求素数和整数1,2,3,…,n的排列构成。生成-测试法的完整程序如下： #include #include using namespace std; int is_prime(int x) { //判数一个整数x是否是一个素数 for(int i = 2; i*i <= x; i++) if(x % i == 0) return 0; return 1; } int main() { int n, A[50], isp[50]; scanf("%d", &n); for(int i = 2; i <= n*2; i++) //生成素数表，加快后继判断 isp[i] = is_prime(i); for(int i = 0; i < n; i++) A[i] = i+1; //第一个排列 do { int ok = 1; for(int i = 0; i < n; i++) if(!isp[A[i]+A[(i+1)%n]]) { //判断合法性 ok = 0; break; } if(ok) { for(int i = 0; i < n; i++) printf("%d ", A[i]); //输出序列 printf("\n"); } }while(next_permutation(A+1, A+n)); return 0; } 运行后，发现当n=12时就已经很慢了，而当n=16根本出不来。下面采取回溯法来解决此问题，完整的回溯法的程序如下： #include #include using namespace std; int is_prime(int x) { //判数一个整数x是否是一个素数 for(int i = 2; i*i <= x; i++) if(x % i == 0) return 0; return 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 < n; i++) printf("%d ", A[i]); printf("\n"); } else for(int i = 2; i <= n; i++) //尝试放置每个数i if(!vis[i] && isp[i+A[cur-1]]) { //如果i没有用过，并且与前一个数之和为素数 A[cur] = i; vis[i] = 1; //设置标志 dfs(cur+1); vis[i] = 0; //清除标志 } } int main() { scanf("%d", &n); for(int i = 2; i <= n*2; i++) isp[i] = is_prime(i); memset(vis, 0, sizeof(vis)); A[0] = 1; dfs(1); return 0; } 测试后，回溯法比生成-测试法要快很多。回溯法是按照深度优先的顺序在遍历解答树。 7.4.3 困难串 如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其它的串称为“困难的串”。 输入正整数n和L，输出由前L个字符组成的、字典序第k小的困难的串。例如，当L=3时，前7个困难的串分别为：A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。输入保证字符答案不超过80个字符。 样例输入： 7 3 30 3 样例输出： ABACABA ABACABCACBABCABACABCACBACABA 【分析】 从左到右依次考虑每个位置上的字符。因此，主要问题是如何判断当前字符串是否已存在连续的重复子串。所在只需判断当前串的后缀，而非所有子串。 完整的程序如下： #include int n, L, cnt = 0; int S[100]; int dfs(int cur) { // 返回0表示已经得到解，无须继续搜索 if(cnt++ == n) { for(int i = 0; i < cur; i++) printf("%c", 'A'+S[i]); // 输出方案 printf("\n"); return 0; } for(int i = 0; i < L; 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 < j; k++) // 检查后一半是否等于前一半 if(S[cur-k] != S[cur-k-j]) { equal = 0; break; } if(equal) { ok = 0; break; } // 后一半等于前一半，方案不合法 } if(ok) if(!dfs(cur+1)) return 0; // 递归搜索。如果已经找到解，则直接退出 } return 1; } int main() { scanf("%d%d", &n, &L); dfs(0); return 0; } 7.4.4 带宽 给出一个n个结点的图G和一个结点的排列，定义结点i的带宽b(i)为i和相邻结点在排列中的最远距离，而所有b(i)的最大值就是整个图的带宽。给定图G，求出让带宽最小的结点排列。 【分析】 可以记录下目前已经找到的最小带宽k。如果发现已经有某两个结点的距离大于或等于k，再怎么扩展也不可能比当前解更优，应当强制把它“剪掉”，即为解答树“剪枝（prune）”。 除此之外，还可以剪掉更多的枝叶。如果在搜索到结点u时，u结点还有m个相邻接点没有确定位置，那么对于结点u来说，最理想的情况就是这m个结点紧跟在u后面，这样的结点带宽为m，而其他任何“非理想情况”的带宽至少为m+1。这样，如果m≥k，即“最理想的情况下都不能得到比当前最优解更好的方案”，则显然应当剪枝。 7.5 隐式图搜索 对很多问题可以用图的遍历算法解决，但这些问题的图却不是事先给定、从程序读入的，而是由程序动态生成的。 7.5.1 隐式树的遍历 到目前为止，本章中的解答树都有是树，有着严格的“层次”概念——从根往下走，你永远都无法回到根结点。 回溯法是按照深度优先顺序遍历的，它的优点是空间很节省：只有递归栈中结点需要保存。换句话说，回溯法的空间开销和访问的最深结点的深度成正比。 树不仅可以深度优先遍历，还可以宽度优先遍历。好处是找到的第一个解一定是离根最近的解，但空间开销却大增加（队列中结点很多）。 例7-1 最优程序。 有一台只有一个数据栈的计算机，支持整数的5种运算：ADD、SUB、MUL、DIV、DUP。假设栈顶的3个元素分别为a、b、c，则5种运算的效果依次如下： ADD：a和b依次出栈，计算a+b，把结果压栈。 SUB：a和b依次出栈，计算b-a，把结果压栈。 MUL：a和b依次出栈，计算a×b，把结果压栈。 DIV：a和b依次出栈，计算b/a并向下取整，把结果压栈。 DUP：a出栈，再连续把两个a压栈。 遇到以下情况之一，机器会产生错误：执行DIV操作时，栈顶元素为0；执行ADD、SUB、MUL、DIV操作时，栈中只有一个元素；运算结果的绝对值大于30000。 给出n个整数对(a i,b i)（a i互不相同），你的任务是设计一个最短的程序，使得对于1和n之间的所有i，如果程序执行前栈中只有一个元素a i，则执行后栈顶元素是b i。n≤5。 【分析】 本题没有办法用回溯法来解决。本题的解答树是无穷大的——多长的程序都是合法的。题目要求最短的程序，最简单可行的方法是利用宽度优先遍历解答树。 例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 【分析】 本题的解决方案是采用迭代加深搜索（iterative deepening）：从小到大枚举深度上限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升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢？ 方法如图7-7所示。 图7-7 倒水问题：一种方法是(6,0,0)→(3,3,0)→(3,2,1)→(4,2,0) 注意：由于没有刻度，用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯子x倒空，而不能中途停止。 你的任务是解决一般性的问题：设大、中、小3个杯子的容量分别为a,b,c，最初只有大杯子装满水，其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢？你需要打印出每步操作后各个杯子中的水量（0 【分析】 假设在某一时刻，大杯子中有v0升水，中杯子有v1升水，小杯子有v2升水，称当时的系统状态为(v0,v1,v2)。把“状态”想象成图中的结点，可以得到如图7-8所示的状态图（stata graph）。 图7-8 倒水问题状态图 注意图7-8所示的状态图和迷宫是不同的。在迷宫中，只在可以成功往上走，走完后往下一定会回到刚才的地方，但此图并不相同：从状态（4,2,0）可以通过把水从中杯子倒入大杯子而一步到达（6,0,0），但是从（6,0,0）却无法一步到达（4,2,0）。换句话说，迷宫图是无向图（undirected graph），而本题“倒水状态图”是有向图（directed graph）由于无论如何倒，杯子中的水量都是整数（按照倒水次数归纳即可），因此水杯的小量最多只有0,1,2,…,c共c+1种可能；同理，中杯子的水量一共只有b+1种可能，大杯子一共只有a+1种可能，因此理论上状态最多有(a+1)(b+1)(c+1)种可能性。但是由于水量x永远不变，如果有两个状态的小杯子和中杯小量都相同，则大杯子小量相同。换句话说，最多可能的状态数不会超过(b+1)(c+1)，因此结点数不超过106。 完整的程序如下： #include #include #define MAXN 105 int cap[3], x; int vis[MAXN][MAXN]; struct Node { int v[3]; int fa, dist, last_op; }; Node q[MAXN*MAXN]; void print_path(int idx) { if(q[idx].fa != 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(front Node& u = q[front]; if(u.v[0] == x || u.v[1] == x || u.v[2] == x) { printf("%d\n", u.dist); print_path(front); return; } for(i = 0; i < 3; i++) for(j = 0; j < 3; j++) if(i!=j) { Node& v = q[rear]; int amount = u.v[i]+u.v[j] for(k = 0; k < 3; k++) v.v[k] = u.v[k]; v.v[i] -= amount; v.v[j] += amount; if(!vis[v.v[1]][v.v[2]]) { vis[v.v[1]][v.v[2]] = 1; v.fa = front; v.dist = q[front].dist+1; https://www.doczj.com/doc/4b8888964.html,st_op = i*10+j; rear++; } } front++; } } int main() { int i, j; scanf("%d%d%d%d", &cap[0], &cap[1], &cap[2], &x); memset(vis, 0, sizeof(vis)); bfs(); return 0; } 7.5.3 八数码问题 编号为1～8的8个正方形滑块摆成3行3列（有一个格式留空），如图7-9所示。每次可以把与空格相邻的滑块（有公共边才算相邻）移动到空格中，而它原来的位置就成为了新的空格。给定初始局面和目标局面（用0表示空格），你任务是计算出最少的移动步数。如 样例输入： 2 6 4 1 3 7 0 5 8 8 1 5 7 3 6 4 0 2 样例输出： 31 【分析】 把八数码问题归结为图上的最短路问题，其中每个状态就是9个格式中的滑块编号（从上到下、从左到右地把它们放在一个包含9个元素的数组中）。具体程序如下：typedef int State[9]; //定义“状态”类型 const int MAXSTATE = 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 < 9; z++) if(!s[z]) break; //找“0”的位置 int x = z/3, y = z%3; //获取行列位置（0～2） for(int d = 0; d < 4; 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 < 9; i++) //起始状态 scanf("%d", &st[1][i]); for(int i = 0; i < 9; 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 < 9; i++) fact[i] = fact[i-1] * i; } int try_to_insert(int s) { int code = 0; //把st[s]映射到整数code for(int i = 0; i < 9; i++) { int cnt = 0; for(int j = i+1; j < 9; j++) if(st[s][j] < st[s][i]) cnt++; code += fact[8-i] * cnt; } if(vis[code]) return 0; return vis[code] = 1; } 说明：上面尽管原理巧妙，时间效率也非常高，但编码解码法的适用范围不大：如果隐式图的总结数非常大，编码也将会很大，数组还是存不下。 （2）方法二 #《算法竞赛入门经典》勘误 关于勘误?下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出，谢谢！ 一些一般性的问题?运算符?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++ 4.6.2下编译通过） 重大错误?p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 (感谢imxivid） p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) (感谢imxivid） p45. 第七行和第九行i-j+1应为i+j+1。修改后： 1. { 2. for (j = 0; i - j >= 0 && i + j < m; j++) 3. { 4. if (s[i - j] != s[i + j]) break; 5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7. for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。应是“输入非负整数m和n”。 p54. 举例中的m和n也写反了（真是个悲剧），且C(20,1)=20。 p71. 《周期串》代码的第8行，j++应为i++。 p72. 代码的第7行，“return”改为“break”以和其他地方一致。 p81. k为奇数和偶数的时候，分子和分母的顺序是不一样的。正确代码为： #include 第一章习题1-1 #include 习题1-3 #include 习题1-5 #include 大师兄教你如何过华为机试 宝典1—内功心法 大华为这个大数据时代土豪金海量式的招聘又要开始了！！！ 近期听说大华为的校招机试马上就要开始了，由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容，所以机试的地位非常重要。对于机试，除了长期积累的软件基本功以外，还有很多可以短期训练的东西，类似于考试之前的突击，可以迅速提高机试成绩，就像在我西电大杨老师考前最后一堂课一定要去，那个重点就是考点阿。 这篇机试葵花宝典的内容是针对华为软件类上机准备的，如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学，请移步 https://www.doczj.com/doc/4b8888964.html,/land/或者https://www.doczj.com/doc/4b8888964.html,，刷上200道题，机试不想拿满分都难。 对于机试，首先应该调整好自己的心态，不要觉得写程序很难，机试题很难，也不要去考虑，万一机试考到自己不会的内容怎么办，要相信，机试题永远是考察每个人的基础，基础是不会考的很偏的，会有人恰好做过某个题而做出来那个题，但不会有人恰好没做过一个题而做不出来那个题。 机试之前，应该做的准备有： 1、买一本《算法竞赛入门经典》，这本书不同于普通的算法或者编程语言的书籍，这 本书既讲语言，又讲算法，由浅入深，讲的很好，能看完前几章并且把例题都做 会，想通过机试就很简单了 2、调整好心态，时刻告诉自己，哪些小错误是自己以前经常犯的，最好用笔记本记录 下来，写每道题前再看一遍，如果遇到代码调不出来了，先想想自己是否犯过以 前那些错误。还有就是，看了题目以后，先仔细想清楚细节，在纸上写清楚自己 需要用到的变量，以及代码的基本框架，不要急于动手去写代码 3、不要惧怕任何一道看起来很难的题目，有不会的就去问身边会的人，让别人给自己 讲清楚 4、心中默念10遍C++跟C除了多了两个加号其实没有区别，会C就能上手C++ 5、大量的练习是必要且有效的 6、看完这篇宝典，预过机试、必练此功。 在这里推荐一个帖子，是机试归来的学长写的，写的很不错，里面的例题在后面的攻略 信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 424-Integer Inquiry One of the first users of BIT's new supercomputer was Chip Diller.He extended his exploration of powers of3to go from0 to333and he explored taking various sums of those numbers. ``This supercomputer is great,''remarked Chip.``I only wish Timothy were here to see these results.''(Chip moved to a new apartment,once one became available on the third floor of the Lemon Sky apartments on Third Street.) Input The input will consist of at most100lines of text,each of which contains a single VeryLongInteger.Each VeryLongInteger will be100or fewer characters in length,and will only contain digits(no VeryLongInteger will be negative). The final input line will contain a single zero on a line by itself. Output Your program should output the sum of the VeryLongIntegers given in the input. Sample Input 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 Sample Output 370370367037037036703703703670 10106–Product The Problem The problem is to multiply two integers X,Y.(0<=X,Y<10250) The Input The input will consist of a set of pairs of lines.Each line in pair contains one multiplyer. The Output For each input pair of lines the output line should consist one integer the product. Sample Input 12 12 2 222222222222222222222222 Sample Output 144 444444444444444444444444 465–Overflow Write a program that reads an expression consisting of two non-negative integer and an operator.Determine if either integer or the result of the expression is too large to be represented as a``normal''signed integer(type integer if you are working Pascal,type int if you are working in C). Input An unspecified number of lines.Each line will contain an integer,one of the two operators+or*,and another integer. Output For each line of input,print the input followed by0-3lines containing as many of these three messages as are appropriate: ``first number too big'',``second number too big'',``result too big''. Sample Input 300+3 9999999999999999999999+11 Sample Output 300+3 9999999999999999999999+11 first number too big 算法工程师成长计划 大学期间必须要学好的课程：C/C++两种语言（或JA V A）、高等数学、线性代数、数据结构、离散数学、数据库原理、操作系统原理、计算机组成原理、人工智能、编译原理、算法设计与分析。 大一上学期： 1.C语言基础语法必须全部学会，提前完成C语言课程设计。 2.简单数学题：求最大公约数、筛法求素数、康托展开、同余定理、次方求模等。 3.计算机课初步：三角形面积，三点顺序等等。 4.学会计算简单程序的时间复杂度和空间复杂度。 5.二分查找、贪心算法经典算法。 6.简单的排序算法：冒泡排序法、插入排序法。 7.高等数学。 8.操作系统应用：DOS命令，学会Windows系统的一些小知识，学会编辑注册表， 学会使用组策略管理器（gpedit.msc）管理组策略等。 大一下学期： 1.掌握C++部分语法，如引用类型、函数重载等，基本明白什么是类。 2.学会使用栈和队列等线性结构。 3.掌握BFS和DFS以及树的前序、中序、后序遍历。 4.学会分治策略。 5.掌握排序算法：选择排序、归并排序、快速排序、计数、基数排序等等。 6.动态规划：最大子串和、最长公共子序列、最长单调递增子序列、01背包、完全背 包等。 7.数论：扩展欧几里德算法、求逆元、同余方程、中国剩余定理。 8.博弈论：博弈问题与SG函数的定义、多个博弈问题SG值的合并。 9.图论：图的存储、欧拉回路的判定、单源最短路Bellman-Ford算法及Dijkstra算法、 最小生成树Kruskal算法及Prim算法。 10.学会使用C语言进行网络编程与多线程编程。 11.高等数学、线性代数：做几道“矩阵运算”分类下的题目。 12.学习matlab，如果想参加数学建模大赛，需要学这个软件。 大一假期： 1.掌握C++语法，并熟练使用STL（重要）。 2.试着实现STL的一些基本容器和函数、使自己基本能看懂STL源码。 3.数据结构：字典树、并查集、树状数组、简单线段树。 4.图论：使用优先队列优化Dijkstra算法及Prim算法，单源最短路径之SPFA，差分 约束系统，多源多点最短路径之FloydWarshall算法，求欧拉回路（圈套圈算法）。 5.拓扑排序：复杂BFS和DFS搜索、复杂模拟题训练。 6.动态规划：多重背包、分组背包、依赖背包等各种背包问题（参见背包九讲）。 7.计算几何：判断点是否在线段上、线段相交、圆与矩形的关系、点是否在多边形内、 点到线段的最近点、多边形面积、求多边形重心、求凸包、点在任意多边形内外的 判定。 8.学习使用C/C++连接数据库、学习一种C++的开发框架来编写一些窗体程序（如 MFC、Qt）。 第7章暴力求解法 【教学内容相关章节】 7.1简单枚举 7.2枚举排列 7.3子集生成 7.4回溯法 7.5隐式图搜索 【教学目标】 （1）掌握整数、子串等简单对象的枚举方法； （2）熟练掌握排列生成的递归方法； （3）熟练掌握用“下一个排列”枚举全排列的方法； （4）理解解答树，并能估算典型解答树的结点数； （5）熟练掌握子集生成的增量法、位向量法和二进制法； （6）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （7）熟练掌握解答树的宽度优先搜索和迭代加深搜索； （8）理解倒水问题的状态图与八皇后问题的解答树的本质区别； （9）熟练掌握八数码问题的BFS实现； （10）熟练掌握集合的两种典型实现——hash表和STL集合。 【教学要求】 掌握整数、子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用“下一个排列”枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握解答树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现——hash表和STL集合。【教学内容提要】 本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的递归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的基本框架；介绍了集合的两种典型实现——hash表和STL集合。 【教学重点、难点】 教学重点： （1）熟练掌握排列生成的递归方法； （2）理解解答树，并能估算典型解答树的结点数； （3）熟练掌握子集生成的增量法、位向量法和二进制法； （4）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （5）熟练掌握解答树的宽度优先搜索和迭代搜索； （6）熟练掌握集合的两种典型实现——hash表和STL集合。 教学难点： （1）熟练掌握子集生成的增量法、位向量法和二进制法； （2）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （3）熟练掌握解答树的宽度优先搜索和迭代搜索； （4）熟练掌握集合的两种典型实现——hash表和STL集合。 【课时安排】 7.1简单枚举 7.2枚举排列 7.3子集生成 7.4回溯法 7.5隐式图搜索 第6章数据结构基础 【教学内容相关章节】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 【教学目标】 （1）熟练掌握栈和队列及其实现； （2）了解双向链表及其实现； （3）掌握对比测试的方法； （4）掌握随机数据生成方法； （5）掌握完全二叉树的数组实现； （6）了解动态内存分配和释放方法及其注意事项； （7）掌握二叉树的链式表示法； （8）掌握二叉树的先序、后序和中序遍历和层次遍历； （9）掌握图的DFS及连通块计数； （10）掌握图的BFS及最短路的输出； （11）掌握拓扑排序算法； （12）掌握欧拉回路算法。 【教学要求】 掌握栈和队列及其实现；掌握对比测试的方法；掌握随机数据生成方法；掌握完全二叉树的数组实现和链式表示法；掌握二叉树的先序、后序和中序遍历和层次遍历；掌握图的DFS和BFS遍历；掌握拓扑排序算法；掌握欧拉回路算法。 【教学内容提要】 本章介绍基础数据结构，包括线性表、二叉树和图。有两种特殊的线性表：栈和队列。对于树型结构主要讨论二叉树，还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好，很难设计正确、高效的算法。 【教学重点、难点】 教学重点： （1）掌握栈和队列及其实现； （2）掌握对比测试的方法； （3）掌握随机数据生成方法； （4）掌握完全二叉树的数组实现和链式表示法； （5）掌握二叉树的先序、后序和中序遍历和层次遍历； （6）掌握图的DFS和BFS遍历； （7）掌握拓扑排序算法和欧拉回路算法。 教学难点： （1）掌握完全二叉树的数组实现和链式表示法； （2）掌握二叉树的先序、后序和中序遍历和层次遍历； （3）掌握图的DFS和BFS遍历； （4）掌握拓扑排序算法和欧拉回路算法。 【课时安排（共9学时）】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 求int的上限与下限#include return 0; } 1-3 #include 求int的上限与下限 #include return 0; } 1-3 #include 第一章程序设计入门 1.1算术表达式 ?大小写字母代表的含义不同 ?整数值用%d输出，实数用%lf,小数点位数可以用%.nf中的n来控制 ?整数/整数=整数浮点数/浮点数=浮点数 1.2变量及其输入 ?可以通过scanf来输入数据，但是要注意每个变量前需要&符号。 ?比赛时不需编写提示信息。 ?不要让程序“按任意键退出”，即在程序的最后写入 return0; 尽量用const关键字声明变量 1.3顺序结构程序设计 ?注意数据的分离。准确的使用/和% ?十进制：非0数字打头 ?竞赛目标：解决问题 1.4分支结构程序设计 ?情况考虑周全，不仅仅是样例数据 1.5小结与习题 1.5.1数据类型实验 ?A1A2注意数据范围，数值太大，用double表示时，最好将数据换成浮点型?A3负数不能开方，计算过程中系统不会报错，最后结果是错误结果 ?A4编译报错 ?A5编译报错 1.5.2scanf输入格式实验 ?B1B2可以得到预期结果 ?B3前后插入大量空格或者水平制表符或者空格都可以 ?B4只能正常输出12，字符无法输出 1.5.3printf语句输出实验 ?C1两个空行：\n\n ?C2%%d ?C3\\n ?转义字符 1.5.4测测你的实践能力 问题1： 问题2、3： 问题4：！14级&&5级||4级问题5：if(a) {if(b)x++; else y++; } 1.5.6上机练习 习题1-1平均数 注意将整数换成实数 习题1-2温度 可直接将f定义成float类型 习题1-3连续和 注意求和公式（a1+an）*n/2 习题1-4正弦和余弦 注意将数值转换成角度，n*pa/180 习题1-5距离 距离公式sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))习题1-6偶数 x%2==0 x==(x/2)+(x/2) (x+1)%2==1 算法竞赛入门竞赛 第1章程序设计入门 学习目标 ?熟悉C语言程序的编译和运行 ?学会编程计算并输出常见的算术表达式的结果 ?掌握整数和浮点数的含义和输出方法 ?掌握数学函数的使用方法 ?初步了解变量的含义 ?掌握整数和浮点数变量的声明方法 ?掌握整数和浮点数变量的读入方法 ?掌握变量交换的三变量法 ?理解算法竞赛中的程序三步曲：输入、计算、输出 ?记住算法竞赛的目标及其对程序的要求 计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。 接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。 注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。 1.1 算术表达式 计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。 程序1-1 计算并输出1+2的值 #include 算法竞赛入门经典 ·2· { printf("%d\n", 1+2); return 0; } 这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。 即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。 下面让我们做4个实验： 实验1：修改程序1-1，输出3-4的结果 实验2：修改程序1-1，输出5×6的结果 实验3：修改程序1-1，输出8÷4的结果 实验4：修改程序1-1，输出8÷5的结果 直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。 等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。 在C 语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1，不信可以自己试试。那么如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。 程序1-2 计算并输出8/5的值，保留小数点后1位 #include ?基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 ?提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 算法竞赛-入门经典-作者刘汝佳.doc 第1部分语言篇 第1章程序设计入门 学习目标 ?熟悉C语言程序的编译和运行 ?学会编程计算并输出常见的算术表达式的结果 ?掌握整数和浮点数的含义和输出方法 ?掌握数学函数的使用方法 ?初步了解变量的含义 ?掌握整数和浮点数变量的声明方法 ?掌握整数和浮点数变量的读入方法 ?掌握变量交换的三变量法 ?理解算法竞赛中的程序三步曲：输入、计算、输出 ?记住算法竞赛的目标及其对程序的要求 计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。 接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。 注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。 （为帮助没有分值的朋友能下载，特此修改文档，以免上传不了） 1.1 算术表达式 计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。 程序1-1 计算并输出1+2的值 #include 算法竞赛入门经典 这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。 即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。 下面让我们做4个实验： 实验1：修改程序1-1，输出3-4的结果 实验2：修改程序1-1，输出5×6的结果 实验3：修改程序1-1，输出8÷4的结果 实验4：修改程序1-1，输出8÷5的结果 直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。 等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。 在C语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1，不信可以自己试试。那么如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。 程序1-2 计算并输出8/5的值，保留小数点后1位 #include 第2章循环结构程序设计 【教学内容相关章节】 2.1 for循环 2.2 循环结构程序设计 2.3文件操作 2.4 小结与习题 【教学目标】 （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； （3）学会使用计算器和累加器； （4）学会用输出中间结果的方法调试； （5）学会用计时函数测试程序效率； （6）学会用重定向的方式读写文件； （7）学会fopen的方式读写文件； （8）了解算法竞赛对文件读写方式和命名的严格性； （9）记住变量在赋值之前的值是不确定的； （10）学会使用条件编译指示构建本地运行环境。 【教学要求】 掌握for循环的使用方法；掌握while循环的使用方法；掌握几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。 【教学内容提要】 在有些程序中，需要反复执行某些语句。将n条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。相关的语句有：for、while、do while、break、continue等。 既可以从文件中读取数据, 也可以向文件中写入数据。读写文件之前，首先要打开文件。读写文件结束后，要关闭文件。C/C++提供了一系列库函数，声明于stdio.h中，用于进行文件操作。这里介绍其中几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。 【教学重点、难点】 教学重点： （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； （3）掌握文件有关操作； （4）条件编译。 教学难点： （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； 【课时安排（共2学时）】 2.1 for循环 2.2 循环结构程序设计 2.3 文件操作 2.4 小结与习题 number theory 575 - Skew Binary When a number is expressed in decimal, the k-th digit represents a multiple of 10k. (Digits are numbered from right to left, where the least significant digit is number 0.) For example, When a number is expressed in binary, the k-th digit represents a multiple of 2k. For example, In skew binary, the k-th digit represents a multiple of 2k+1 - 1. The only possible digits are 0 and 1, except that the least-significant nonzero digit can be a 2. For example, The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew binary is useful in some applications because it is possible to add 1 with at most one carry. However, this has nothing to do with the current problem.) Input The input file contains one or more lines, each of which contains an integer n. If n = 0 it signals the end of the input, and otherwise n is a nonnegative integer in skew binary. Output For each number, output the decimal equivalent. The decimal value of n will be at most 231 - 1 = 2147483647. Sample Input 10120 200000000000000000000000000000 10 1000000000000000000000000000000 11 100 11111000001110000101101102000 Sample Output 44 2147483646 3 2147483647 4 7 1041110737 10110 - Light, more light There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there is `n' bulbs, he walks along the corridor back and forth `n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again. Now you have to determine what is the final condition of the last bulb. Is it on or off? The Input The input will be an integer indicating the n'th bulb in a corridor. Which is less then or equals 2^32-1. A zero indicates the end of input. You should not process this input. The Output Output "yes" if the light is on otherwise "no" , in a single line. Sample Input 3 6241 8191蓝书刘汝佳算法竞赛入门经典勘误
最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案
大师兄教你如何过华为机试
(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
BIG NUMBER 算法竞赛入门经典 刘汝佳
算法工程师本科生学习计划
算法竞赛入门经典授课教案第7章 暴力求解法
算法竞赛入门经典授课教案第6章数据结构基础(精心排版,并扩充部分内容)
算法竞赛入门经典第二版习题答案
算法竞赛入门经典第二版习题问题详解
算法竞赛入门经典第一章要点
《算法竞赛入门经典》
信息竞赛推荐书籍
算法竞赛-入门经典-作者刘汝佳
算法竞赛入门经典授课教案第2章_循环结构程序设计(精心排版,并扩充部分内容)
number theory 算法竞赛入门经典 刘汝佳
相关主题
文本预览