算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告3

1、武漢z o a f計(jì)算機(jī)科學(xué)與工程學(xué)院算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告專業(yè)班級(jí)實(shí)驗(yàn)地點(diǎn)學(xué)生學(xué)號(hào)指導(dǎo)教師張立學(xué)生姓名實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)項(xiàng)目圖的搜索算法實(shí)驗(yàn)類別設(shè)計(jì)性實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康募耙竽康呐c要求：練習(xí)圖的搜索算法的使用實(shí)驗(yàn)內(nèi)容要點(diǎn)：1、熟悉廣度優(yōu)先搜索算法以及深度優(yōu)先搜索算法的應(yīng)用2、掌握冋溯法和分支限界法的應(yīng)用成績?cè)u(píng)定表類另ij評(píng)分標(biāo)準(zhǔn)分值得分合計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律 主動(dòng)完成實(shí)驗(yàn)設(shè)計(jì)任務(wù)30分實(shí)驗(yàn)報(bào)告及時(shí)遞交、填寫規(guī)范 內(nèi)容完整、體現(xiàn)收獲70分說明：評(píng)閱教師：日期：年月日實(shí)驗(yàn)內(nèi)容1、走迷宮問題。迷宮是許多小方格構(gòu)成的矩形，如圖3-3所示，在每個(gè)小方格中有的是墻（圖 中的“1”）有的是路（圖中的“0”）。

2、走迷宮就是從一個(gè)小方格沿上、下、左、右四個(gè)方向 到鄰近的方格，當(dāng)然不能穿墻。設(shè)迷宮的入口在左上角（1,1）,出口是右下角（8, 8） o根據(jù)給 定的迷宮，找出一條入口到出口的路徑。0000000001111010000010100100001001011010010000110100100001111110圖3-1迷宮矩形圖#include<iostream.h>int maze8 8= 0,0,0,0,0,0,0,0, 0,1,1,1,1,0,1,0, 0,0,0,0丄0丄0, 0,1,0,0,0,0,1,0,0,1,0,14,0,1,0,0,1,0,0,0,0,1,1, 0,1

3、,0,0,1,0,0,0, 0,1,1,1,1,1,1,0;int fx4=1,-1,0,0 ,fy 4=0,0,-1,1;structint x,y,pre;sq100;int qh,qe,i,j,k;int check(int i,int j);int search();void out(); void main()search();int search()qh=o;qe=l; maze00=-l;sqo.pre=o;sq0.x=0; sqo.y=o;while(qh!=qe)qh=qh+l; for(k=0;k<=3 ;k+) i=sqqh.x+fxk;j=sqqh.y+fyk;

4、if(check(i,j)=l)qe 二 qe+1;sqqe.x=i;sqqe.y=j; sqqe<pre=qh; mazeij=-l;if(sqqe.x=7&&sq qe .y=7) out();return 0;cout«"non solution an"int check(int i,int j)int flag=l; if(i<0|i>7|j<0|u>7) flag=0;if(mazeij=l|mazeij=-l)flag=0; return(flag);void out() cout«n(n

5、1;sqqe.x«,«sqqe.y«n)"«endl; while(sq qe .pre! =0)qe=sqqe.pre;cout«h-,«,("«sqqe.x«,；,«sqqe.y«,),f«endl;亍 we:vclllldebugllllexe,i 口| 回 |牛g|<?,?><6,7一一<6.5一一<5.5一一匕4一一03-<5,2一一<4,2一一<3.2<2,2>一一c2.1<2,0>

6、<1,0><0,0>press any key to continue.圖322、有如圖3-3所示的七巧板，試設(shè)計(jì)算法，使用至多4種不同顏色對(duì)七巧板進(jìn)行涂色（每 塊涂一種顏色），要求相鄰區(qū)域的顏色互不和同，打印輸出所有可能的涂色方案。#include<stdio.h>int data88,n=8,color8,total;void trys(int s);int colorsame(int s);void output();void main()int i,j； for(i=l;i<=7;i+) forg=l;j<=7;j+) scanf(”d”

7、,&d atai|j);for(j=l;j<=7;j+)colorj=0;total=0;trys(l);printf(nntotal=%dn,total);void trys(int s)int i;if(s>7)output();elsefor(i=l;i<=4;i+)colors=i;if(colorsame(s)=0)trys(s+l);int colorsame(int s)int i,flag;flag=0;for(i=l;i<=s-l;i+)if(datai s= 1 &&colori=colors) flag=l;retum(fl

8、ag);void output()int i;printf(hnserial numble:%dnh,total); for(i=l;i<n;i+)printf(n%d n,colori);total=total+1; "e:vclllldebugllll.exe""“卜=小回serial nunble：575221243serial nunble：576223211serial nunble：577223241serial nunble：578223311serial nunble：579223341serial nunble：580224113seria

9、l nunble：58142241331nti < 1mh圖3-43、馬的遍歷問題：在n*m的棋盤上，馬只能走日字，馬從位置(x, y)處出發(fā)，把棋盤的 每一點(diǎn)都走一次，且只能走一次，找出所有的路徑。#include<stdio.h>void find(int x,int y,int dep);void output();int check(int b,int c);int m=5,n=4,count,dep;int fx9=0 丄fy9>0,2,l,-l,-2,-2,-l,l,2,a65;void main()count=0;int i,j,x,y;dep=l;sca

10、nf("%d%du,&x,&y);if (x>m|y>n|x<l|y<l)printf("x,y error!");return ;for(i=l;i<=m;i+) for(j=l；j<=n;j+)aij=o;axy=l;find(x,y,2);if(count=0)printf(hno answer!h);elseprintf(ucount=%d,count);void find(int y,int dep)int i.xxjy;for (i=l;i<=8;i+)加上方向增量,形成新的坐標(biāo)xx

11、=x+fxi; yy=y+fyi;if(check(xx,yy)= 1)判斷新坐標(biāo)是否出界,是否己走過?alxxjlyyj=dep;走向新的坐標(biāo)if (dep=n*m) output();elsefind(xx，yy,dep+l);從新坐標(biāo)出發(fā)，遞歸下一層axxyy=0;冋溯，恢復(fù)未走標(biāo)志 void output()int i,j; count=count+l; printf(nnn); printf(ucount=%d,count); for(i=l;i<=m;i+ )printf(hnn); for(j=l；j<=n;j+)printf(“3ct,aij);int check(

12、int bjnt c)if(!(b< l|b>m|c< l|c>n)訐(abc=0)return 1;elsereturn 0; elsereturn 0;20"e:vclllldebugllll163count =11 10 1514 192581118 136741712count =21 10 17 129圖3-5581116141963741520=31615201613275101914121783941118=4161914181327510152012178394111618 1324、按排列樹搜索解決8皇后問題。 #include<std

13、io. h>int a100, n, s=0, c20, d20; vold swap(int tl, int 12) int t;t=atl; atl=at2;at2=t; void output () int j;printf(n)； for(j=l;j<=n;j+) printf (，z%d ，aj);s+; void trys(int t) int j;if (t>n) output ();else for(j=t;j<=n;j+) swap(t, j);if(ct+at=0&&dt-at+n=0) ct+at=l;dt-at+n=l; trys (t+1); ct+at二0;dt-at+n=0; swap(t, j);void main() int i; printfc'請(qǐng)輸入問題規(guī)模：“); seanf (%d, &n); for(i=l;i二n;i+) ai=i;for (i=l;i二n;i+) ci=0;cn+i二0; di二 0;dn+i二0; trys(l);printf(ns二dn，s);圖3-6哎%爭(zhēng)幺吉本次試驗(yàn)