一、引例
提问:输入一个数字n,输出1~n的全排列。
首先,将全排列比作小盒子和扑克牌
将数字比作扑克牌,我们有1号,2号,3号扑克牌和1号2号3号3个盒子。每个盒子只能放置一个扑克牌,实现全排列。那我们如何往小盒子中放入扑克牌。每个小盒子都可能放1号、2号或者3号扑克牌,这都需要一一尝试,这里一个for循环就可以解决问题。
for ( i = 1; i < n; i++)
{
a[step] = i; // 将i号扑克牌放入到第step个盒子中
}
其次,需要一个数组book来标记哪些牌已经使用了
数组a是用来表示小盒子的,变量step是用来表示房钱正处在第step个小盒子面前。
a[step] = i;就是将第i号扑克牌放入到第step个盒子中。
for (i = 1; i < n; i++)
{
if (book[i] == 0)
{
a[step] = i; // 将i号扑克牌放入到第step个盒子中
book[i] = 1; // 将book[i]设为1,表示i号扑克牌已经不在手上了
}
}
之后,包装递归dfs函数
目前,已经处理完第step个小盒子。
现在需要将这个包装成一个dfs函数,应用递归处理第step+1个小盒子。
如下:
void dfs(int step) // step表示现在站在第几个盒子面前
{
for (i = 1; i <= n; i++)
{
if (book[i] == 0)
{
a[step] = i; // 将i号扑克牌放入到第step个盒子中
book[i] = 1; // 将book[i]设为1,表示i号扑克牌已经不在手上了
}
}
return;
}
还有,将此过程写成函数,处理完step + 1个盒子后,递归dfs(step+1)。
下面的book[i]=0;非常重要,作用是将刚才尝试的扑克牌收回,才能进行下一次尝试
void dfs(int step)
{
if (step == n + 1)
{
// 当step等于n+1时,表示找到了一个全排列,打印结果
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)
{
a[step] = i; // 将第i个数放入排列中
book[i] = 1; // 标记数字i已经被使用
dfs(step + 1); // 递归进入下一步
book[i] = 0; // 回溯,将数字i标记为未使用
}
}
}
最后放一个,完整代码
#include <stdio.h>
#define MAXN 10
int a[MAXN], book[MAXN], n;
// 深度优先搜索函数,用于生成全排列
void dfs(int step)
{
if (step == n + 1)
{
// 当step等于n+1时,表示找到了一个全排列,打印结果
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)
{
a[step] = i; // 将第i个数放入排列中
book[i] = 1; // 标记数字i已经被使用
dfs(step + 1); // 递归进入下一步
book[i] = 0; // 回溯,将数字i标记为未使用
}
}
}
int main()
{
printf("请输入n的值:");
scanf("%d", &n);
if (n <= 0 || n > MAXN)
{
printf("无效的输入。请在1和%d之间输入一个值。\n", MAXN);
return 1;
}
dfs(1); // 从第一个位置开始深度优先搜索
return 0;
}
放一个运行截图吧
总结:
以上是一个简单的例子,核心代码不过20行,却包含深度优先搜索的基本模型。
理解深度优先搜索的关键在于解决“当下如何做”。至于“下一步如何做”则与“当下如何做”是一样的。
下面的代码就是深度优先搜索的基本模型。
void dfs(int step)
{
判断边界
尝试每一种可能 for (i = 1; i <= n; i++)
{
/* code */
继续进行下一步dfs(step + 1)
}
返回
}
每一种尝试就是一种“扩展”。每次站在一个盒子面前的时候,其实都有n种扩展方法,但是并不是每种扩展都能够扩展成功。
练习,使用深度优先搜索写一个1~n的数字全排列C语言代码
#include <stdio.h>
#include <stdbool.h>
// 定义一个全局数组,用于存储当前排列
int result[10];
// 定义一个数组来标记数字是否已经被使用
bool used[10];
int n; // 1 到 n 的数字
// 递归生成排列
void generatePermutations(int pos) {
// 如果已经生成了一个完整的排列,打印它
if (pos == n) {
for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
}
printf("\n");
return;
}
// 尝试每个数字
for (int i = 1; i <= n; i++) {
// 如果数字未被使用,将其添加到排列中
if (!used[i]) {
result[pos] = i;
used[i] = true;
generatePermutations(pos + 1);
used[i] = false; // 回溯,将数字标记为未使用
}
}
}
int main() {
printf("请输入一个1~9的数字: ");
scanf("%d", &n);
if (n >= 1 && n <= 9) {
for (int i = 1; i <= n; i++) {
used[i] = false; // 初始化used数组
}
generatePermutations(0);
} else {
printf("请输入1~9的数字\n");
}
return 0;
}
标签:优先,扑克牌,int,算法,dfs,step,book,小盒子,深度
From: https://www.cnblogs.com/yzx-sir/p/17780536.html