《程序设计艺术与方法》课程实验报告实验名称姓名实验日期系院专业5.29指导教师实验二 搜索算法的实现班级徐本柱学号成绩一、实验目的和要求1.掌握宽度优先搜索算法。2.掌握深度优先搜索算法。二、实验预习内容1．预习 ICPC 讲义中的搜索的内容2. 了解什么是深度优先搜索和广度优先搜索。三、实验项目摘要1. 将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。3. 骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4.倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升的水，如果可以，输出步骤，如果不可以，请输出No Solution。四、实验结果与分析（源程序及相关说明）1.走迷宫代码算法采用深度优先搜索的思想，通过递归遍历 4 个方向实现寻找迷宫的终点。2.八皇后问题本算法使用回溯法，定义一个二维数组用于表示棋盘，遍历一行中每一个位置，依次从第一行开始循环，找到下一行第一个可行的位置，依次向下，知道找到 N 个皇后位置，可能数加一，返回上一层，接着之后的点，知道遍历完行中每一个位置，结束循环，此时得到所有可能的位置放置方法。思考：当 N 达到 14 以上是，此算法的时间将大大增加，我考虑本算法可以在每一次计算之后，直接剔除之后各行一些不可行的位置，以减少判断的次数，并且可以使用数组存储当前算法执行位置可行的点，这样可以减少循环的次数，降低时间复杂度。#include "stdafx.h"#include
#include#include#includeusing namespace std;#define N 16int n = 1; //皇后个数int sum = 0; //解个数int Cheekerboard[N]; //皇后放置位置表示，数组位置为行号，元素为列号//判断该位置是否可以放置int place(int x ,int k){int i;for (i = 0; i
