C语言课件 第25 26章.ppt

第25章 八皇后问题的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第25章 八皇后问题的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第25章 八皇后问题的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第25章 八皇后问题的实现,问题描述 问题分析及实现 开发过程常见问题及解决,八皇后问题的实现,国际象棋中，“皇后”在横、竖、两个方向的对角线上都可以吃对方的棋子。如果一个棋盘上有八个皇后，那么如何放置才可以相互不能攻击呢？又有多少种放置方案呢？本章就通过c语言来实现此算法。,25.1 问题描述,八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出：在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。,25.2 问题分析及实现,25.2.1 问题分析 25.2.2 问题实现 25.2.3 程序运行,25.2 问题分析及实现,对于此问题，首先想到的前面提到的要领：看清、想明、把握每一个细节。由问题描述可知，我们要实现的是找到皇后的行列坐标以及对应方案号即可。,25.2.1 问题分析,我们将要开发的程序，就是设置一个棋盘（nn，n=8），并设置此棋盘上所有点均是空的。然后一种情况一种情况地试验，遇到与问题的要求相匹配的情况时，方案数累加1，并输出这种情况。,25.2.2 问题实现,通过分析，我们得出此问题实现的2个要点：第一个是在哪种情况下，我们可以认为是与问题的要求一致；第二个是怎么划分模块。问题实现的代码如下。 1. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显，代码如下（代码25-1.txt）。,25.2.2 问题实现,01 #include 02 #define n 8 03 void output(int bcn,int *count) 04 05 int i; 06 int j; 07 *count=*count+1; 08 printf(“第%d种:n“,*count); 09 for(i=0;in;i+) 10 11 for(j=0;jn;j+) 12 13 if(bcij) 14 printf(“q“); /*在皇后位置打印q*/ 15 else 16 printf(“0“); /*在非皇后位置打印0*/ 17 18 printf(“nr“); 19 20 system(“pause“); /*暂停*/ 21 ,25.2.2 问题实现,2. 求解每种方案是否符合题目要求 我们采用递归的方法，可以很容易地将这个问题简化。就是要想让第八个皇后的情况合法，我们需要去找第七个合法的皇后位置。那么，要想让第七个皇后的位置合法，怎么办？当然是去找第六个皇后的位置，依此类推，可以推到第一个合法皇后的位置后，我们就返回调用处。代码如下（代码25-2.txt）。,25.2.2 问题实现,3. 主程序函数 可实现对数据初始化，调用问题求解功能函数，并输出最终方案个数。代码如下（代码25-3.txt）。,25.2.2 问题实现,01 void main() 02 03 int padnn; 04 int count=0; 05 int i ,j; 06 for(i=0;in;i+) 07 08 for(j=0;jn;j+) 09 10 padij=0; /*将棋牌中所有位置置为0进行初始化*/ 11 12 13 queen(pad,0, 15 ,25.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【enter】键，即可输出如下结果。,25.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 如何编写这个递归函数呢？这里所要写的递归函数的主要目的确认后，就可以编写正确的函数了，主要目的是试探方案是不是合法。无论如何，在函数中，一定要边写边思考一旦条件成立后，递归它时，程序运行的流程，控制的对吗？还要考虑函数递归结束后，返回到上次调用的那个位置之后。而且，我们采用的变量没有传递进递归函数，因此，函数返回后，需要归位。即将还原某些变量的值，在本例中，需要还原棋牌的最后试探的点，标为未试探，这样，程序可以一直试验其他情况。 此程序的难点之一理解本例的递归函数。递归的函数，本例中，只在一个地方调用自己。那就是找到一个合法皇后，再找下一个皇后，这样，只要找够8个皇后，则函数打印此方案并返回上次调用的位置。而在这个位置，向后执行，则是继续循环查找棋牌中其他位置上放置皇后是否合法，一旦合法，又将继续找本方案中下一个合法皇后。,第26章 商人过河游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第26章 商人过河游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第26章 商人过河游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第26章 商人过河游戏,问题描述 问题分析及实现 开发过程常见问题及解决,商人过河游戏,c语言的功能是强大而又灵活的。特别是在算法与数据结构上，其灵活性、高效性更加明显。本章研究对商人过河问题的求解。,26.1 问题描述,三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?,26.2 问题分析及实现,26.2.1 问题分析 26.2.2 问题实现 26.2.3 程序运行,26.2 问题分析及实现,对于此问题，首先想到的前面提到的要领：看清、想明、把握每一个细节。由问题描述可知，我们要实现的是打印安全过河的方案，即不触发杀人越货并能安全过河的方案。,26.2.1 问题分析,我们的将要开发的程序，就是从所有过河方案中，排除错误的方案，留下正确可行的方案。,26.2.2 问题实现,本小节就来通过编程来实现商人过河的游戏。 1. 采用结构体保存过程数据 通过定义一个结构体类型，模拟商人过河时，所有可能的方案及此方案的状态，即需要记录当前河东（原点）有几位商人、几位仆人，当前河西（目的地）有几位商人、几位仆人。实现代码见随书光盘中的代码26-1.txt。,26.2.2 问题实现,2. 求解问题的主要实现函数 由于渡河过程有两种情况：向东渡河，向西返回，因此，在设置的两个状态0,1时，均需要分别判断商人与仆人个数是否合法。代码如下（代码26-1.txt）。,26.2.2 问题实现,3. 求解问题的判断函数 如果合法则继续递归查找剩下的商人和仆人过河的方案，否则为不合法的方案，则应该将此方案放弃。放弃后，程序返回上一级，继续递归判断其他情况是否合法，直到全部情况递归完毕。代码如下（代码26-2.txt）,26.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【enter】键，即可输出如下结果。,26.3