合工大 程序设计艺术与方法 实验二

《合工大 程序设计艺术与方法 实验二》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档《程序设计艺术与方法》课程实验报告实验名称实验二搜索算法的实现姓名系院专业班级学号实验日期5.29指导教师徐本柱成绩一、实验目的和要求1.掌握宽度优先搜索算法。2.掌握深度优先搜索算法。二、实验预习内容1．预习ICPC讲义中的搜索的内容2.了解什么是深度优先搜索和广度优先搜索。三、实验项目摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。3.骑士游历问题：在国际棋盘上

2、使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4.倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。文案大全实用文档四、实验结果与分析（源程序及相关说明）1.走迷宫代码算法采用深度优先搜索的思想，通过递归遍历4个方向实现寻找迷宫的终点。2.八皇后问题本算法使用回溯法，定义一个二维数组用于表示棋盘，遍历一行中每一个位置，依次从第一行开始循环，找到下一行第一个可行的位置，依次向下，知

3、道找到N个皇后位置，可能数加一，返回上一层，接着之后的点，知道遍历完行中每一个位置，结束循环，此时得到所有可能的位置放置方法。思考：当N达到14以上是，此算法的时间将大大增加，我考虑本算法可以在每一次计算之后，直接剔除之后各行一些不可行的位置，以减少判断的次数，并且可以使用数组存储当前算法执行位置可行的点，这样可以减少循环的次数，降低时间复杂度。#include"stdafx.h"#include#include#include#include

4、.h>usingnamespacestd;#defineN16intn=1;//皇后个数intsum=0;//解个数intCheekerboard[N];//皇后放置位置表示，数组位置为行号，元素为列号//判断该位置是否可以放置intplace(intx,intk){inti;for(i=0;i

5、

6、k==Cheekerboard[i])return0;文案大全实用文档return1;}voidprint()//打印输出N皇后的一

7、组解{inti,j;for(i=0;i

8、----------------"<

9、t<<"解法"<0){cout<<"输入皇后个数：（输入0结束循环）："<>n;//tm=time(0);t=Queen(n);if(n==0)//如果n=0，则可行解个数为0，这种情况一定不要忽略t=0;cout<<"可行解的个数为

10、："<