DFS入门刷题c++

目录

821. 跳台阶 - AcWing题库

​92. 递归实现指数型枚举 - AcWing题库 

​P1706 全排列问题 - 洛谷 (luogu.com.cn)

P1157 组合的输出 - 洛谷 (luogu.com.cn)

​P1036 [NOIP 2002 普及组] 选数 - 洛谷 (luogu.com.cn)

P2089 烤鸡 - 洛谷 (luogu.com.cn)

P1088 [NOIP 2004 普及组] 火星人 - 洛谷 (luogu.com.cn)

---

 821. 跳台阶 - AcWing题库

#include<iostream>
using namespace std;
int t(int n) {if (n <= 2)return n;if (n >= 3)return t(n - 1) + t(n - 2);
}
int main() {int n; cin >> n;cout << t(n);return 0;
}

92. 递归实现指数型枚举 - AcWing题库 

#include<iostream>
using namespace std;
int n;
int s[20];//0表示未考虑;1表示选;2表示不选
void dfs(int x) {if (x > n) {for (int i = 1; i <= n; i++) {if (s[i] == 1)cout << i << " ";}cout << endl;return;}for (int i = 1; i <= 2; i++) {s[x] = i;dfs(x + 1);}
}
int main() {cin >> n;dfs(1);return 0;
}

 P1706 全排列问题 - 洛谷 (luogu.com.cn)

#include<iostream>
using namespace std;
int n;
int s[20];
bool vis[20];
void dfs(int x) {if (x > n) {for (int i = 1; i <= n; i++) {printf("%5d", s[i]);}cout << endl;return;}for (int i = 1; i <= n; i++) {if (!vis[i]) {vis[i] = true;s[x] = i;dfs(x + 1);vis[i] = false;s[x] = 0;}}
}
int main() {cin >> n;dfs(1);return 0;
}

 P1157 组合的输出 - 洛谷 (luogu.com.cn)

#include<iostream>
using namespace std;
int n, r;
int a[25];
void dfs(int x, int start) {if (x > r) {for (int i = 1; i <= r; i++) {printf("%3d", a[i]);}cout << endl;return;}for (int i = start; i <= n; i++) {a[x] = i;dfs(x + 1, i + 1);a[x] = 0;}
}
int main() {cin >> n >> r;dfs(1,1);return 0;
}

 P1036 [NOIP 2002 普及组] 选数 - 洛谷 (luogu.com.cn)

#include<iostream>
using namespace std;
int n, k;
int a[25]; int s[25];
int res;
bool jud(int t) {if (t < 2)return false;for (int i = 2; i * i <= t; i++) {if (t % i == 0)return false;}return true;
}
void dfs(int x, int start) {if (x > k) {int sum = 0;for (int i = 1; i <= k; i++) {sum += s[i];}if (jud(sum))res++;return;}for (int i = start; i <= n; i++) {s[x] = a[i];dfs(x + 1, i + 1);s[x] = 0;}
}
int main() {cin >> n >> k;for (int i = 1; i <= n; i++)cin >> a[i];dfs(1, 1);cout << res;return 0;
}

P2089 烤鸡 - 洛谷 (luogu.com.cn)

#include<iostream>
using namespace std;
int n;
int res;
int a[60000][11];
int tem[11];
void dfs(int x, int sum) {if (sum > n)return;if (x > 10) {if (sum == n) {res++;for (int i = 1; i <= 10; i++) {a[res][i] = tem[i];}}return;}for (int i = 1; i <= 3; i++) {tem[x] = i;dfs(x + 1, sum + i);}
}
int main() {cin >> n;dfs(1, 0);cout << res << endl;for (int i = 1; i <= res; i++) {for (int j = 1; j <= 10; j++) {cout << a[i][j] << " ";}cout << endl;}return 0;
}

 P1088 [NOIP 2004 普及组] 火星人 - 洛谷 (luogu.com.cn)

#include<iostream>
using namespace std;
int n, m;
int res;
const int N = 10010;
int a[N]; bool vis[N]; int mars[N];
void dfs(int x) {if (x > n) {res++;if (res == m + 1) {for (int i = 1; i <= n; i++) {cout << a[i] << " ";}exit(0);//剪枝，输出之后强制退出}}for (int i = 1; i <= n; i++) {if (!res) {i = mars[x];}if (!vis[i]) {vis[i] = true;a[x] = i;dfs(x + 1);vis[i] = false;a[x] = 0;}}
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> mars[i];dfs(1);return 0;
}

P1149 [NOIP 2008 提高组] 火柴棒等式 - 洛谷 (luogu.com.cn)

#include <iostream>
using namespace std;
int n;
int res;
const int N = 10010;
int a[N];
int num[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int col(int p)
{if (num[p]){return num[p];}else{int t = 0;while (p){t += num[p % 10];p /= 10;}return t;}
}
void dfs(int x, int sum)
{if (sum > n){return;}if (x > 3){if (a[1] + a[2] == a[3] && sum == n){res++;}return;}for (int i = 0; i < N / 10; i++){a[x] = i;dfs(x + 1, sum + col(i));a[x] = 0;}
}
int main()
{cin >> n;n -= 4;dfs(1, 0);cout << res;return 0;
}

P2036 [COCI 2008/2009 #2] PERKET - 洛谷 (luogu.com.cn) 

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
int n;
int s[11];
int b[11];
int t[11]; // 0:未考虑；1：选；2：不选
int res = INT_MAX;
bool flag;
void dfs(int x)
{if (x > n){int x = 1;int y = 0;for (int i = 1; i <= n; i++){if (t[i] == 1){flag = true;x *= s[i];y += b[i];}}if (flag){res = min(abs(x - y), res);flag = false;}return;}for (int i = 1; i <= 2; i++){t[x] = i;dfs(x + 1);t[x] = 0;}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> s[i] >> b[i];}dfs(1);cout << res;return 0;
}