《程序设计艺术与方法》课程实验报告cout << "It's empty!" << en dl;实验名称搜索算法的实验姓名系院专业信息工程/ 物联网一学号班级系班实验日期指导教师成绩一、实验目的和要求1 •掌握宽度优先搜索算法。

2•掌握深度优先搜索算法。

二、实验预习内容1宽度优先搜索算法：又称广度优搜索。

是最简单的图的算法的原形。

其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。

换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

2深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。

在一个HTML文件中，当一个超链被选择后，被连接的HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

当不再有其他超链可选择时，说明搜索已经结束。

三、实验项目摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。

2 . 八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。

上机运行并检验结果。

思考：将此题推广到N 皇后的情况，检验在N 比较大的情况下，比方说N=16 的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。

3骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。

4 倒水问题：给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升的水，如果可以，输出步骤，如果不可以，请输出No Solution 。

四、实验结果与分析(源程序及相关说明)2，八皇后问题：#include <stdio.h>/*声明常量 N 存储行和列 */#define N 8#define NUM 8/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的* 纵坐标， count 用于计数。

*/int h[N][N],n[N],H[N][N];int count=0;/*声明函数 void tryit(int,int) 尝试符合条件的方法 */void tryit(int,int);/*声明函数 void outputArray(int[][N]) 输出数组 */void outputArray(int[][N]);main(){int x=0,y=0,i,j;/*初始化为零 */for(i=0;i<=N-1;i++){for(j=0;j<=N-1;j++)h[i][j]=0;}tryit(x,y);printf("// 其他的布局略 \n");printf("共有％d 种布局.\n",92);return(0);}/*定义函数 void tryit(int,int) 尝试符合条件的方法 */void tryit(int x,int y){int i,j;if(count<=NUM){/* 重复时跳出递归 */if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6 ]==1& &H[6][1]==1&&H[7][3]==1)&&count!=1){}else{if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0){/* 对与皇后在同一行、列、斜线上的点作出处理 */for(j=0;j<=7;j++){if(h[x][j]==0)h[x][j]=x+1;if(h[j][y]==0)h[j][y]=x+1;if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0)h[x+j][y+j]=x+1;if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0)h[x+j][y-j]=x+1;if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)h[x-j][y+j]=x+1;if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0)h[x-j][y-j]=x+1;}/* 对皇后处的点作出标志 */h[x][y]=-x-1;/* 完成一种走法作出处理 */if(x==7){/* 转换成输出的格式 */for(i=0;i<=N-1;i++){for(j=0;j<=N-1;j++){if(h[i][j]<0)H[i][j]=1;elseH[i][j]=0;}}count=count+1;/* 输出前几种情况 */if(count<=NUM){printf(" - 布局 %d -- \n",count);outputArray(H);}/* 对下一种走法，清楚前一次的影响 */for(i=0;i<=N-1;i++){for(j=0;j<=N-1;j++){if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1) h[i][j]=0;}/* 递归，尝试另一种方法 */tryit(x-1,n[x-1]+1);}/* 未走完一次，继续下一行 */else{n[x]=y;tryit(x+1,0);}}else{/* 此路不通时，返回上一行，尝试下一种方法 */if(y>7){/* 清楚前一次影响 */for(i=0;i<=N-1;i++){for(j=0;j<=N-1;j++){if(h[i][j]==x||h[i][j]==-x) h[i][j]=0;}}/* 分情况递归 */if(x-1>=0)tryit(x-1,n[x-1]+1);elsetryit(0,0);}/* 尝试下一格 */e-semx ylx「M x ®達voidoufpufAlray(inq=ND鸯圧達^*、voidoufputAlray(infh s z )宀in 二"f o r T o x H N —l T +)宀folxjHojAHN —二+ +)p 「imf(=%d =h三导prinmvl)ttinc-ude=sfdio.h=inf main 。

宀infcao bo cx Mwh=e(scanf(=%d%d%d=QOcaQOcbQOcc)HEOF)宀 if(cbHHCC) 宀 p 「inm =h=Bwxe-se if(caHHCC)宀else{x=y=0;if(ca<cc){while(1){ if(y==0){y=cb; printf("fill B\n");}if(y>ca-x)//如果 b 中的水大于 a 中的剩余容积，就把 a 灌满 //{ y-=ca-x; x=ca; printf("pour B A\n");}else//如果b中的水小于a中的剩余容积，那么把b中的水全加入all{x+=y;y=0; printf("pour B A\n");}if(y==cc)〃如果b中的水已经和cc相等，那就结束//{break;}if(ca==x)//如果a中的水满了，就把a倒空//{x=0;printf("empty A\n");}}else{while(1){if(x==0){x=ca; printf("fill A\n");}if(x>cb-y)//如果 a 中的水大于 b 中的剩余容积，就把 b 灌满 //{ x-=cb-y; y=cb; printf("pour A B\n");}else//如果a中的水小于b中的剩余容积，那么把a中的水全加入b〃{y+=x;x=0;printf("pour A B\n");}if(y==cc)//如果 b 中的水已经和 cc 相等，那就结束 //{break;}if(y==cb)II如果b中的水满了，就把b倒空//y=0;printf("empty B\n");}}}}prin tf("success\n");}return 0; }运行截图：。