欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

啊哈 , 算法 !--深度优先搜索( 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;
}

调试如下 : 

啊哈 , 算法 !--深度优先搜索( C语言版 )

 

相关标签: 深度优先搜索