搜索算法小结
例题
指数型枚举
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
题解：
#include
using namespace std;
const int N = 20;
bool st[N];
int m; // 要输入的整数
void dfs(int n) {
if(n > m) { // 选完了
for(int i = 1; i <= m;i++) {
if(st[i])
cout << i << ' ';
}
cout << endl;
return;
}
// 不选这个数
dfs(n + 1);
// 选这个数
st[n] = true;
dfs(n + 1);
st[n] = false;
}
int main() {
cin >> m;
dfs(1);
return 0;
}
排列型枚举
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
题解：
#include
using namespace std;
const int N = 10;
bool st[N];
int re[N];
int u; // 要输入的数的个数
void dfs(int n) { // n 表示第几个位置
if(n > u) { // u个位置占满了
for(int i = 1;i <= u;i++)
cout << re[i] << " ";
cout << endl;
}
for(int i = 1;i <= u;i++) {
if(!st[i]) {
st[i] = true; // 表示i已经被选中
re[n] = i;
dfs(n+1);
st[i] = false;
}
}
}
int main() {
cin >> u;
dfs(1);
return 0;
}
递归实现组合型枚举
输入样例：
5 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
题解：
#include
#include
using namespace std;
int n,m; // 从 n个数 中选 m个数 出来
int way[30];
void dfs(int u,int start){ // u表示正在选第u个数，已经选了u-1个数字 ， start表示从数字几开始选
// 剪枝,提高搜索效率
if(u+n-startm){ // 已经找到m位数字可以输出
for(int i=1;i<=m;i++){
cout<>n>>m;
dfs(1,1); // 从第一个位置开始，从数字1开始选
return 0;
}
粘木棍
问题描述
有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。
输入格式
第一行两个整数N,M。
一行N个整数，表示木棍的长度。
输出格式
一行一个整数，表示最小的差距
思路：n根木棍粘贴成m根木棍，那么需要n - m次合并，使用搜索，递归不同的合并情况
递归边界--> 最后只剩下m根木棍，合并完成(一种情况)，计算最大值-最小值进行比较
题解：
#include
#include
using namespace std;
const int N = 10;
int a[N];
int n, m;
int res = INT_MAX;
// 还剩下n根木棍
void dfs(int k) {
// 还剩下m根木棍,合并完成
if (k == m) {
int pm = INT_MAX, pa = 0;
for (int i = 0; i < m; i++) {
if (pm > a[i])
pm = a[i];
if (pa < a[i])
pa = a[i];
}
res = min(res, pa - pm);
return;
}
for (int i = 0; i < k - 1; i++)
for (int j = i + 1; j < k; j++) {
a[i] += a[j]; // 合并i和j两根木棍到第i根
swap(a[j], a[k - 1]); // 第j根没用了和最后一根交换，数量-1
dfs(k - 1); // 合并减少一根木棍
// 恢复状态
swap(a[j], a[k - 1]);
a[i] -= a[j];
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
dfs(n);
cout << res << endl;
return 0;
}
24点游戏
思路：直接递归暴力搜索，搜索两个数的组合，每两个数的组合有四种运算符号
可以看成一次运算就是把两个数合并成一个数，那么减少的没用的数的值修改为0，作为一个数是否有效的判断条件。
题解：
#include
using namespace std;
int ans;
void dfs(int q[], int n) {
if (n == 4) {
for (int i = 0; i < 4; i++) {
if (q[i] && q[i] <= 24) {
ans = max(ans, q[i]);
break;
}
}
return;
}
// 四个数中选两个数的组合
for (int i = 0; i < 4; i++)
if (q[i] != 0)
for (int j = 0; j < 4; j++) {
if (i != j && q[j] != 0) {
int l = q[i], r = q[j];
q[i] = 0;
q[j] = l + r;
dfs(q, n + 1);
q[j] = l - r;
dfs(q, n + 1);
q[j] = l * r;
dfs(q, n + 1);
if (l % r == 0) {
q[j] = l / r;
dfs(q, n + 1);
}
// 恢复状态
q[i] = l;
q[j] = r;
}
}
}
int main() {
int n;
cin >> n;
while (n--) {
int q[4]; // 存储4个数字
ans = INT_MIN;
for (int i = 0; i < 4; i++)
cin >> q[i];
dfs(q, 1); // 第1次运算
cout << ans << endl;
}
return 0;
}
木棒
思路：
思路：这个题就是要把小棒一个个进行比较，看能不能恢复原棒，但是效率太低
1、首先是假设原木棒长度，最大的小棒 < 原木棒 < 所有小棒的长度总和，当遍历的原木棒长度 > 长度总和的一半时，原木棒的长度一定是总长sum
剪枝：1、过程中确定某根小棒是否成功被接收，在遍历某个小木棒时，对其后的木棒进行递归搜索。若当前木棒不可用，则和这根木棒相同长度的木棒也不可用，过滤掉长度相同的木棒
特殊情况：2、当拼接一根木棒的开头位置不成功，则该长度不符合；当拼接一根木棒的最后一个小木棒位置时，长度也不符合
3、当原木棒长度遍历超过总和sum 的一半时，说明原木棒的长度一定是sum，因为已经不够凑出两根原木棒了，这种情况下只能是1根。
题解
#include
#include
#include
using namespace std;
const int N = 80;
int s[N];
bool st[N];
int sum = 0, cnt, Len;
int n; // 段数
// cab当前第几段、 len当前段的长度 start开始的位置
bool dfs(int cab, int len, int start) {
if (cab > cnt)
return true; // 拼完了所有根数的原木棒
if (len == Len)
return dfs(cab + 1, 0, 0); // 拼完了一根原木棒
// 正在拼一根木棒,从start位置开始
for (int i = start; i < n; i++) {
if (st[i])
continue;
if (len + s[i] <= Len) {
st[i] = true;
if (dfs(cab, len + s[i], start + 1))
return true;
st[i] = false;
if (len == 0 || len + s[i] == Len)
return false;
while (s[i] == s[i + 1])
i++;
}
}
return false;
}
int main() {
while (cin >> n && n) {
sum = 0;
for (int i = 0; i < n; i++) {
cin >> s[i];
sum += s[i];
}
sort(s, s + n);
reverse(s, s + n); // 从大到小排序
// 遍历长度i
for (Len = s[0]; Len <= sum / 2; Len++) {
if (sum % Len)
continue;
cnt = sum / Len; // 原木棒数量
memset(st, 0, sizeof st);
if (dfs(1, 0, 0)) {
cout << Len << endl;
break;
}
}
if(Len > sum / 2) cout << sum << endl;
}
return 0;
}