算法設(shè)計與分析實驗報告3

《算法設(shè)計與分析實驗報告3》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

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

2、就是從一個小方格沿上、下、左、右四個方向到鄰近的方格，當然不能穿墻。設(shè)迷宮的入口在左上角（1,1）,出口是右下角（8,8）o根據(jù)給定的迷宮，找出一條入口到出口的路徑。0000000001111010000010100100001001011010010000110100100001111110圖3-1迷宮矩形圖#includeintmaze[8][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}};intfx[4]={1,-1,0,0},fy[4]={0,0,-1,1};struct}intx,y,pre;}sq[100];intqh,qe,i,j,k;intcheck(inti,intj);intsearch();voidout();voidmain(){search();}intsearch(){qh=O;qe=l;maze[0][0]=-l;sq[O].pre=O;sq[0].x=0;sq[O].y=O;while(qh!=qe)qh=qh+l;for(k=0;k<=3;k++)i=sq[qh].x+fx[k];j=

4、sq[qh].y+fy[k];if(check(i,j)==l){qe二qe+1;sq[qe].x=i;sq[qe].y=j;sq[qe]

5、

6、i>7

7、[j<0

8、U>7)flag=0;if(maze[i][j]==l

9、

10、maze[i][j]==-l)flag=0;return(flag);}voidout(){cout?n(n?sq[qe].x?,,,,

11、,?sq[qe].y?n)"?endl;while(sq[qe].pre!=0)qe=sq[qe].pre;cout?H-,,?,,("?sq[qe].x?,,；,?sq[qe].y?,,),f?endl;亍wE:VCllllDebuglllLexe,i〔口

12、回

13、■牛g

14、—<6,7〉—〉一一<6.5〉一一<5.5〉一一匕4〉一一03〉--<5,2〉一一<4,2〉一一<3.2〉―<2,2>一一C2.1〉—<2,0>―<1,0>—<0,0>Pressanykeytocontinue.圖3~22、有如圖3-3所示的七巧板，試設(shè)計算法，使用至多4種不同顏色對七巧板進行涂色（每塊涂一

15、種顏色），要求相鄰區(qū)域的顏色互不和同，打印輸出所有可能的涂色方案。#includeintdata[8][8],n=8,color[8],total;voidtrys(ints);intcolorsame(ints);voidoutput();voidmain(){inti,j；for(i=l;i<=7;i++)forG=l;j<=7;j++)scanf(”％d”,&data[i]

16、j]);for(j=l;j<=7;j++)color[j]=0;total=0;trys(l);printf(nTotal=%dn,total);}voidtrys(ints){inti;if

17、(s>7)output();elsefor(i=l;i<=4;i++){color[s]=i;if(colorsame(s)==0)trys(s+l);}}intcolorsame(ints){inti,flag;flag=0;for(i=l;i<=s-l;i++)if(data[i][s]==1&&color[i]==color[s])flag=l;retum(flag);}voidoutput(){int