资源描述：
《10122157项镇敏实验6跳马问题ok》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法设计与分析实验》实验报告实验指导教师沈云付学生姓名项镇敏学号10122157序号1实验时间上海大学计算机工程与科学学院2016年11月3日实验六、跳马问题问题描述：给定8*8方格棋盘，实验目的：求棋盘上一只马从一个位置到达另一位置的最短路径长。算法思想：1•简单分析，说明原理或方法依旧是最短路径问题，不过此问题用回溯法来求解释比较好的。如下：一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是：(2,1)、(2,-1)、(1,2)>(1，-2)、(-2,1)>(-2,-1)>(-1,2)>(-1,-2)。从中任选择一个方向前进，到达新的位置。在
2、从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置己经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位置……算法复杂度分析：在任何时刻，冋溯算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为0(h(n))。而显式地存储整个解空间则需要0(2h(n))或0(h(n)!)内存空间。2.给岀能正确运行的程序：程序代码见附录。以下是输入输出要求以及实验结果截图：输入要求：输入有若
3、干测试数据。每组测试数据仅1行，每行上有2个方格posl、pos2,之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母(a・h)及表示行的一个数字(1-8)构成，如“d7”表示第4列第7行。输出要求:对输入中每行上的2个方格posl、pos2,输岀马从位置posl跳到pos2所需的最短路径长。如“31=〉ei2:3moves"表示从位置且1跳到£所需的最少步数是3。注意:按输出样例所示格式输出，如“81=>32:3moves"中冒号后有一个空格，再跟着所需的最少步数。实验结果F:OJ61Debug61.exe3.13.2al
4、==>a2:ala3al==>a3:alh8al==>h8:g2b8g2==>b8：3noues2noues6noues5noues实验报告要求：3.设计、调试中的问题及实验体会。回溯法，我们要知道回溯法的基本思想，以及生成问题的基本方法。在一般情况下，用递归回溯法求解问题比较好。附录：#includeusingnamespacestd;classstack{private:inta[100],b[1001;intposx;public:stack():posx(0){}voidpush(intx,inty){afposx]=x;b[p
5、osx]=y;posx++;}voidpop(int&x,int&y){posx—;x=a[posx];y=b[posx];boolempty(){if(posx==0)returntrue;elsereturnfalse;}};voidjump(introw,intcoljnta[8][8]){intr.c;a[row][col]=0;r=row;c=col;stackst;st.push(r,c);while(!st.empty()){st.pop(r,c);〃左上角if(r>0&&c>l&&a[r-l][c-2]==-l){a[r-l][c-2]=a
6、[r][c]+l;st.push(r-l,c-2);}elseif(r>0&&c>l&&a[r-l][c-2]>a[r][c]+l){a[r-l][c-2]=a[r][c]+l;st.push(r-l,c-2);}if(r>l&&c>0&&arr-2][c-l]==-l){a[r-2][c-l]=a[r][c]+l;st.push(r-2,c-l);}elseif(r>l&&c>0&&a[r-2][c-l]>a[r][c]+l){a[r-2][c-l]=a[r][cl+l;st.push(r-2,c-l);〃右上角-(-O7+J)qsnd.-S二+0=」帛
7、〒。=2一e三diIAH+ze电00AO密9乂)七«$«、/"(I+07l)qsnd.ls二+sEf=+o=eAE5+5EeAH+0=ziE多卜V。电电-2)七USR_(-+yeL)qsnd」s二+5EP占+o=eAe三dILI+o=z己」E电电00呀-g」(z+2I」)qsnd.ls二+sEfe7+0=IAe5+sEecCT+0=IAE电电9V0电电0含USR_(e+y.」)£nd」s二+sEfK+o=IAe三die+o=.」」e电応9VO电电0£)七二+O=」PMI+O=e+」H三+5EEA=+O=Z±一E孩9V」)七USQ^+TZ+J)qsnd」s二
8、+see"i+o=z+jh三d"I+o=e+」」e电之§孩9V」)
