馬踏棋盤-實驗報告

游戲算法實踐實訓(xùn)報告姓名專業(yè)班級指導(dǎo)教師2014年1月16日TOC\o"1-1"\h\u5406一．需求分析 題目：需求分析用8x8的棋盤order[8][8]模擬國際象棋，其中的格子存放馬的位子，馬按走棋規(guī)則進行移動。每個方格只進去一次，走遍棋盤上全部的64個方格。用非遞歸的程序，求得馬的行走路線，將數(shù)字1,2,…64依次填入order[8][8]數(shù)組。每次在多個可走位置中選擇其中一個進行試探，每次選擇位置的“最佳策略”，即可走位置最少的作為下一個試探位置。這樣可以減少回溯次數(shù)。其余未曾試探過的可走位置用棧管理，以備試探失敗時的“回溯”使用。演示程序以用戶與計算機的對話方式執(zhí)行，用戶輸入馬初始的位置（i,j），輸出結(jié)果顯示在其后，即為馬的行走路線。測試數(shù)據(jù)：(1)馬的初始位置（i,j）為：23馬的初始位置（i,j）為：11馬的初始位置（i,j）為：14馬的初始位置（i,j）為：57概要設(shè)計為實現(xiàn)上述程序功能，需要順序棧。順序棧的抽象數(shù)據(jù)類型定義為：ADTSqStack{數(shù)據(jù)對象：D={ai|ai∈Pos,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：intInitStack(SqStack&S)操作結(jié)果：構(gòu)造一個空棧SintStackEmpty(SqStackS)操作結(jié)果：若棧S為空棧，則返回1，否則返回0intPush(SqStack&S,PosTypee)操作結(jié)果：插入元素e為新的棧頂元素intPop(SqStack&S,PosType&e)操作結(jié)果：插入元素e為新的棧頂元素}本程序中包括的四個基本模塊：主程序模塊：Voidmain(){初始化；求解行走路線；//ChessBoardPath(b,start);}棧模塊：實現(xiàn)順序棧的抽象數(shù)據(jù)結(jié)構(gòu)求下一位置模塊：用最優(yōu)策略求下一個探測位置求棋盤行走路線模塊：do{若當(dāng)前位置可通，則{ 將當(dāng)前位置納入棧頂；并將b[i][j]相應(yīng)位置的值置為當(dāng)前編號；若當(dāng)前位置的編號為64，則結(jié)束；否則切換當(dāng)前位置的最優(yōu)探測方向作為新的當(dāng)前位置；}否則{若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為下一個最優(yōu)位置；若棧不空且棧頂位置的四周均不可走，則{b[i][j]相應(yīng)位置的值置為0；刪去棧頂位置；若棧不空，則重新測試新的棧頂位置，直到找到下一個可走位置或出棧至?？?；}}}while(棧不空)；詳細設(shè)計棋盤坐標(biāo)結(jié)點類型、棧的結(jié)構(gòu)體structPoint{intx;inty;intfrom;};//棋盤坐標(biāo)位置類型structStack{Point*top;Point*base;intlength;};//順序棧用順序棧保存走過的路徑，基本操作函數(shù)如下：boolInitstack(Stack&s){//構(gòu)造一個空棧Ss.base=(Point*)malloc(STACKSIZE*sizeof(Point));if(!s.base)returnfalse;s.length=STACKSIZE;s.top=s.base;returntrue;}boolPush(Stack&s,Pointe){//插入元素e為新的棧頂元素if(s.top-s.base>=s.length){s.base=(Point*)realloc(s.base,(s.length+STACKINCREASE)*sizeof(Point));if(!s.base)returnfalse;s.length+=STACKINCREASE;s.top=s.base+s.length;}(*s.top).x=e.x;(*s.top).y=e.y;(*s.top).from=e.from;s.top++;returntrue;}boolPop(Stack&s,Point&e){//若棧不為空，則刪除S的棧頂元素if(s.top==s.base)returnfalse;e.x=(*--s.top).x;e.y=(*s.top).y;e.from=(*s.top).from;returntrue;}voidDestroyStack(Stack&s){//銷毀棧S，S不在存在free(s.base);}boolStackEmpty(StackS){//若棧S為空棧，則返回ture；否則返回falseif(S.base==S.top)returntrue;elsereturnfalse;}boolGetTop(StackS,Point&e){//若棧不為空，則取棧頂元素if(StackEmpty(S))returnfalse;else{e.x=(*(S.top-1)).x;e.y=(*(S.top-1)).y;e.from=(*(S.top-1)).from;returntrue;}}intGetDeep(StackS){//取棧的深度return(S.top-S.base);}關(guān)于行走路徑的其他函數(shù)：voidSetRound(Pointcur){//查找所在位置的所有可走位置的坐標(biāo)，將其賦給指針g_round[8]g_round[8];Pointround[]={cur.x-2,cur.y+1,0,cur.x-1,cur.y+2,0,cur.x+1,cur.y+2,0,cur.x+2,cur.y+1,0,cur.x+2,cur.y-1,0,cur.x+1,cur.y-2,0,cur.x-1,cur.y-2,0,cur.x-2,cur.y-1,0,};for(inti=0;i<8;i++){g_round[i].x=round[i].x;g_round[i].y=round[i].y;}}求解馬的行走路線boolGetRound(inti,Point&pt){//將所在位置周圍所有八個位置坐標(biāo)賦予指針變量pt，并判斷其合理性pt.x=g_round[i-1].x;pt.y=g_round[i-1].y;if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)//判斷其合理性returnfalse;elsereturntrue;}主函數(shù)：voidmain(){ints=1;charyn;while(s){intorder[8][8]={0};//初始化intcount=0;//計數(shù)器，記錄的是第幾步棋Pointbegin; cout<<"請輸入馬在棋盤上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8；例如47]:";cin>>begin.x>>begin.y;cout<<endl;begin.from=0;while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){cout<<"輸入有誤!請重新輸入"<<endl;cout<<endl;cout<<"請輸入馬在棋盤上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8;例如47]:";cin>>begin.x>>begin.y;cout<<endl;}begin.x--;//實際下標(biāo)是0~7，begin.y--;StackhorseVisit;Pointcur,next;Initstack(horseVisit);Push(horseVisit,begin);//首位置進棧order[begin.x][begin.y]=++count;//計數(shù)器+1while(count<64){//其余63步棋的走法 GetTop(horseVisit,cur);SetRound(cur);boolflag=false;for(inti=cur.from+1;i<=8;i++){//按照逆時針的優(yōu)先規(guī)則，選出下一個可用的新位置if(GetRound(i,next)&&order[next.x][next.y]==0){//可用位置未曾使用，則進棧，計數(shù)器加1flag=true;order[next.x][next.y]=++count;Pop(horseVisit,cur);cur.from=i;Push(horseVisit,cur);next.from=0;Push(horseVisit,next);break;}}if(!flag){//如果當(dāng)前位置周圍沒有路徑，則退棧，直至退到存在有最佳位置的坐標(biāo)intj=0,p;if(begin.x==2&&begin.y==6)p=4;elsep=5;while(j<p&&GetDeep(horseVisit)>1){Pop(horseVisit,cur);order[cur.x][cur.y]=0;count--;j++;}}}DestroyStack(horseVisit);//完成后銷毀棧cout<<"棋盤表示:"<<endl;cout<<"12345678"<<endl;for(inti=0;i<8;i++){//輸出order數(shù)組，數(shù)組上數(shù)值為路徑cout<<setw(12)<<i+1<<setw(2)<<"";for(intj=0;j<8;j++){cout<<resetiosflags(ios::right)<<setw(2)<<order[i][j]<<"";}cout<<endl;} cout<<endl;cout<<"謝謝使用！"<<endl;}}主函數(shù)的流程圖：輸入馬在棋盤上的初始位置（i,j）輸入馬在棋盤上的初始位置（i,j）判定輸入是否符合條件0<(i,j)<9?判定輸入是否符合條件0<(i,j)<9?否是把i,j的值賦給內(nèi)部指針變量begin.x,begin.y把i,j的值賦給內(nèi)部指針變量begin.x,begin.y尋找下一步可走位置的坐標(biāo)賦給指針g_round[8]尋找下一步可走位置的坐標(biāo)賦給指針g_round[8]否是否還有別的路可走？是否還有別的路可走？使用最優(yōu)算法選擇下一步（這里采用逆時針優(yōu)先原則）使用最優(yōu)算法選擇下一步（這里采用逆時針優(yōu)先原則）是判斷下一步是否在棋盤上？判斷下一步是否在棋盤上？否是更新馬在棋盤上的位置（i,j）更新馬在棋盤上的位置（i,j）count=count+1count=>64?count=>64?否是逐行打印棋盤逐行打印棋盤調(diào)試分析這個程序剛開始寫的時候，在處理如何選擇下一步的做法上，我沒有用“最優(yōu)”策略，即找下個位子可走次數(shù)最少的，而是簡單的將8個位子一個一個探測，結(jié)果程序在短時間內(nèi)運行不出來，開始我不知道是因為算法效率低的緣故，以為是自己寫錯了，然后修改了算法，輸出了結(jié)果，但是這時候并沒有用最優(yōu)處理，測試了很多數(shù)據(jù)都發(fā)現(xiàn)不出錯誤，最后再分析后發(fā)現(xiàn)寫的算法有問題，根據(jù)問題測試出了錯誤。后來自己又用最優(yōu)策略去改寫，主要是改寫了原來的求下一步的函數(shù)PosTypeNextPos(PosTypepos)，通過計算下一個方向的可走位置次數(shù)，把最小的方向作為最優(yōu)策略，即為下一步。通過改寫，減少了回溯次數(shù)，算法的效率得到了很大的提高。在求路徑的算法里，主要參考了迷宮的思路，也是程序的核心算法，即當(dāng)前位置可走，馬行走此位置，記錄信息，并探測下一位置，采取最優(yōu)策略，即下一個方向的可走位置數(shù)最小的作為下一位置。若當(dāng)前位置不可走，則退棧，找相鄰的下一位置。直至走遍64個格子。但在處理尚有其他方向未被探索時，直接用了求下一步，有重復(fù)計算的現(xiàn)象，這是程序要改進的地方。用戶手冊本程序的運行環(huán)境為windows操作系統(tǒng)，執(zhí)行文件名為：實訓(xùn)項目_馬踏棋盤.exe運行程序后，需要根據(jù)提示輸入馬的初始位置(i,j)的值，其中1≤i,j≤8按回車鍵即可得到測試結(jié)果。數(shù)字標(biāo)號即代表馬在棋盤上的行走順序。本程序的輸入輸出可以無線循環(huán)，可以重復(fù)輸入。測試結(jié)果第一組數(shù)據(jù)測試結(jié)果：第二組數(shù)據(jù)測試結(jié)果：第三組數(shù)據(jù)測試結(jié)果：第四組數(shù)據(jù)測試結(jié)果：程序清單stack.h//棧的定義頭文件stack.cpp//棧的定義Horsevisit.cpp//馬踏棋盤的實現(xiàn)程序八．小結(jié)體會一、這次課程設(shè)計的心得體會通過實踐我的收獲如下：1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。3、通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。4、通過課程設(shè)計，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。二、根據(jù)我在實習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點：1、認(rèn)真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴(yán)密。3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。九．參考文獻[1]嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）——北京：清華大學(xué)出版社，[2]（c++版）——電子工業(yè)出版社[3]王紅梅，胡明，王濤，數(shù)據(jù)結(jié)構(gòu)（c++版）——北京：清華大學(xué)出版社，2005[4]網(wǎng)上搜索相關(guān)程序作為參考(如棧類型的定義等）附錄//stack.h#include<malloc.h>#ifndefSTACK_H#defineSTACK_HstructPoint{intx;inty;intfrom;};#defineSTACKSIZE70#defineSTACKINCREASE10structStack{Point*top;Point*base;intlength;};boolInitstack(Stack&s);boolPush(Stack&s,Pointe);boolPop(Stack&s,Point&e);voidDestroyStack(Stack&s);boolStackEmpty(StackS);boolGetTop(StackS,Point&e);intGetDeep(StackS);#endif//stack.cpp#include"stack.h"boolInitstack(Stack&s){//構(gòu)造一個空棧Ss.base=(Point*)malloc(STACKSIZE*sizeof(Point));if(!s.base)returnfalse;s.length=STACKSIZE;s.top=s.base;returntrue;}boolPush(Stack&s,Pointe){//插入元素e為新的棧頂元素if(s.top-s.base>=s.length){s.base=(Point*)realloc(s.base,(s.length+STACKINCREASE)*sizeof(Point));if(!s.base)returnfalse;s.length+=STACKINCREASE;s.top=s.base+s.length;}(*s.top).x=e.x;(*s.top).y=e.y;(*s.top).from=e.from;s.top++;returntrue;}boolPop(Stack&s,Point&e){//若棧不為空，則刪除S的棧頂元素if(s.top==s.base)returnfalse;e.x=(*--s.top).x;e.y=(*s.top).y;e.from=(*s.top).from;returntrue;}voidDestroyStack(Stack&s){//銷毀棧S，S不在存在free(s.base);}boolStackEmpty(StackS){//若棧S為空棧，則返回ture；否則返回falseif(S.base==S.top)returntrue;elsereturnfalse;}boolGetTop(StackS,Point&e){//若棧不為空，則取棧頂元素if(StackEmpty(S))returnfalse;else{e.x=(*(S.top-1)).x;e.y=(*(S.top-1)).y;e.from=(*(S.top-1)).from;returntrue;}}intGetDeep(StackS){//取棧的深度return(S.top-S.base);}//horsevisit.cpp/*SourceFiles/HorseVisit.cpp*/#include<iostream>#include"stack.h"#include<iomanip>usingnamespacestd;Pointg_round[8]={0,0,0};voidSetRound(Pointcur){//查找所在位置的所有可走位置的坐標(biāo)，將其賦給指針g_round[8]g_round[8];Pointround[]={cur.x-2,cur.y+1,0,cur.x-1,cur.y+2,0,cur.x+1,cur.y+2,0,cur.x+2,cur.y+1,0,cur.x+2,cur.y-1,0,cur.x+1,cur.y-2,0,cur.x-1,cur.y-2,0,cur.x-2,cur.y-1,0,};for(inti=0;i<8;i++){g_round[i].x=round[i].x;g_round[i].y=round[i].y;}}boolGetRound(inti,Point&pt){//將所在位置周圍所有八個位置坐標(biāo)賦予指針變量pt，并判斷其合理性pt.x=g_round[i-1].x;pt.y=g_round[i-1].y;if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)//判斷其合理性returnfalse;elsereturntrue;}voidmain(){ints=1;charyn;while(s){intorder[8][8]={0};//初始化intcount=0;//計數(shù)器，記錄的是第幾步棋Pointbegin; cout<<"請輸入馬在棋盤上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8；例如47]:";cin>>begin.x>>begin.y;cout<<endl;begin.from=0;while(begin.x>8||begin.x<1||begin.y>8||begin.y<1){cout<<"輸入有誤!請重新輸入"<<endl;cout<<endl;cout<<"請輸入馬在棋盤上的初始位置x和y。"<<endl;cout<<"[其中1≤x≤8且1≤y≤8;例如47]:";cin>>begin.x>>begin.y;cout<<endl;}begin.x--;//實際下標(biāo)是0~7，begin.y--;StackhorseVisit;Pointcur,next;Initstack(horseVisit);Push(horseVisit,begin);//首位置進棧order[begin.x][begin.y]=++count;//計數(shù)器+1while(count<64){//其余63步棋的走法 GetTop(horseVisit,cur);SetRound(cur);boolflag=false;for(inti=cur