马的Hamilton周游问题 算法设计课程设计.doc

河南科技大学河南科技大学 课课 程程 设设 计计 任任 务务 书书 课程名称课程名称 软件专题训练 题题 目目 马的马的Hamilton周游路线问题周游路线问题 院院 系系 电子信息工程学院 电子信息工程学院 班班 级级 计算机计算机091091班班 学生姓名学生姓名 张昉华 张昉华 指导教师指导教师 孙士保 张明川 冀治航孙士保 张明川 冀治航 日日 期期 2011年年5月月28日日 2011年年6月月3日日 课程设计题目马的Hamilton周游路线问题 姓名张昉华学号09104060129班级计算机091 系别计算机科学与技术专业计算机科学与技术 组别组长张昉华 组员 指导教师姓名孙士保 张明川 冀治航 课程 设计 目的 进一步巩固C程序设计和算法设计与分析的基础知识 提升结构化程序 模 块化程序设计的方法和能力 深入理解数据结构的基本理论 掌握数据存储结构 的设计方法 掌握基于数据结构的各种操作的实现方法 训练对基础知识和基本 方法的综合运用能力 增强对算法的理解能力 提高软件设计能力 在实践中培 养独立分析问题和解决问题的作风和能力 设计 环境 1 PC兼容机 2 Windows 2000 XP操作系统 3 TC集成开发环境或其他C语言开发环境 课程 设计 要求 和任 务 要求 1 熟练掌握递归与分治策略 能够利用递归与分治解决实际问题 2 使用文件进行存储和管理 程序启动时可从文件中读取信息 或从键盘 输入信息 运行过程中也可对文件进行存取 退出前可选择将部分信息 保存到文件中 3 不同的功能使用不同的函数实现 模块化 对每个函数的功能和调用 接口要注释清楚 对程序其它部分也进行必要的注释 4 对系统进行功能模块分析 画出总流程图和各模块流程图 5 用户界面要求使用方便 简洁明了 美观大方 格式统一 所有功能可 以反复使用 最好使用菜单 6 通过命令行相应选项能直接进入某个相应菜单选项的功能模块 7 所有程序需调试通过 任务 完成马的Hamilton周游路线问题 设计内容包括 1 确定能对给定的偶数m n 6 且 m n 2 编程计算m n的国际象棋棋盘上马的一条Hamilton周游路线 2 程序能够演示一条Hamilton周游路线的周游过程等 课程设计工作进度计划 序 号起止日期工 作 内 容 1下发任务书 分组 选定课题 查阅相关资料 2总体设计 划分模块 3编制源程序 4上机调试 修改 完善系统 5程序检查 6撰写说明书 河南科技大学 课程设计报告 课程名称 课程名称 软件专题训练 设计题目设计题目 马的Hamilton周游路线问题 院院 系 系 电子信息工程学院 专专 业 业 计算机科学与技术 班班 级 级 计算机091班 学生姓名学生姓名 张昉华 学学 号号 09104060129 起止日期起止日期 2011年5月28日 2011年6月3日 指导教师指导教师 孙士保 张明川 冀治航 目录目录 一一设计分析设计分析 1 1 1 课程设计题目课程设计题目 1 1 2 课程设计任务及要求课程设计任务及要求 1 1 3 软硬件运行环境及开发工具软硬件运行环境及开发工具 1 二二程序结构程序结构 2 2 1 流程图流程图 2 2 2各模块的功能及程序说明各模块的功能及程序说明 2 三三源程序源程序 3 3 1源代码源代码 3 3 2操作方法操作方法 4 四四试验结果试验结果 7 五五设计体会设计体会 8 一一 设计分析设计分析 1 1课程设计题目课程设计题目 马的Hamilton周游路线问题 1 2 课程设计任务及要求课程设计任务及要求 1 确定能对给定的偶数m n 6 且 m n 2 编程计算m n的国际象棋棋盘上马的一条Ha milton周游路线 2 程序能够演示一条Hamilton周游路线的周游过程等 1 3 软硬件运行环境及开发工具软硬件运行环境及开发工具 1 PC兼容机 2 Windows 2000 XP操作系统 3 TC集成开发环境或其他C语言开发环境 二二 程序结构程序结构 2 1 流程图流程图 开始 Input 输入棋盘大小m和n Output m n 6 且 m n 2 m n12m n 12 Comp 循环至m n 12 输出 Return 2 2各模块的功能及程序说明各模块的功能及程序说明 void step int m int n grid b 作用 将读入的基础棋盘的Hamilton回路转化为网格数据 void input 作用 读入初始数据 int pos int x int y int col 作用 计算棋盘方格的编号 void build int m int n int offx int offy int col grid b 作用 构造结构化Hamilton回路 void Base int mm int nn int offx int offy 作用 根据基础解构造子棋盘的结构化Hamilton回路 bool comp int mm int nn int offx int offy 作用 分治法主体 void output 作用 输出路线 三三 源程序源程序 3 1源代码源代码 include include include define M 2048 int m n FILE fin typedef struct int x y grid grid b66 36 b68 48 b86 48 b88 64 b810 80 b108 80 b1010 100 b1012 120 b1210 120 grid link 500 500 int a 10 12 void step int m int n grid b int i j k m n p if m n for i 0 i m i for j 0 j n j p a i j 1 b p x i b p y j else for i 0 i m i for j 0 j n j p a j i 1 b p x i b p y j void input printf 请输入棋盘规格 格式为m n 例如 6 6 scanf d d fin fopen infoundation r int i j for i 0 i 6 i 读入m n的基本的回路 for j 0 j 6 j fscanf fin d step 6 6 b66 for i 0 i 6 i for j 0 j 8 j fscanf fin d step 6 8 b68 step 8 6 b86 for i 0 i 8 i for j 0 j 8 j fscanf fin d step 8 8 b88 for i 0 i 8 i for j 0 j 10 j fscanf fin d step 8 10 b810 step 10 8 b108 for i 0 i 10 i for j 0 j 10 j fscanf fin d step 10 10 b1010 for i 0 i 10 i for j 0 j 12 j fscanf fin d step 10 12 b1012 step 12 10 b1210 int pos int x int y int col return col x y void build int m int n int offx int offy int col grid b int i p q k m n x1 x2 y1 y2 for i 0 i2 nn mm 2 mm 6 nn 6 return true if mm 12 nn0 mm1 mm2 mm mm1 nn1 nn 2 if nn 4 0 nn1 nn2 nn nn1 comp mm1 nn1 offx offy comp mm1 nn2 offx offy nn1 comp mm2 nn1 offx mm1 offy comp mm2 nn2 offx mm1 offy nn1 x 0 offx mm1 1 y 0 offy nn1 3 x 1 x 0 1 y 1 y 0 2 x 2 x 1 1 y 2 y 1 2 x 3 x 2 2 y 3 y 2 1 x 4 x 3 1 y 4 y 3 2 x 5 x 4 1 y 5 y 4 2 x 6 x 5 1 y 6 y 5 2 x 7 x 6 2 y 7 y 6 1 for i 0 i 8 i p i pos x i y i n for i 1 i 8 i 2 j1 i 1 8 j2 i 2 8 if link x i y i x p i 1 link x i y i x p j1 else link x i y i y p j1 if link x j1 y j1 x p j2 link x j1 y j1 x p i else link x j1 y j1 y p i return false void output int i 0 j 0 k 2 x y p int b 500 500 if comp m n 0 0 return for i 0 i m i for j 0 j n j b i j 0 b 0 0 1 printf 0 0 for p 1 p m n p x link i j x y link i j y i x n j x n if b i j i y n j y n b i j k printf d d i j if k 1 n 0 printf n printf n for i 0 i m i for j 0