10122157项镇敏实验6跳马问题ok.doc

算法设计与分析实验实验报告实验指导教师 沈云付 学生姓名 项镇敏 学号 10122157 序号 1 实验时间 周三7-9节课 上海大学计算机工程与科学学院2016年11月3日实验六、跳马问题问题描述： 给定8*8方格棋盘，实验目的：求棋盘上一只马从一个位置到达另一位置的最短路径长。算法思想：1简单分析，说明原理或方法 依旧是最短路径问题，不过此问题用回溯法来求解释比较好的。如下： 一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是：(2,1)、(2,-1)、(1,2)、(1,-2)、(-2,1)、(-2,-1)、(-1,2)、(-1,-2)。从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位置算法复杂度分析： 在任何时刻，回溯算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。2给出能正确运行的程序：程序代码见附录。以下是输入输出要求以及实验结果截图：输入要求：输入有若干测试数据。每组测试数据仅1行，每行上有2个方格pos1、pos2，之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母（a-h）及表示行的一个数字（1-8）构成，如“d7”表示第4列第7行。输出要求：对输入中每行上的2个方格pos1、pos2，输出马从位置pos1跳到pos2所需的最短路径长。如“a1=a2: 3 moves”表示从位置a1跳到a2所需的最少步数是3。注意：按输出样例所示格式输出，如“a1=a2: 3 moves”中冒号后有一个空格，再跟着所需的最少步数。实验结果实验报告要求: 3设计、调试中的问题及实验体会。 回溯法，我们要知道回溯法的基本思想，以及生成问题的基本方法。在一般情况下，用递归回溯法求解问题比较好。附录：#includeusing namespace std;class stackprivate:int a100,b100;int posx;public:stack():posx(0)void push(int x,int y)aposx=x;bposx=y;posx+;void pop(int &x,int &y)posx-;x=aposx;y=bposx;bool empty()if(posx=0)return true;elsereturn false;void jump(int row,int col,int a88)int r,c;arowcol=0;r=row;c=col;stack st;st.push(r,c);while(!st.empty() st.pop(r,c);/左上角if(r0 & c1 & ar-1c-2=-1)ar-1c-2=arc+1;st.push(r-1,c-2);else if(r0 & c1 & ar-1c-2arc+1)ar-1c-2=arc+1;st.push(r-1,c-2);if(r1 & c0 & ar-2c-1=-1)ar-2c-1=arc+1;st.push(r-2,c-1);else if(r1 & c0 & ar-2c-1arc+1)ar-2c-1=arc+1;st.push(r-2,c-1);/右上角if(r0 & c0 & carc+1)ar-1c+2=arc+1;st.push(r-1,c+2);if(r1 & c1 & carc+1)ar-2c+1=arc+1;st.push(r-2,c+1);/左下角if(r0 & ar+2c-1=-1)ar+2c-1=arc+1;st.push(r+2,c-1);else if(r0 & ar+2c-1arc+1)ar+2c-1=arc+1;st.push(r+2,c-1);if(r1 & ar+1c-2=-1)ar+1c-2=arc+1;st.push(r+1,c-2);else if(r1 & ar+1c-2arc+1)ar+1c-2=arc+1;st.push(r+1,c-2);/右下角if(r6 & c7 & ar+2c+1=-1)ar+2c+1=arc+1;st.push(r+2,c+1);else if(r6 & carc+1)ar+2c+1=arc+1;st.push(r+2,c+1);if(r7 & c6 & ar+1c+2=-1)ar+1c+2=arc+1;st.push(r+1,c+2);else if(r7 & carc+1)ar+1c+2=arc+1;st.push(r+1,c+2);int main()int x,y;char a,b;while(cinax)cinby;int s88;int i,j;for(i=0;i8;i+)for(j=