[数据结构与算法]《啊哈，算法》-9-深度优先遍历-C语言编程实现（小游戏情景学习）

一、问题描述

再次使用这个小案例：
一道奥数题目：将数字1-9分别填入9个【】中，每个数字只能使用一次使得等式成立。
【】【】【】+【】【】【】=【】【】【】
请问一共有多少中合理的组合呢？
注意：173+286=459与286+173=459是同一种组合。
上次我们使用的方法是枚举法。

二、思路解析及深度优先遍历

其实这道题可以加一个情景：
你手里有编号1-9的9张扑克牌，然后将这9张牌放在9个盒子中。
并使得【】【】【】+【】【】【】=【】【】【】成立。
一共有多少种方法？

深度优先遍历（Depth First Search:dfs）：
该模型在于解决“当下应该如何做",至于“下一步如何做”，则与“当下应该如何做”是一样的。
通常的方法就是把每一种可能都尝试一遍（一般使用for循环来实现），当前的一步解决了就进入下一步。
下一步的解决方法和当前完全是一样的。
深度优先遍历基本模型如下：

void dfs(int step){
	判断边界
	尝试每一种可能for(i=1;i<=n;i++)
	{
		继续下一步dfs(step+1) 
	}
	返回 
	 
}

三、代码复现

#include<stdio.h> 
int a[10],book[10],total=0;
void dfs(int step)//step表示现在站在第几个盒子面前
{
	int i;
	if(step==10)//如果站在第10个盒子面前，则表示前边9个盒子已经放好扑克牌
	{
		//判断是否满足等式【】【】【】+【】【】【】=【】【】【】
		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])
		{
			//如果满足要求，可行解加1，并且打印这个结果。
			total++;
			printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
		}	
		return;//返回之前的一步（最近调用的地方）	 	 
	} 
    //此时站在第step个盒子面前，应该放哪一张牌呢？
	//按照1、2、3...n的顺序，一一尝试
	for(i=1;i<=9;i++)
	{ 
	   //判断扑克牌i是否还在手上 
		if(book[i]==0);//如果==0表示还在手上 
		{						
			//开始尝试使用扑克牌
			a[step]=i;//将扑克牌i放入第step个盒子中
			book[i]=1;//将book[i]的值设置为1，表示扑克牌i不在手上
			
			//第step个盒子中已经放好了牌，走到下一个盒子面前
			dfs(step+1);//这里通过函数的递归来实现（自己调用自己）
			
			//这是非常重要的一步，一定要将刚才尝试的扑克牌收回来，才能进行下一次的尝试
			book[i]=0; 
		}												
	} 
	return;
} 

int main(){
	dfs(1);//首先站在一个盒子面前 
	printf("total=%d",total/2);
	getchar();
	getchar();
	return 0; 
}

四、总结

深度优先遍历，每一种尝试都是一种扩展，每次站在盒子前边，其实有n中扩展方法，但是并不是每一种扩展都可以成功。