啊哈 , 算法 !--深度优先搜索( C语言版 )
程序员文章站
2022-03-13 22:06:44
...
深度优先搜索 : 理解的关键在于解决“当下该如何做”。至于“下一步该如何做”则与“当下该如何做”是一样的
问题 : 求出123的全排列
- 123 132 213 231 312 321
这里我们可以用一个a数组去存放要排列的数组, 再用一个book数组去标记哪些数已经被使用了 .
代码如下 :
#include <stdio.h>
#include <stdlib.h>
//在全局变量中,数组默认为0
int a[5], book[5], n = 3;
void Dfs(int step)
{
int i;
//当数组a存放了1-3所有元素且每个数都是被标记过的,证明该序列满足
if (step == n + 1){
for (i = 1; i <= n; i++)
printf("%d", a[i]);
printf("\n");
return;
}
for (i = 1; i <= n; i++){
//判断该位置是否被标记过
if (book[i] == 0){
//将i存入到数组的第step的位置中
a[step] = i;
//标记i位置证明i已经存入到a数组当中
book[i] = 1;
//更新step继续执行循环
Dfs(step + 1);
//将刚标记的位置收回,执行下一次尝试
book[i] = 0;
}
}
return;
}
int main()
{
//首先从第一个数字开始
Dfs(1);
system("pause");
return 0;
}
类似问题 : 现在你手中有编号1-9的九张扑克牌, 然后将这九张扑克牌放到九个盒子中, 并使得□□□ + □□□ = □□□ 成立
#include <stdio.h>
#include <stdlib.h>
//在全局变量中,数组默认为0
int a[10], book[10], n = 9,num = 0;
void Dfs(int step)
{
int i;
//当数组a存放了1-9所有元素且每个数都是被标记过的,证明该序列满足
if (step == n + 1){
if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6]
== a[7] * 100 + a[8] * 10 + a[9]) {
num++;
printf("%d%d%d + %d%d%d = %d%d%d", a[1], a[2], a[3],
a[4], a[5], a[6], a[7], a[8], a[9]);
printf("\n");
return;
}
}
for (i = 1; i <= n; i++){
//判断该位置是否被标记过
if (book[i] == 0){
//将i存入到数组的第step的位置中
a[step] = i;
//标记i位置证明i已经存入到a数组当中
book[i] = 1;
//更新step继续执行循环
Dfs(step + 1);
//将刚标记的位置收回,执行下一次尝试
book[i] = 0;
}
}
return;
}
int main()
{
//首先从第一个数字开始
Dfs(1);
//num要除二是因为718 + 236 = 954 和 236 + 718 = 945是同一种可能
printf("一共有%d可能!\n", num / 2);
system("pause");
return 0;
}
调试如下 :
推荐阅读