分享
 
 
 

马踏棋盘演示程序的设计

王朝other·作者佚名  2006-01-31
窄屏简体版  字體: |||超大  

马踏棋盘演示程序设计题目:马踏棋盘班级:02级计算机2班 姓名:刘晓明 学号:200201020219

完成日期:2004年11月20日

需求分析将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,……,64依次填入一个8×8的方阵,输出之。

测试数据:由读者指定。可自行指定一个马的初始位置(i,j),0<=i,j<=7。

设计思路按照顺时针顺序,每次产生一个新的路点,并验证此路点的可用性,需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用,则入栈,并执行下一步,每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0,则走不下去了,进行回溯。

概要设计程序中使用了菜单式设计,操作的输入输出均有提示。主要文件分为dsoper.h和ui.h。分别负责数据结构操作和用户界面显示。

dsoper.h中的主要函数解释如下:

l void Calc(HorsePoint init)用于计算路程的入口函数

l HorsePoint GetNewPoint(HorsePoint *parent) 从parent节点产生一个新节点,方向按照parent.dir方向递增

l void PushStack(HorsePoint pos)入栈

l void PushStack(HorsePoint pos, int dir)入栈重载函数

l HorsePoint PopStack(void)出栈

l void initial(void) 初始化应用程序各个全局变量

ui.h中的主要函数解释如下:

l HorsePoint GetInitPoint(void) 请求输入马的初始位置

l CmdChar GetCommand(void) 显示菜单,并从其中获取菜单命令

l void ShowTable(void) 按照棋盘模型显示输出数据

l void ShowStep(void) 按照步进模型显示输出数据

l void SaveToFile(void) 保存到文件rt.txt中

数据结构定义:

typedef struct horsepoint

{

int x;

int y;

int dir; //下一步的走向,初始化-1,有效0-7

}HorsePoint;

其中dir分量用于指示相对于当前路点的下一路点方向,

全局变量定义:

bool Board[WIDTH][WIDTH] 定义棋盘中各点是否已经走过,未走为false

HorsePoint Path[MAX_LEN] 定义马的行走路径

int scount已经进入路径栈的元素个数

程序源代码文件main.cpp

/*

Name: main.cpp

Copyright: Copyright@1999-2004, Gashero Liu.

Author: Gashero Liu.

Date: 16-11-04 20:41

Description: 程序主文件,仅含main函数

*/

#include <iostream>

#include <stdlib.h>

#ifndef DATASTRUCT_H

#define DATASTRUCT_H

#include "datastruct.h"

#endif

#ifndef DSOPER_H

#define DSOPER_H

#include "dsoper.h"

#endif

#ifndef UI_H

#define UI_H

#include "ui.h"

#endif

using namespace std;

//--------------------------------全局变量定义 ---------------------------------

bool Board[WIDTH][WIDTH]; //定义棋盘中各点是否已经走过,未走false

HorsePoint Path[MAX_LEN]; //定义马的行走路径

int scount; //已经进入路径栈的元素个数

int main(int argc, char *argv[])

{

CmdChar cmd; //命令字符

HorsePoint init;//马的初始位置

initial();

while((cmd=GetCommand())!=CMD_EXIT)

{

switch(cmd)

{

case CMD_NEW:

{

init=GetInitPoint();

Calc(init);

break;

}

case CMD_TABLE:

{

ShowTable();

break;

}

case CMD_STEP:

{

ShowStep();

break;

}

case CMD_SAVE:

{

SaveToFile();

break;

}

}

}

//system("PAUSE");

return 0;

}

文件dsoper.h:

/*

Name: dsoper.h

Copyright: Copyright@1999-2004, Gashero Liu.

Author: Gashero Liu.

Date: 16-11-04 12:48

Description: 数据结构的操作,包含栈和队列的操作

*/

#ifndef DATASTRUCT_H

#define DATASTRUCT_H

#include "datastruct.h"

#endif

//引用全局变量

extern bool Board[WIDTH][WIDTH];

extern HorsePoint Path[MAX_LEN];

extern int scount;

//结束引用全局变量

//---------------------------------function declaration-------------------------

void Calc(HorsePoint init);

/*计算路程的入口函数*/

HorsePoint GetNewPoint(HorsePoint *parent);

/*从parent节点产生一个新节点,方向按照parent.dir方向递增,如果无法产生新的

结点,则parent.dir==-1*/

void PushStack(HorsePoint pos);

void PushStack(HorsePoint pos, int dir);

/*结点pos入栈Path,入栈后scount++;相应Board对应点=true*/

HorsePoint PopStack(void);

/*给栈Path,出栈一个元素,并返回,scount--,对应点Board=false;*/

void initial(void);

/*初始化应用程序各个全局变量*/

//---------------------------------function defination--------------------------

void Calc(HorsePoint init) //-----------------------------------------------

{

int oc=0,wc=0;

HorsePoint npos; //下一结点

HorsePoint *ppos; //当前结点

initial();

ppos=&init;

PushStack(*ppos);

while(!(scount==0 || scount==MAX_LEN))

{

oc++;

if(oc==100000000)

{

oc=0;

wc++;

printf("已执行%d亿次,入栈深度%d\n",wc,scount);

//system("PAUSE");

}

ppos=&Path[scount-1];

npos=GetNewPoint(ppos);

if(ppos->dir!=INVALID_DIR)

{

PushStack(npos,ppos->dir);//产生了一个有效的下步结点,入栈

//printf("PushStack: (%d,%d),last.dir:%d,scount=%d\n",npos.x,npos.y,ppos->dir,scount);

//system("pause");

}

else

{

PopStack();//没有有效的下步结点,出栈

//printf("PopStack : scount:%d\n",scount);

}

//system("pause");

}

printf("共%亿零%d次,Scount:%d\n",wc,oc,scount);

}

HorsePoint GetNewPoint(HorsePoint *parent) //----------------------------------

{

int i;

HorsePoint newpoint;

int tryx[MAX_DIR]={ 1, 2, 2, 1,-1,-2,-2,-1};

int tryy[MAX_DIR]={-2,-1, 1, 2, 2, 1,-1,-2};

newpoint.dir=INVALID_DIR;

parent->dir=parent->dir+1;

for(i=parent->dir;i<MAX_DIR;i++)

{

newpoint.x=parent->x+tryx[i];

newpoint.y=parent->y+tryy[i];

if(newpoint.x<WIDTH && newpoint.x>=0 &&

newpoint.y<WIDTH && newpoint.y>=0 &&

Board[newpoint.x][newpoint.y]==false)

{

parent->dir=i;

//Board[newpoint.x][newpoint.y]=true;

return newpoint;

}

}

parent->dir=INVALID_DIR;//没有有效的下一步方向

return newpoint;//返回一个无关紧要的值

}

void PushStack(HorsePoint pos) //------------------------------------------

{

Board[pos.x][pos.y]=true;

Path[scount]=pos;

scount++;

}

void PushStack(HorsePoint pos, int dir) //-------------------------------------

{

Path[scount-1].dir=dir;

PushStack(pos);

}

HorsePoint PopStack(void) //--------------------------------------------------

{

//std::cout << "PopStack" << std::endl;

HorsePoint pos;

scount--;

pos=Path[scount];

Board[pos.x][pos.y]=false;

Path[scount].dir=INVALID_DIR;

return pos;

}

void initial(void) //--------------------------------------------------------

{

int i,j;

for(i=0;i<WIDTH;i++)

{

for(j=0;j<WIDTH;j++)

{

Board[i][j]=false;

}

}

for(i=0;i<MAX_LEN;i++)

{

Path[i].x=0;

Path[i].y=0;

Path[i].dir=INVALID_DIR;

}

scount=0;

}

文件ui.h:

/*

Name: ui.h

Copyright: Copyright@1999-2004, Gashero Liu.

Author: Gashero Liu.

Date: 16-11-04 12:54

Description: 用户交互操作头文件,另含文件存取

*/

#include <conio.h>

#ifndef DATASTRUCT_H

#define DATASTRUCT_H

#include "datastruct.h"

#endif

//引用全局变量

extern bool Board[WIDTH][WIDTH];

extern HorsePoint Path[MAX_LEN];

extern int scount;

//结束引用全局变量

//-----------------------function declaretion-----------------------------------

HorsePoint GetInitPoint(void);

/*请求输入马的初始位置*/

CmdChar GetCommand(void);

/*显示菜单,并从其中获取菜单命令*/

void ShowTable(void);

/*按照棋盘模型显示输出数据*/

void ShowStep(void);

/*按照步进模型显示输出数据*/

void SaveToFile(void);

/*保存到文件rt.txt中*/

//---------------------------------function defination--------------------------

HorsePoint GetInitPoint(void) //----------------------------------------------

{

HorsePoint pos;

do

{

for(int i=0;i<24;i++)

{

printf("\n");//产生24个换行符来屏蔽上一页的信息

}

printf("\t\t\t\t请输入马的初始位置x,y:");

scanf("%d,%d",&pos.x,&pos.y);

}while(pos.x>=WIDTH || pos.y>=WIDTH ||

pos.x<0 || pos.y<0);

pos.dir=INVALID_DIR;

return pos;

}

CmdChar GetCommand(void) //----------------------------------------------------

{

char cmd;

while(true)

{

printf("\n\n\n\n");

printf("\t\t\t\t马走棋盘演示程序\n");

printf("\t\t\t\t 版本:v1.2\n\n");

printf("\t\t\t\t [n]新游戏\n");

printf("\t\t\t\t [t]输出棋盘模型\n");

printf("\t\t\t\t [s]步进输出\n");

printf("\t\t\t\t [f]保存至文件rt.txt\n");

printf("\t\t\t\t [x]退出\n");

printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n");

/*使用n多个换行符来刷屏,因为我找不到可以跨平台的清屏函数*/

cmd=getch();

switch(cmd)

{

case 'n':

{

return CMD_NEW; //开始新游戏

break;

}

case 't':

{

return CMD_TABLE; //输出棋盘模型

break;

}

case 's':

{

return CMD_STEP; //输出步进模型

break;

}

case 'f':

{

return CMD_SAVE; //保存至文本文件rt.txt

break;

}

case 'x':

{

return CMD_EXIT; //退出本程序

break;

}

default:

{

cmd='\0';

continue;

}

}

}

}

void ShowTable(void) //--------------------------------------------------------

{

int ft[WIDTH][WIDTH];

int step=0;

HorsePoint pos;

if(scount==MAX_LEN)

{

for(int i=0;i<MAX_LEN;i++)

{

step++;

pos=Path[i];

ft[pos.x][pos.y]=step;

}

for(int i=0;i<WIDTH;i++)

{

printf("\t\t\t\t");

for(int j=0;j<WIDTH;j++)

{

if(ft[i][j]<10)

{

printf(" ");//输出一个空格来保持对齐

}

printf("%d ",ft[i][j]);

}

printf("\n");

}

printf("\n\n\n\n\n\n\n\n");

system("pause");

}

else

{

printf("\t\t\t\t任务未完成或失败,没有有效数据\n");

system("pause");

}

}

void ShowStep(void) //--------------------------------------------------------

{

int ft[WIDTH][WIDTH];

int step=0;

HorsePoint pos;

char cmd;

if(scount==MAX_LEN)

{

for(step=0;step<MAX_LEN;step++)

{

printf("\n\n\n\n\n\n\n\n");

for(int i=0;i<WIDTH;i++)//清除输出数组内容

{

for(int j=0;j<WIDTH;j++)

{

ft[i][j]=0;

}

}

for(int i=0;i<step;i++)//只显示到step步的内容

{

pos=Path[i];

ft[pos.x][pos.y]=i+1;

}

for(int i=0;i<WIDTH;i++)

{

printf("\t\t\t\t");

for(int j=0;j<WIDTH;j++)

{

if(ft[i][j]<10)

{

printf(" ");

}

if(ft[i][j]==0)

{

printf(" ");

}

else

{

printf("%d ",ft[i][j]);

}

}

printf("\n");

}

printf("\n\n\n\n\n\n\n\n\n");

system("pause");

}

printf("\n\n\n\n\n\n\n\n");

system("pause");

}

else

{

printf("\t\t\t\t任务未完成或失败,没有有效数据\n");

system("pause");

}

}

void SaveToFile(void) //------------------------------------------------------

{

int ft[WIDTH][WIDTH];

int step=0;

HorsePoint pos;

FILE *pfile;

if(scount==MAX_LEN)

{

for(int i=0;i<MAX_LEN;i++)//将路径数据转存到棋盘模型中

{

step++;

pos=Path[i];

ft[pos.x][pos.y]=step;

}

if((pfile=fopen(FILE_NAME,"w"))!=NULL)//保存至文件

{

for(int i=0;i<WIDTH;i++)

{

for(int j=0;j<WIDTH;j++)

{

if(ft[i][j]<10)

{

fprintf(pfile," ");//补齐格式用的空格

}

fprintf(pfile,"%d ",ft[i][j]);

}

fprintf(pfile,"\n");

}

fclose(pfile);

system("notepad.exe rt.txt");

}

else

{

printf("\t\t\t\t输出文件打开错误,请检查文件属性和文件系统属性\n");

system("PAUSE");

}

}

else

{

printf("\t\t\t\t任务未完成或失败,没有有效数据\n");

system("PAUSE");

}

}

文件datastruct.h:

/*

Name: datastruct.h

Copyright: Copyright@1999-2004, Gashero Liu.

Author: Gashero Liu.

Date: 16-11-04 12:25

Description: 数据结构的定义头文件

*/

typedef struct horsepoint

{

int x;

int y;

int dir; //下一步的走向,初始化-1,有效0-7

}HorsePoint;

typedef enum cmdchar

{

CMD_NEW, /*输入一个新的初始坐标点*/

CMD_TABLE, /*输出棋盘模型*/

CMD_STEP, /*输出步进模型*/

CMD_SAVE, /*保存至文件*/

CMD_EXIT, /*退出程序*/

}CmdChar;

#define WIDTH 8

#define MAX_LEN 64

#define MAX_DIR 8

#define INVALID_DIR -1

#define FILE_NAME "rt.txt"

调试分析程序中的指针操作多次出现错误,尤其发生在操作栈中的方向分量时,由于操作的失误,开始实际未保存此数据,导致第47次循环需要回溯时进入死循环。后改用Visual Studio 2003中VC++.net中的调试工具发现栈内的所有dir分量值均为-1。后改正即可。因为这个问题,我重写了一次整个程序。

用户手册首页菜单选项,按下中括号内的字符即可进入相关功能。需要输入数据后方可按照3中形式输出数据,输入数据格式为2个数字使用逗号分隔。

棋盘输出为一次完全输出整个棋盘信息。

步进输出每次仅前进一步,之后按下任意键前进。

保存至文件rt.txt则将结果存入可行性文件所在目录下的rt.txt文件内,并同时开启记事本显示保存文件内容。

按下x键退出程序

测试结果经测试有些路点的数据计算量极大,其中(4,4)点使用AMD1.2GhzCPU计算了2个多小时,完成了850亿个有效路点的入栈尝试仍然没有算出结果。我也因为数据的问题而三次重写整个程序。所以推荐使用如下测试数据。有效入栈次数超过10亿次的数据均略掉(计算时间将超过5分钟)。数据后为实测的有效入栈次数:

初始坐标点

有效路点入栈次数

0,0

6,484,065

0,3

18,305,907

0,7

16,501,401

2,3

217,047,959

2,4

4,504,281

7,0

503,650,751

7,7

54,482,161

(在此仅列出x=0,1,2的全部数据和另外两个数据)

附录虽说同学们的作业来源广泛,但希望老师相信这份是我自己写的。整个程序的开发经历了v1.0,v1,1,v1,2三个版本。如上的代码是v1.2版本。经过后来的测试证明v1.1版本(使用C语言)没有错误,可以正确执行,只怪我一开始选错了一直使用的数据(4,4)。漫长的计算导致我错以为进入了一个周期非常大的死循环。

在这三个版本的开发过程中,我使用了Dev-C++5,Visual C++.net2003,GNU gcc3.3.0三个版本两个平台的编译器和IDE。我也为此付出了约20个小时的时间。回头看来付出还是值得的,程序源码总量达到了470余行,是我至今写的最长的C程序(其他语言不计)。而如此高的计算量也让我开始考虑程序的时间复杂性问题了。程序中用户界面的刷屏设计也用到了我以前一次课设的经验,实际证明即实现了全屏幕显示,又有非常完美的跨平台性能(Windows XP / GNU Linux)。

在版本v1.2中实际上是使用了面向过程的C++语言写成的,标准参考了ISO C++98标准,因此代码在Dev-C++中书写,而移植到VC++.net和gcc时,没有修改任何一句代码。由此可见标准在跨平台开发方面的优越性。但后来实际证明在基于Win32,.net,Linux Kernel三种平台中实际运算速度几乎没有差异,而将程序运行于Pentium2.4Ghz平台运行时速度提高也很小(1.4亿次/分钟,1.7亿次/分钟)。

版本v1.0开发过程中间隔时间过长,以致忘记了开发思路,所以没有完成就放弃了,现在可以到我的个人站点下载v1.1和v1.2的源代码和可执行文件。v1.1版本只提供Dev-C++编译下的符合ISO C99标准的代码和基于Win32平台的二进制源码。V1.2版本使用ISO C++98标准书写,二进制版本提供Win32平台的Dev-C++编译版本和.net Framework1.1平台下的VC++.net编译版本。对于Linux平台,可自行复制源码编译,再次不提供。

源码下载地址:http://e5022.wx-e.com/sourcecode/index.htm

E-mail: gashero@163.com

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有