合工大程序設(shè)計(jì)藝術(shù)及方法實(shí)驗(yàn)二

.."程序設(shè)計(jì)藝術(shù)與方法"課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱實(shí)驗(yàn)二搜索算法的實(shí)現(xiàn)姓名系院專業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)日期5.29指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?.掌握寬度優(yōu)先搜索算法。2.掌握深度優(yōu)先搜索算法。二、實(shí)驗(yàn)預(yù)習(xí)容1．預(yù)習(xí)ICPC講義中的搜索的容2.了解什么是深度優(yōu)先搜索和廣度優(yōu)先搜索。三、實(shí)驗(yàn)工程摘要1.將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會(huì)搜索的思想。2.八皇后問題：在一個(gè)國際象棋棋盤上放八個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。3.騎士游歷問題：在國際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對(duì)于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑。4.倒水問題：給定2個(gè)沒有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出L升的水，如果可以，輸出步驟，如果不可以，請(qǐng)輸出NoSolution。實(shí)驗(yàn)結(jié)果與分析〔源程序及相關(guān)說明〕走迷宮代碼算法采用深度優(yōu)先搜索的思想，通過遞歸遍歷4個(gè)方向?qū)崿F(xiàn)尋找迷宮的終點(diǎn)。八皇后問題本算法使用回溯法，定義一個(gè)二維數(shù)組用于表示棋盤，遍歷一行中每一個(gè)位置，依次從第一行開場(chǎng)循環(huán)，找到下一行第一個(gè)可行的位置，依次向下，知道找到N個(gè)皇后位置，可能數(shù)加一，返回上一層，接著之后的點(diǎn)，知道遍歷完行中每一個(gè)位置，完畢循環(huán)，此時(shí)得到所有可能的位置放置方法。思考：當(dāng)N到達(dá)14以上是，此算法的時(shí)間將大大增加，我考慮本算法可以在每一次計(jì)算之后，直接剔除之后各行一些不可行的位置，以減少判斷的次數(shù)，并且可以使用數(shù)組存儲(chǔ)當(dāng)前算法執(zhí)行位置可行的點(diǎn)，這樣可以減少循環(huán)的次數(shù)，降低時(shí)間復(fù)雜度。#include"stdafx.h"#include<iostream>#include<math.h>#include<algorithm>#include<time.h>usingnamespacestd;#defineN16intn=1;//皇后個(gè)數(shù)intsum=0;//解個(gè)數(shù)intCheekerboard[N];//皇后放置位置表示，數(shù)組位置為行號(hào)，元素為列號(hào)//判斷該位置是否可以放置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<<"結(jié)果位置：";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)//未找到適宜的點(diǎn) {//完畢循環(huá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<<"輸入皇后個(gè)數(shù)：〔輸入0完畢循環(huán)〕："<<endl; cin>>n;//tm=time(0); t=Queen(n);if(n==0)//如果n=0，那么可行解個(gè)數(shù)為0，這種情況一定不要忽略 t=0; cout<<"可行解的個(gè)數(shù)為："<<t<<endl; sum=0;//printf("計(jì)算時(shí)間%d秒\n",(int)(time(0)-tm)); }return0;}騎士游歷問題使用貪心算法，使用二維數(shù)組表示棋盤，定義一個(gè)全局變量step=1，從指定點(diǎn)開場(chǎng)，尋找出口數(shù)最少的方向，跳轉(zhuǎn)至該方向，再將該點(diǎn)標(biāo)記為經(jīng)過點(diǎn)，用一個(gè)點(diǎn)構(gòu)造體表示一個(gè)數(shù)組用于存放路徑，將該點(diǎn)放入路徑中，接著step++，接著尋找該點(diǎn)的最少出口的點(diǎn)，如果返回，step--，那么進(jìn)入出口第二少的方向，直達(dá)沒有出口可走，判斷step==64.如果是，那么找到一條路徑，輸出，否那么就返回。#include"stdafx.h"#include<iostream>usingnamespacestd;//路徑點(diǎn)個(gè)數(shù)intstep=1;//棋盤數(shù)組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};//找到出口最少的點(diǎn)返回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<<"輸出一條可能路徑結(jié)果："<<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++)//把這個(gè)位置的所有可以動(dòng)的方向重新置為未訪問過 is_visit[path[step].x-1][path[step].y-1][i]=0; cout<<endl; } }}int_tmain(intargc,_TCHAR*argv[]){intx=0,y=0; cout<<"請(qǐng)輸入初始點(diǎn)坐標(biāo)(8*8棋盤)"<<endl;while(x>8||x<1||y>8||y<1) { cin>>x>>y; } findPath(x,y); OutPath();return0;}倒水問題：首先使用歐幾里得擴(kuò)展算法判斷輸入的升數(shù)是否有解，并且所求升數(shù)，是否小于等于兩容器體積之和，如果都成立，那么輸出過程，否那么，就輸出NoSolution；過程如下：如果A=L，裝滿A，如果B=L，裝滿B，如果L==A+B，裝滿A，B；如果A桶沒水,就裝滿水，如果A桶的水比(B桶容量-B桶的水)要多，就用A桶的水將B桶裝滿，清空B桶；否那么就將A桶的水全部倒入B桶中；在每一次倒水以后，判斷是否得出結(jié)果，如果得出，就完畢循環(huán)，接著輸出執(zhí)行的步驟。#include"stdafx.h"#include<iostream>#include<stdlib.h>#include<vector>#include<string>usingnamespacestd;/*倒水問題：給定2個(gè)沒有刻度容器，對(duì)于任意給定的容積，求出如何只用兩個(gè)瓶裝出L升的水，如果可以，輸出步驟，如果不可以，請(qǐng)輸出NoSolution。*///操作指令conststringOPERATOR_NAME[8]={"裝滿A桶","裝滿B桶","將A桶清空","將B桶清空","A桶中水倒入B桶","B桶中水倒入A桶","成功得到所需結(jié)果","NoSolution"};//判斷是否可以倒出,使用歐幾里得擴(kuò)展算法判斷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表示所求結(jié)果intpourWater(intx,inty,intz){vector<string>record;//記錄操作步數(shù)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