信息学奥赛-一本通-第二部门 根本算法 --＞ 第五章 搜刮与回溯算法

1317：【例5.2】组合的输出
【标题形貌】
分列与组合是常用的数学方法，此中组合就是从n个元素中抽出r个元素(不分次序且r≤n)，我们可以简朴地将n个元素明白为天然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出全部组合。
比方n＝5，r＝3，全部组合为：
1 2 3   1 2 4   1 2 5   1 3 4   1 3 5   1 4 5   2 3 4   2 3 5   2 4 5   3 4 5
【标题分析】
1.搜刮函数参数:上一次搜刮的数字i(i(n)>=i(n-1)),要搜刮的数位cnt
2.竣事的条件:满意个数的要求cnt==k+1
3.摆列与回溯方式:  
  for (int i = b; i <= n; i++) {  
         if (vis == 0) {  
             vis = 1;
             dfs(i + 1, r - 1);
             vis = 0;
         }
     }

  
【代码实现】
#include <bits/stdc++.h>
  
using namespace std;
  
bool vis[21];
int n;
void dfs(int b, int r) {  //r 控制循环层数  b控制循环出发点
     if (r == 0) {  
         for (int i = 1; i <= n; i++)
             if (vis) cout << "  " << i ;
         cout << endl;
         return ;
     };
  
     for (int i = b; i <= n; i++) {  
         if (vis == 0) {  
             vis = 1;
             dfs(i + 1, r - 1);
             vis = 0;
         }
     }
}
int main() {  
     //input data
     int  r;
     cin >> n >> r;
     dfs(1, r);
     return 0;
}
1318：【例5.3】天然数的拆分
【标题形貌】
任何一个大于1的天然数n，总可以拆分成多少个小于n的天然数之和。
当n=7共14种拆分方法：
【标题分析】
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
.....
7=3+4
共14个
1.搜刮函数参数:上一次搜刮的数字i(i(n)>=i(n-1)),要搜刮的数位cnt
2.竣事的条件:和sum==n满意条件输出,sum>n不满意条件直接返回
3.摆列与回溯方式:  
  for (int i = m; i <= n; i++) {  
         a[index]=i;
         sum+=i;
         dfs(i,index+i);
         sum-=i
     }
  【代码实现】
#include <bits/stdc++.h>
  
using namespace std;
  
int n;
int a[100005];
int sum = 0;
void dfs(int m, int index) {  
     if (sum > n) return;
     if (sum == n) {  
         cout << n << "=";
         cout << a[1];
         for (int i = 2; i < index; i++) {  
             cout << "+" << a;
         }
         cout << endl;
         return;
     }
     for (int i = m; i < n; i++) {  
         a[index] = i;
         sum += i;
         dfs(i, index + 1);
         sum -= i;
     }
}
int main() {  
     //input data
     cin >> n;
     dfs(1, 1);
     return 0;
}
1212：LETTERS
【标题形貌】
给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，而且不能移向曾经颠末的字母。问最多可以颠末几个字母。
【标题分析】

  【代码实现】
#include <bits/stdc++.h>
  
using namespace std;
  
int n, m;
char a[25][25];
bool vis[30];
int maxc = 0;
int _next[4][2] = {  {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int i, int j, int cnt) {  
     maxc = max(cnt, maxc);
     for (int k = 0; k <= 3; k++) {  
         int x = i + _next[k][0];
         int y = j + _next[k][1];
         if (x < 0 || y < 0 || x >= n || y >= m) continue;
         if (vis[a[x][y] - 'A']) continue;
         vis[a[x][y] - 'A'] = 1;
         dfs(x, y, cnt + 1);
         vis[a[x][y] - 'A'] = 0;
     }
}
int main() {  
     //input data
     cin >> n >> m;
     getchar();
     for (int i = 0; i < n; i++) {  
         cin.getline(a, 25);
     }
     vis[a[0][0] - 'A'] = 1;
     maxc++;
     dfs(0, 0, 1);
     cout << maxc;
     return 0;
}
1213：八皇后题目
【标题形貌】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
【标题分析】

  
【代码实现】
#inc