《程序设计艺术与方法》课程实验报告一二实验名称搜索算法的实验姓名系院专业信息工程系班级物联网一班学号实验日期指导教师成绩一、实验目的和要求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);}/*尝试下一格*/elsetryit(x,y+1);}}}}/*定义函数void outputArray(int[][N])输出数组*/ void outputArray(int h[][N]){int i,j;for(i=0;i<=N-1;i++){for(j=0;j<=N-1;j++)printf("%d ",h[i][j]);printf("\n");}}运行截图：4.倒水问题：#include"stdio.h"int main(){int ca,cb,cc,x,y;while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF) {if(cb==cc){ printf("fill B\n");}else if(ca==cc){printf("fill A\n");printf("pour A B\n");}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中的水全加入a//{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)//如果b中的水满了，就把b倒空//{y=0;printf("empty B\n");}}}}printf("success\n");}return 0;}运行截图：三。