马踏棋盘的实习报告

马踏棋盘实习报告题目：设计一个国际象棋的马踏遍棋盘的演示程序班级：姓名：学号：完成日期：需求分析将马随机放在m*n棋盘Board[m][n]的某个方格中，马按国际象棋行棋的规则进行移动。要求每个方格只行走一次，走遍棋盘上全部m*n个方格。编写非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,.m*n依次填入-一个m*n的方阵中。程序要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。二．概要设计棋盘可用二维数组表示，马踏棋盘问题可采用回溯法解题。当马位于棋盘某-位置时，它有唯一坐标，根据国际象棋的规则，它67有8个方向可跳，对每一方向逐探测，从中选择可行方向继续行棋，每一行棋坐标借助栈记录。若8个方向均不可行则借助栈回溯，在前一位置选择下一可行方向继续行棋，直至跳足m*n步，此时成功的走步记录在栈中。或不断回湖直至栈空失败。关于栈的抽象数据类型定义:ADTList{数据对象：D={ailai∈ElemType，i=1，2，…，n，n≥0}数据关系：R1={<ai-1，ai>|ai∈D,i=2，…，n}基本操作：InitStack(Stack&s);操作结果：栈的初始化DestoryStrack(&s)操作结果：栈结构销毁GetTop(Stacks,SElemType&e);操作结果：若栈不空，则用e返回s的栈顶元素，返回OK；否则返回ERRORPushStack(&s,SElemTypee);操作结果：插入元素e为新的栈顶元素PopStack(&s,SElemType&e);操作结果：若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERRORStackEmpty(s)操作结果：判断栈是否为空}本程序包含以下模块：主程序模块：voidmain(){定义变量；接受命令；处理命令；退出；}起始坐标函数模块——马儿在棋盘上的起始位置；搜索路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；输出路径函数模块——输出马儿行走的路径模块调用关系：输出路径模块搜索坐标模块起始坐标模块主模块 输出路径模块搜索坐标模块起始坐标模块主模块函数调用关系：详细设计#include<stdio.h>#include<stdlib.h>#defineOK1#defineTRUE1#defineERROR0#defineFALSE0#defineM8#defineN8intdirection[2][9]={{0,-2,-1,1,2,2,1,-1,-2},{0,1,2,2,1,-1,-2,-2,-1}};//增量数组intpow[M][N];intcheck[M][N],next[M][N];//创建棋盘，初始为0structElement//数据域{intx,y;//x行,y列intd;//下一步的方向};typedefstructLStack//链栈{Elementdata;structLStack*next;}*PLStack;typedefstructcheck//定义棋盘内点的坐标{intx;inty;}Check;/*************栈函数****************/intInitStack(PLStack&S)//构造空栈{S=NULL;returnOK;}intStackEmpty(PLStackS)//判断栈是否为空{if(S==NULL)returnOK;elsereturnFALSE;}intPush(PLStack&S,Elemente)//元素入栈{PLStackp;p=(PLStack)malloc(sizeof(LStack));p->data=e;p->next=S;S=p;returnOK;}intPop(PLStack&S,Element&e)//元素出栈{PLStackp;if(!StackEmpty(S)){e=S->data;p=S;S=S->next;free(p);returnOK;}elsereturnFALSE;}/********贪心权值函数********/voidPrintf(intp[M][N]){//打印权值数组 for(inti=0;i<M;i++){ for(intj=0;j<N;j++)printf("%2d",p[i][j]);printf("\n"); }}voidInitWeight(){//创建权值数组并初始化每个位置的权值 for(inti=0;i<M;i++) for(intj=0;j<N;j++)pow[i][j]=0; for(inti=0;i<M;i++){ for(intj=0;j<N;j++){ for(intdir=1;dir<=8;dir++){ intx1=i+direction[0][dir]; inty1=j+direction[1][dir]; if(x1>=0&&x1<=7&&y1>=0&&y1<=7) pow[i][j]++; } } }}voidSetWeight(intx,inty){//位置（x,y）设置为被占用时，修改权值数组,被占用时为9 pow[x][y]=9; for(intdir=1;dir<=8;dir++){ intx1=x+direction[0][dir]; inty1=y+direction[1][dir]; if(x1>=0&&x1<=7&&y1>=0&&y1<=7&&pow[x1][y1]!=9) pow[x1][y1]--; }}voidUnSetWeight(intx,inty){//位置（x,y）设置为未占用时，修改权值数组 for(intdir=1;dir<=8;dir++){ intx1=x+direction[0][dir]; inty1=y+direction[1][dir]; if(x1>=0&&x1<=7&&y1>=0&&y1<=7&&pow[x1][y1]!=9){ pow[x1][y1]++; pow[x][y]++; } }}/*******马踏棋盘函数*******/intStep(Checkstart,PLStack&H){ Elementdata; intx=start.x-1,y=start.y-1;//将输入位置建议，数组从0，0开始存储 inti=1; while(i<=64){check[x][y]=i;//将当前步数写入棋盘数组 SetWeight(x,y);structElementt,data;intpow_min=9; for(intdir=1;dir<=8;dir++){//探测下一步可走的方向 intx1=x+direction[0][dir]; inty1=y+direction[1][dir]; if(x1>=0&&x1<=7&&y1>=0&&y1<=7&&pow[x1][y1]!=9) { if(pow_min>pow[x1][y1])//找出下一步位置中权值最小的 { pow_min=pow[x1][y1]; t.d=dir;//上一步的方向 t.x=x1; t.y=y1; } } } data.x=x;//入栈 data.y=y; data.d=t.d; Push(H,data); x=t.x;//坐标更新 y=t.y; i++;//步数增加 } returnOK;}intmain(){ for(inti=0;i<M;i++)for(intj=0;j<N;j++){check[i][j]=0;next[i][j]=0; } InitWeight(); PLStackH; InitStack(H); Checkstart; printf("请输入起始坐标xy："); scanf("%d%d",&start.x,&start.y); Step(start,H); Printf(check); return0;}四．调试分析1.刚开始的时候并没