资源描述：
《马踏棋盘课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、学号：课程设计计算机科学与技术学院题目学院专业班级姓名指导教师马踏棋盘2013年7月4日课程设计任务书学生姓名：专业班级：指导教师：工作单位：物联网工程系题目：马踏棋盘初始条件：设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际彖棋的8X8棋盘Board[8][8]的某个方格中，马按走棋规则（见题集p98）进行移动。耍求每个方格只进入一次，走边棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,3,-,64依次填入一个8X8的方阵，输出之。测试用例见题集p98。要
2、求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明帖撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、问题描述简述题H要解决的问题是什么。2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、经验和体会（包括对算法改进的设想）5、附源程序淸•单和运行结果。源程序耍加注释。如果题忖规定了测试数据，则运行结果耍包含这些测试数据和运行输出，6、设计报告、程序不得相互抄袭和
3、拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第20周（7刀1H至7刀4H）完成。2、7月4日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：年月日系主任（或责任教师）签名：年月日问题描述一、问题设计一个国际象棋的马踏棋盘的演示程序。二基本要求将马随机放在国际象棋8*8的棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,3……・64—次填入一
4、个8*8的方阵输出Z三、测试数据可自行指定一个马的初始位置(i,j),0<=i,j<=7.o四、实现提示一般说来，当马位于位置(i,j)时，可以走到下列8个位置之一(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能位置可以用一维数组Htryl[0---7]和HTry2[0..7]来表示：-2-11221-1-2
5、Htry201234561221-1-2-2-1Htryl23401567位于(i,j)的马可以走到新位置是在棋盘范围内的(i+Htryl[h],j+Htry2[h])，其中h=0,1,-.7五、选作内容:(1)求岀从某一起点岀发的多条至全部行走路线。(2)探讨每次选择位置的“最佳策略”，以减少凹溯的次数。(3)演示寻找行走路线的回溯过程。设计一*问题分析马踏棋盘的演示程序涉及一下儿个方面：1.棋盘的表示2.如何在只进入每个方格一次的情况下确定下一步位置3.当出现“死棋”时如何实现“回溯”(悔棋)4.如何判
6、定已经走遍了棋盘上所有的方格5.如何实现整个行走路线的输出6.效率优化二问题的解决方案1.棋盘用二维数组board[8][8]表示，其中board[i][j]=0,表示第i行、第j列的方格尚未被访问;board[i][j]=l,表示第i行、第j列的方格已经被访问过了。2.由提示知：当马位于位置(i,j)时，可以走到下列8个位置乙一(i—2,j+1),(i—l,j+2),(i+1,j+2),(i+2,j+1),(i+2,j—l),(i+1,j—2),(i-1,j-2),(i-2,j-1)因此HTry[d]表示
7、下一步可能走位置。再由判定函数intcheck(intx,inty)和数组board[8][8]判定该位置是否合法(既在8*8的棋盘内，而且未被访问过)。3.利用栈“后进先出”的特点实现对每一步棋的记录，当出现死棋时通过出栈操作实现“回溯”。4.用变量step实现对走棋次数的记录，每走一步step++,当step二63(step初始值为0)时表示已经走遍整个棋盘。5.由于每一步走棋都记录在栈中，因此构造数组c[8][8],将栈中数据的输出次序逆向按自身存储的i、j输出到对应的c[i][j]中，再逐行输出数组
8、c[8][8]的内容，即可实现对整个行走路线的输出。6.如果单纯的按照以上方法编写出的程序，在运行时需要花费极多的时间才能运行出结果，这在效率上产生了极大的浪费。因此，需要对算法进行优化处理。通过杳找资料，决定采用贪婪算法对算法做出优化。以下是关于贪婪法的介绍：贪焚算法是指,在对问题求解时，总是做出在当前看來是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意••义上的局部最优解。那么我们在回溯
