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 803 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 开发过程常见问题及解决,此程序的难点是如何正确理解渡河的函数运行情况。通过分析问题，需要确认：人员情况需要在每次渡完河时判断。因为渡河过程中，小船只能容纳两个，此时，小船上是安全的。另外，如果在某一方案下，一种情况不成功，则需要回退，而且两岸人员的状态（个数等）也需要回退，否则永远找不到正确答案。,
