1. 递归实现指数型枚举 AcWing92
从1 ~ n 这 n (n < 20) 个整数中随机选取任意多个，输出所有可能的选择方案。
相当于每个数字有0（不选）、1（选）两种状态，共2^n种情况。
vector<int> chosen;
void calc(int x) {
if (x == n + 1) {
for (int i = 0; i < chosen.size(); i++)
printf("%d", chosen[i]);
puts("");
return;
}
//不选，则进入子问题
calc(x + 1);
//选，压入数组，然后进入子问题
chosen.push_back(x);
calc(x + 1);
//准备回溯到上一问题执勤啊，还原现场（将这一层问题上压入的元素取出）
chosen.pop_back();
}
int main() {
calc(1);
}2. 递归实现组合型枚举 AcWing93
从1 ~ n 这 n 个整数中随机选取m(0 ≤ m ≤ n < 20)个，输出所有可能的选择方案。
在第一题的基础上，进行剪枝（大于和小于m的不要）。
vector<int> chosen;
void calc(int x) {
//添加的内容：剪去已选择的数已经大于m的、已选择的数加上x和剩下的数也不足m的
//1 2 3 4 5
if(chosen.size() > m || chosen.size() + (n - x + 1) < m){
return;
}
if (x == n + 1) {
for (int i = 0; i < chosen.size(); i++)
printf("%d", chosen[i]);
puts("");
return;
}
//不选，则进入子问题
calc(x + 1);
//选，压入数组，然后进入子问题
chosen.push_back(x);
calc(x + 1);
//准备回溯到上一问题执勤啊，还原现场（将这一层问题上压入的元素取出）
chosen.pop_back();
}
int main() {
calc(1);
}3. 递归实现排列型枚举 AcWing94
把1 ~ n 这 n (n < 10) 个整数排成一行后随机打乱顺序，输出所有可能的次序。
int order[20]; //存输出序列
bool chosen[20]; //查看该数字是否用过
//和上个问题不同，这里的x表示的不是数，而是数组中的位置；i表示的才是数
void calc(int x){
if(x == n + 1){
for(int i = 1; i <= n; i++){
printf("%d ", order[i]);
}
puts("");
return;
}
for(int i = 1; i <= n; i++){
if(chosen[i]) //子问题跳过父问题中已选过的数
continue;
order[x] = i; //这样通过一次for循环，遍历x位置为1~n所有数的情况
chosen[i] = 1;
calc(x + 1); //子问题，及其他数的放置
chosen[i] = 0; //还原现场
//order[x] = 0; 可以不要这句，因为数组可以直接覆盖
}
}
int main() {
calc(1);
}4. 费解的开关 AcWing95
在一个5*5的01矩阵中，点击任意一个位置，该位置以及它上下左右四个相邻的位置中的数字都会变化（0变1,1变0），问：判断是否可能在6步以内使给定的01矩阵变成全1矩阵，能则输出最小步数，不能则输出-1？
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5;
//改变数组：上下左右中
int dx[5] = {0, 0, -1, 1, 0};
int dy[5] = {-1, 1, 0, 0, 0};
char arr[N][N];
char backup[N][N];
//改变函数
void turn(int x, int y) {
for (int i = 0; i < 5; i++) { //五个位置
int fx = x + dx[i];
int fy = y + dy[i];
if (fx < 0 || fx > 4 || fy < 0 || fy > 4)
continue;
arr[fx][fy] = (arr[fx][fy] == '0') ? '1' : '0';
}
}
int main() {
int n;
cin >> n;
while (n--) {
//每行当成字符串录入
for (int i = 0; i < 5; i++) {
cin >> arr[i];
}
int res = 25; //设置所需步数为最大值
//更改第一行（枚举：32种）
for (int op = 0; op < 32; op++) {
//备份数组，每枚举一种还原一次
memcpy(backup, arr, sizeof arr);
//计数器（记录步骤）
int count = 0;
for (int i = 0; i < 5; i++) { //第一行的五个位置
if (op >> i & 0) { //五个位置中哪些位置为0，则变化那些位置（op为二进制，
//op遍历0~31十进制数相当于将第一行五个位置遍历00000~11111）
count++;
turn(0, i);
}
}
//根据第一行更改后四行
for (int i = 0; i < 4; i++) { //行
for (int j = 0; j < 5; ++j) { //列
if (arr[i][j] == '0') {
count++;
turn(i + 1, j); //变化下一行的同一位置
}
}
}
//检查最后一行是否全为1（前四行此时必定全为1）
bool flag = false;
for (int i = 0; i < 5; i++) {
if (arr[4][i] == '0') {
flag = true;
break;
}
}
//若通过，更新res
if (!flag) {
res = min(res, count);
}
//还原现场
memcpy(arr, backup, sizeof arr);
}
if (res > 6)
res = -1;
cout << res << endl;
}
return 0;
}5. Strange Towers of Hanoi AcWing96
解出n个盘子3座塔和4座塔的Hanoi（汉诺塔）问题最少需要多少步？
三座塔：设d[n]为n盘三塔问题的最少步骤，则有d[n] = 2 * d[n – 1] + 1
四座塔：设f[n]为n盘四塔问题的最少步骤，则有f[n] = min(1≤i<n){2 * f[i] + d[n – i]}
//三塔
#include <iostream>
using namespace std;
int hanoi(int n) {
if (n == 1)
return 1;
else {
return 2 * hanoi(n - 1) + 1;
}
}
int main() {
int n;
cin >> n;
cout << hanoi(n);
return 0;
}
//四塔
#include <iostream>
using namespace std;
int hanoi3(int n) {
if (n == 1)
return 1;
else {
return 2 * hanoi3(n - 1) + 1;
}
}
int hanoi4(int n) {
if (n == 1)
return 1;
else {
int res = 2 + hanoi3(n - 1);
for (int i = 2; i < n; i++) {
res = (res > (2 * hanoi4(i) + hanoi3(n - i))) ? (2 * hanoi4(i) + hanoi3(n - i)) : res;
}
return res;
}
}
int main() {
for (int i = 1; i <= 12; i++) {
cout << hanoi4(i) << endl;
}
return 0;
}视频讲解
https://pan.baidu.com/s/1Js1fR1N-XUm_xadjGJZZWQ?pwd=9q5d 提取码: 9q5d
