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

.."程序设计艺术与方法"课程实验报告实验名称实验二搜索算法的实现姓名系院专业班级学号实验日期5.29指导教师徐本柱成绩一、实验目的和要求1.掌握宽度优先搜索算法。2.掌握深度优先搜索算法。二、实验预习容1．预习ICPC讲义中的搜索的容2.了解什么是深度优先搜索和广度优先搜索。三、实验工程摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。3.骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4.倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。实验结果与分析〔源程序及相关说明〕走迷宫代码算法采用深度优先搜索的思想，通过递归遍历4个方向实现寻找迷宫的终点。八皇后问题本算法使用回溯法，定义一个二维数组用于表示棋盘，遍历一行中每一个位置，依次从第一行开场循环，找到下一行第一个可行的位置，依次向下，知道找到N个皇后位置，可能数加一，返回上一层，接着之后的点，知道遍历完行中每一个位置，完毕循环，此时得到所有可能的位置放置方法。思考：当N到达14以上是，此算法的时间将大大增加，我考虑本算法可以在每一次计算之后，直接剔除之后各行一些不可行的位置，以减少判断的次数，并且可以使用数组存储当前算法执行位置可行的点，这样可以减少循环的次数，降低时间复杂度。#include"stdafx.h"#include<iostream>#include<math.h>#include<algorithm>#include<time.h>usingnamespacestd;#defineN16intn=1;//皇后个数intsum=0;//解个数intCheekerboard[N];//皇后放置位置表示，数组位置为行号，元素为列号//判断该位置是否可以放置intplace(intx,intk){inti;for(i=0;i<x;i++)if(abs(x-i)==abs(k-Cheekerboard[i])||k==Cheekerboard[i])return0;return1;}voidprint()//打印输出N皇后的一组解{inti,j;for(i=0;i<n;++i) {for(j=0;j<n;++j) {if(Cheekerboard[i]!=j)//a[i]为初始值 cout<<".\t";else//a[i]表示在第i行的第a[i]列可以放置皇后 cout<<"*\t"; } cout<<endl; }//输出放置位置 cout<<"结果位置：";for(i=0;i<n;++i) cout<<"("<<i+1<<","<<Cheekerboard[i]+1<<")"; cout<<endl; cout<<"--------------------------------"<<endl;}intQueen(inti){inta=0,b=0;while(a<n) {while(b<n) {if(place(a,b)) { Cheekerboard[a]=b; b=0;break; }else { b++; } }if(b==n)//未找到适宜的点 {//完毕循环，找到所有可能if(a==0)break;else {//回到上一行 a--; b=Cheekerboard[a]+1;continue; } }if(a==n-1) {//找到一种解法 sum++;//cout<<"解法"<<sum<<":"<<endl;//print(); a--; b=Cheekerboard[a]+1;continue; } a++; }returnsum;}int_tmain(intargc,_TCHAR*argv[]){time_ttm;intt;while(n>0){ cout<<"输入皇后个数：〔输入0完毕循环〕："<<endl; cin>>n;//tm=time(0); t=Queen(n);if(n==0)//如果n=0，那么可行解个数为0，这种情况一定不要忽略 t=0; cout<<"可行解的个数为："<<t<<endl; sum=0;//printf("计算时间%d秒\n",(int)(time(0)-tm)); }return0;}骑士游历问题使用贪心算法，使用二维数组表示棋盘，定义一个全局变量step=1，从指定点开场，寻找出口数最少的方向，跳转至该方向，再将该点标记为经过点，用一个点构造体表示一个数组用于存放路径，将该点放入路径中，接着step++，接着寻找该点的最少出口的点，如果返回，step--，那么进入出口第二少的方向，直达没有出口可走，判断step==64.如果是，那么找到一条路径，输出，否那么就返回。#include"stdafx.h"#include<iostream>usingnamespacestd;//路径点个数intstep=1;//棋盘数组intCheckerboard[8][8]={0};//可能的方向intseatx[8]={-2,-1,1,2,2,1,-1,-2};intseaty[8]={1,2,2,1,-1,-2,-2,-1};//可选方向intis_visit[8][8][8]={0};structpoint{intx;inty;};pointpath[64]={0};//找到出口最少的点返回boolMinpoint(intx,inty,point&seat){intmin=9;intcount=0;intk;for(inti=0;i<8;i++) {if(!is_visit[x-1][y-1][i])if((x+seatx[i])>0&&(y+seaty[i])>0&&(x+seatx[i])<9&&(y+seaty[i])<9) {if(Checkerboard[x-1+seatx[i]][y-1+seaty[i]]==0) { count=0;for(intj=0;j<8;j++) {if((x+seatx[i]+seatx[j])>0&&(y+seaty[i]+seaty[j])>0&&(x+seatx[i]+seatx[j])<8&&(y+seaty[i]+seaty[j])<8) {if(Checkerboard[x-1+seatx[i]+seatx[j]][y-1+seaty[i]++seaty[j]]==0) count++; } }if(count<min) { min=count;seat.x=x+seatx[i];seat.y=y+seaty[i]; k=i; } } } }if(min==9)returnfalse;else { is_visit[x-1][y-1][k]=1;returntrue; }}voidOutPath(){ cout<<"输出一条可能路径结果："<<endl;intj=0;for(inti=0;i<64;i++) { cout<<"("<<path[i].x<<","<<path[i].y<<")"<<"->";if(j<9) j++;else { j=0; cout<<endl; } } cout<<"END"<<endl; system("pause");}voidfindPath(intx,inty){ path[0].x=x; path[0].y=y; Checkerboard[x-1][y-1]=1;while(true) {if(Minpoint(path[step-1].x,path[step-1].y,path[step])) { Checkerboard[path[step].x-1][path[step].y-1]=1; step++; }elseif(step==64)break;else { step--; Checkerboard[path[step].x-1][path[step].y-1]=0;for(inti=0;i<8;i++)//把这个位置的所有可以动的方向重新置为未访问过 is_visit[path[step].x-1][path[step].y-1][i]=0; cout<<endl; } }}int_tmain(intargc,_TCHAR*argv[]){intx=0,y=0; cout<<"请输入初始点坐标(8*8棋盘)"<<endl;while(x>8||x<1||y>8||y<1) { cin>>x>>y; } findPath(x,y); OutPath();return0;}倒水问题：首先使用欧几里得扩展算法判断输入的升数是否有解，并且所求升数，是否小于等于两容器体积之和，如果都成立，那么输出过程，否那么，就输出NoSolution；过程如下：如果A=L，装满A，如果B=L，装满B，如果L==A+B，装满A，B；如果A桶没水,就装满水，如果A桶的水比(B桶容量-B桶的水)要多，就用A桶的水将B桶装满，清空B桶；否那么就将A桶的水全部倒入B桶中；在每一次倒水以后，判断是否得出结果，如果得出，就完毕循环，接着输出执行的步骤。#include"stdafx.h"#include<iostream>#include<stdlib.h>#include<vector>#include<string>usingnamespacestd;/*倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。*///操作指令conststringOPERATOR_NAME[8]={"装满A桶","装满B桶","将A桶清空","将B桶清空","A桶中水倒入B桶","B桶中水倒入A桶","成功得到所需结果","NoSolution"};//判断是否可以倒出,使用欧几里得扩展算法判断intgcd(inta,intb){returnb"gcd(b,a%b):a;}booljuege(intx,inty,intz){intk=gcd(x,y);if(z%k==0&&(x+y)>(z-1))return1;elsereturn0;}//x表示A桶体积，y表示B桶体积，z表示所求结果intpourWater(intx,inty,intz){vector<string>record;//记录操作步数inta_water,b_water; a_water=b_water=0;//A桶，B桶中有多少升水charszTemp[30];while(true) {if(x==z) { a_water=x; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[0]+szTemp);//fillAbreak; }elseif(y==z) { b_water=y; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[1]+szTemp);//fillbbreak; }elseif(x+y==z) { a_water=x; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[0]+szTemp);//fillA b_water=y; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[1]+szTemp);//fillbbreak; }elseif(a_water==0)//A桶没水,就装满水 { a_water=x; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[0]+szTemp);//fillAif(a_water+b_water==z)break; }else {//如果A桶的水比(B桶容量-B桶的水)要多if(a_water>y-b_water) {//A桶的水==A桶的水+B桶的水-B桶容量 a_water=a_water+b_water-y; b_water=y;//B桶的水装满了 sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[4]+szTemp);//A->Bif(a_water==z) { b_water=0;//将B桶清空 sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[3]+szTemp);break; } b_water=0;//将B桶清空 sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAME[3]+szTemp);if(a_water+b_water==z)break; }else {//B桶的水==A桶的水+B桶的水 b_water+=a_water; a_water=0; sprintf(szTemp,"A:%dB:%d",a_water,b_water); record.push_back(OPERATOR_NAM