这次练习主要是复习回溯法，之前一练主要还是学习了子集树与排序树的基本操作。
主要内容
回顾知识：数字全排列（子集树、排序树）
回溯法之加强版：素数环
练习题：数字排序问题（蓝桥杯） + 39级台阶 + 数字排列(相邻之和为素数)
“温故而知新，可以为师矣“
全排列问题
【问题描述】
给定数字n，请输出1～n的全部排列顺序。
例如，n=3,输出:{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}
【题解】
利用两种回溯法的代表解决该问题。
子集树做法：借助 vis[ ] 来标记其在集合中的元素。
构建搜索树，其每一层相当于排列中的每一个位置。
用参数step控制当前位置
该位置填入什么数字，还需看vis[ ]是否被标记过
若该数字已被集合选中，不做处理，则找另外的数字
若该数字未被选中，则把该位置赋值上该数字。同时进行下一层搜索。
当到达叶子结点时，则进行回溯。
回溯时别忘记把当前位置的数字撤标记。
对于当前位置来说又可以填入另外的数字。
其核心代码：
for( int i = 1 ; i <= n ; i ++ ){ if( vis[i] == 0 ){ vis[i] = 1 ; A[step] = i ; dfs_subset( step + 1 ); vis[i] = 0 ; } }
排列树做法：
由于排列必须时n个数，别忘记要初始化数字，直接给赋上值。（1～n）
然后进行排列树的常规操作。
构建搜索树，其每一层相当于排列中的每一个位置。
用参数<S,E>控制，S表示当前位置，E表示结束位置。
我们所需要的是对下标为S，即当前位置的位置分别与后面的数字交换操作。
其目的就是为达到该位置 把全部数字在该位置轮流打头。
到达叶子结点的条件是，当前位置S已经是结束位置E
核心代码：
for( int i = S ; i <= E ; i++ ){ swap( B[S] , B[i] ); dfs_Permutation( S+1 , E ); swap( B[S] , B[i] ); }
具体代码：
1 //DFS 利用子集树 和 排列树 实现数字全排列 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int N = 20 ; 6 int vis[N],n; 7 8 int A[N] , B[N]; 9 void dfs_subset(int step){ 10 if( step == n ){ 11 for( int i = 0 ; i < n ; i++ ){ 12 printf("%3d",A[i]); 13 } 14 putchar(' '); 15 } 16 for( int i = 1 ; i <= n ; i ++ ){ 17 if( vis[i] == 0 ){ 18 vis[i] = 1 ; A[step] = i ; 19 dfs_subset( step + 1 ); 20 vis[i] = 0 ; 21 } 22 } 23 } 24 25 void dfs_Permutation( int S , int E ){ 26 if( S == E ){ 27 for( int i = 1 ; i <= n ; i++ ){ 28 printf("%3d",B[i]); 29 } 30 putchar(' '); 31 return ; 32 } 33 for( int i = S ; i <= E ; i++ ){ 34 swap( B[S] , B[i] ); 35 dfs_Permutation( S+1 , E ); 36 swap( B[S] , B[i] ); 37 } 38 } 39 int main() 40 { 41 puts("Please input N :"); 42 scanf("%d",&n); 43 44 puts(" dfs_subset tree"); 45 dfs_subset(0); 46 47 puts(" dfs_Permutation tree"); 48 for( int i = 1 ; i <= n ; i++ ){ 49 B[i] = i ; 50 } 51 dfs_Permutation(1,n); 52 return 0; 53 }
素数环
【题目描述】
素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。现在要求输入一个n，求n个数围成一圈有多少种素数环，规定第一个数字是1。
【小结】
大家千万不要去新的服务器交题目。我都快自闭了。然后去了以前的服务器上交题过了。但是那个题目的数据有错，应该需要特判1，因为1本身不是素数。而那道题目的数据虽然涉及n=1的情况，但是答案却是1，答案应该是“-1”。
【题解】
全排列的一个变种问题，其实就是在过程中加一个判断即可。在放数字判断前一个数与当前位置需要放的数之和是否为质数。因为是一个环，所以最后还需要加一个判断，即最后一个数与1相加是否为质数。
总结：朴素全排列问题+过程中特判相邻数之和为质数+最后一个数与1相加为质数。
1 //dfs解决素数环 hdu-1016 2 // http://acm.hdu.edu.cn/showproblem.php?pid=1016 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int N = 1e3 +10 ; 7 8 int n ; 9 int a[N] ; 10 int vis[N] ; 11 bool is_prime[N] ; 12 13 void Init(){ 14 for( int i = 2 ; i < N ; i++ ) { 15 bool f = true; 16 for (int j = 2; j * j <= i; j++) { 17 if (i % j == 0) { 18 f = false; 19 break; 20 } 21 } 22 if (f) is_prime[i] = true; 23 24 } 25 a[1] = 1 ; vis[1] = -1 ; 26 } 27 28 void dfs_subset( int step ){ 29 if( step == n + 1 ){ 30 if( is_prime[ a[n] + 1 ] ){ 31 for( int i = 1 ; i <= n ; i ++ ){ 32 printf("%d%c",a[i],i==n?' ':' '); 33 //printf("%d ",a[i]); 34 } 35 //putchar(' '); 36 } 37 return ; 38 } 39 40 for( int i = 2 ; i <= n ; i++ ) { 41 if (vis[i] == 0 && is_prime[i + a[step - 1]]) { 42 vis[i] = 1; a[step] = i; 43 dfs_subset(step + 1); 44 vis[i] = 0; 45 } 46 } 47 } 48 int main() 49 { 50 Init() ; 51 int Case = 0 ; 52 while( ~scanf("%d",&n) ){ 53 printf("Case %d: ",++Case); 54 if( n > 20 ){ 55 printf("-1 "); 56 }else if( n % 2 == 1 ){ 57 printf("-1 "); 58 }else{ 59 dfs_subset( 2 ); 60 } 61 puts(""); 62 } 63 return 0 ; 64 }
练习题
数字排列问题
【题目描述】
今有7对数字：两个1，两个2，两个3，...两个7，把它们排成一行。 要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列： 17126425374635 当然，如果把它倒过来，也是符合要求的。 请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。 注意：只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。 744*7***
【题解】
直接全排列公式用上，同时要多增加一个标记数组，每个位置放一个数的同时相隔i+1的位置同时放。
然后就OK了。
1 //74****4*7******* 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int N = 20 ; 6 int vis[N] , a[N]; 7 void dfs( int step ){ 8 if( step == 14 ){ 9 for( int i = 1 ; i <= 14 ; i++ ){ 10 printf("%d%c",a[i],i==14?' ':' '); 11 } 12 return ; 13 } 14 15 if( a[step] != -1 ) dfs( step + 1 ); 16 17 for( int i = 1 ; i <= 6 ; i ++ ){ 18 if( a[step] == -1 && vis[i] == 0 && step + i + 1 <= 14 && a[ step + i + 1] == -1 ){ 19 vis[i] = 1 ; 20 a[step + i + 1] = a[step] = i ; 21 22 dfs( step + 1 ); 23 24 a[step + i + 1] = a[step] = -1 ; 25 vis[i] = 0 ; 26 } 27 } 28 } 29 int main(){ 30 for( int i = 1 ; i <= 14 ; i ++ ) a[i] = -1 ; 31 vis[4] = vis[7] = -1 ; 32 a[1] = 7 , a[9] = 7 ; 33 a[2] = 4 , a[7] = 4 ; 34 dfs( 3 ) ; 35 return 0 ; 36 }
39级台阶
【题目描述】
小明看完电影《第39级台阶》，离开电影院的时候，他数了数视觉的台阶数，恰好是39级。 站在台阶前，他突然又想起一个问题：如果我每一步只能迈上1个或2个台阶，先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要迈偶数步。那么，上完39级台阶，有多少种不同的上法呢？ 请利用计算机的优势，帮助小明寻找答案。
利用递归来实现，从第0层往上走，上1级或2级。
题目都给出来了，先迈左脚，最后迈出右脚，可以说明步数为偶数。
1 #include<cstdio> 2 using namespace std; 3 int n = 39 ; 4 int ans = 0 ; 5 void dfs( int step , int k ){ 6 //定义结束条件 7 if( step == 39 && k % 2 == 0 ){ 8 ans ++ ; 9 return ; 10 } 11 //结束条件需要多加一条 12 if( step >= 40 ) return ; 13 14 //迈出一步,台阶增加1或2 15 dfs( step + 1 , k + 1 ); 16 dfs( step + 2 , k + 1 ); 17 } 18 //51167078 19 int main() 20 { 21 dfs( 0 , 0 ); 22 printf("%d ",ans); 23 return 0; 24 }
数字排列问题
【题目描述】
将1到20排一列，要求每相邻两位数的和是质数，试求排列的种数。
【题解】
用排列树解决，弱化版的素数环问题。
预处理所有素数出来，用bool数组标识出来。
然后放每一个数的时候加上两数之和为素数即可。
只不过剪枝效果不太好，等个2～3分钟才出答案。。
1 //dfs解决数字排列问题 2 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N = 1e3 +10 ; 8 9 int n ; 10 int a[N] ; 11 bool is_prime[N] ; 12 13 void Init(){ 14 for( int i = 2 ; i < N ; i++ ) { 15 bool f = true; 16 for (int j = 2; j * j <= i; j++) { 17 if (i % j == 0) { 18 f = false; 19 break; 20 } 21 } 22 if (f) is_prime[i] = true; 23 } 24 } 25 26 int ans = 0 ; 27 void dfs_Permutation( int S , int E ){ 28 if( S == E && is_prime[ a[E] + a[E-1] ]){ 29 ans ++ ; 30 return ; 31 } 32 for( int i = S ; i <= E ; i++ ) { 33 if( S == 1 || ( is_prime[ a[i] + a[S-1] ] ) ){ 34 swap( a[S] , a[i] ); 35 dfs_Permutation( S + 1 , E ); 36 swap( a[S] , a[i] ); 37 } 38 } 39 } 40 int main() 41 { 42 Init() ; 43 n = 20 ; 44 for( int i = 1 ; i <= n ; i ++ ){ 45 a[i] = i ; 46 } 47 dfs_Permutation( 1 , n ); 48 printf("%d ",ans); 49 return 0 ; 50 }