logo资料库

数据结构课设马踏棋盘.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    马踏棋盘
    1问题描述
    2程序设计
    附件 1： 学 号： 课 程 设 计 题 目 马踏棋盘 学 院 计算机科学与技术 专 业 计算机科学与技术 班 级 姓 名 指导教师 2011 年 7 月 4 日
    附件 2： 课程设计任务书 专业班级： 班 工作单位： 计算机科学系 学生姓名： 指导教师： 题 目: 马踏棋盘 初始条件： 设计一个国际象棋的马踏遍棋盘的演示程序。 将马随机放在国际象棋的 8×8 棋盘 Board[8][8]的某个方格中，马按走棋 规则（见题集 p98）进行移动。要求每个方格只进入一次，走边棋盘上全部 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1,2,3,…,64 依次填入一个 8×8 的方阵，输出之。 测试用例见题集 p98。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明 书撰写等具体要求） 课程设计报告按学校规定格式用 A4 纸打印（书写），并应包含如下内容： 1、 问题描述 简述题目要解决的问题是什么。 2、 设计 存储结构设计、主要算法设计（用类 C 语言或用框图描述）、测试用例 设计； 3、 调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4、 经验和体会（包括对算法改进的设想） 5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数 据，则运行结果要包含这些测试数据和运行输出， 6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩 均为 0 分。 时间安排： 1、第 19 周完成。 2、7 月 1 日 14：00 到计算中心检查程序、交课程设计报告、源程序（CD 盘）。 指导教师签名： 年 月 日 系主任（或责任教师）签名： 年 月 日
    马踏棋盘 1 问题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 基本要求： 将马随机放在国际象棋的 8×8 棋盘 Board[8][8]的某个方格中，马按走棋 规则（见题集 p98）进行移动。要求每个方格只进入一次，走边棋盘上全部 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1,2,3,…,64 依次填入一个 8×8 的方阵，输出之。 2 程序设计 1 存储结构 马位于方格（i，j）时有八个可能的移动位置。分别用两个一维数组 move1[0…7]、 move2[0…7]来表示这八个位置的。Board[][]用于存储走过方格所填入的数字， 从 1 到 64. int HTry1[8]={2,2,1,1,-1,-1,-2,-2,}, HTry2[8]={1,-1,2,-2,2,-2,1,-1,}， board[8][8]={{0}}; 2 主要算法 程序主要用到两个函数，nextpos 与 movenext。分别用来计算可能的出口 个数和选择出口。 int { nextpos(int i,int j,int a[8],int b[8]) count=0,k,i1,j1; //函数 nextpos 计算位置（i，j）出口个数 int for(k=0;k<8;k++) { i1=i+move1[k]; j1=j+move2[k]; if(i1>7||i1<0||j1>7||j1<0) continue; else if(board[i1][j1]!=0) continue; else {
    a[count]=move1[k]; b[count]=move2[k]; ++count; } } return(count); } 函数 nextpos 用于计算（i，j）可走的出口数，用 count 返回。先从当前位置 走到八个可能的位置中的一个，若超出 8*8 边界则返回进行下一循环，若已被填 入数字则也要返回进行下一循环。反之纪录这一可走出口的位置并将 count 加 1. int movenext(int *i,int *j,int a[],int b[]) { //函数 movenext 在有多出口时，选择适当出口推进一步 int temp,count=8,a1[8],b1[8], nexti_like[8],nextj_like[8], cur_row_like,cur_col_like,k,t; for(k=0;k
    3 调试程序 运行结果 结果正确 结果错误 无路径 无路径 结果错误 输入无效 预期结果 输入有效 输入无效 输入无效 输入无效 测试数据 （3，4） （9,0） （-9,4） （10,12） （a，4） 调试结果： 经过测试发现出错，当输入的字符为非数字字符时，均会被默认输入为（0，0）。 原因在于，输入模块用两个整形数据接收用户的输入数据，当这两个数据不是数 字字符时，系统会默认其为 0。故为该模块代码增设两个字符变量以接收用户输 入的数据。在次测试，符合预期结果。当输入数据超过 8 之后就会显示没有路径。 最后调试完了输出一个 8*8 的方阵，方阵中数字从 1 到 64 表示依次所走的每一 步。 4 体会 根据问题描述可知，需要解决的问题并不复杂，整个问题只需要实现一个功 能那就是输出马按特定规则在棋盘上的遍历顺序。但是为了实现该功能却需要好 的算法以减少时间空间复杂度。由于对象是棋盘我们自然想到把棋盘抽象成一个 二维数组，并且用两个一维数组存放（i，j）可能移动到的位子的行与列。主要 用到两个函数 nextpos 和 movepos 分别计算出口个数和选择一个出口走下一步。 每走一步都输出相应数字，从 1 到 64，于每一步相对应。知道走完 8*8 方格。 此程序主要用到回溯的思想，每次选一个出口，如果最后路不通，可以通过前面 保存的位置进行回溯。 其实马踏棋盘问题还可以采用栈或队来作为存储结构，另外非递归算法比递 归算法更简洁，复杂度也小一些。可以采用深度优先搜索来解决。深度优先遍历 马的行走路径所构成的一颗解的空间树，马的行走路径实际上就是从这颗解空间 树的根节点到叶节点过程中经过的所有节点所组成的路径。此外这个程序稍作修 改之后可以表示一个 9*9 的棋盘。 经过这次数据结构课程设计，我们不仅及时巩固了算法及软件工程的知识， 并利用所学的知识解决了实际问题。我的课设题目是马踏棋盘，最初拿到题目很 茫然，但是翻看了一下指导书之后有了个大致思路。大部分代码是自己编写的， 只有其中一个函数是查了资料之后参考了一下的。上机运行程序时没有错误。老 师验收时提了相关问题，我都一一作了回答，对运行结果老师问道 1 到 64 代表 什么，可不可以改成 9*9 方格，对此我都做了回答。我觉得自己对此次实验完成 的还不错，达到了课设的目的。 5 运行结果 输入（3,4）之后运行结果截屏如下：
    输入符合要求的初始位置，得到的结果正确。 输入的初始位置不合理，结果显示没有路径。
    本科生课程设计成绩评定表 班级： 姓名： 学号： 序号 评分项目 满分 实得分 1 学习态度认真、遵守纪律 2 设计分析合理性 3 设计方案正确性、可行性、创造性 4 设计结果正确性 5 设计报告的规范性 6 设计验收 评语： 10 10 20 40 10 10 总得分/等级 注：最终成绩以五级分制记。优（90-100 分）、良（80-89 分）、中（70-79 分）、 及格（60-69 分）、60 分以下为不及格 指导教师签名： 201 年 月 日
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料