探索法的应用.doc

数学与计算机学院 课程设计说明书 课 程 名 称 算法设计与分析 课程设计 课 程 代 码 7106620 题 目 探索法的应用 年级 专业 班 学 生 姓 名 学 号 开 始 时 间 年 月 日 完 成 时 间 年 月 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际 能力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 西华大学数计学院课程设计说明书 I 目 录 1 引 言 1 1 1 问题的提出 1 1 2 国内外研究的现状 1 1 3 任务与分析 1 2 程序的主要功能 2 2 1 新建数组 2 2 2 判定数组 2 2 3 设定需要的界面 2 3 程序运行平台 3 4 总体设计 4 5 程序类的说明 5 6 模块分析 7 6 1 迷宫问题主函数模块 7 6 2 迷宫问题中 方位为上 下 左 右位置可到达 7 6 3 迷宫问题判断出口位置 10 6 4 预先设定迷宫 12 6 5 计算机进程调度全局数据结构和变量 12 6 6 计算机进程调度函数说明 13 7 系统测试 14 8 结论 27 参考文献 28 西华大学数学与计算机学院课程设计说明书 1 1 1 引引 言言 1 11 1 问题的提出问题的提出 在很多研究中 数学问题的形式千变万化 结构错综复杂 寻找正确有效的解题 途径 以为着寻找一条摆脱困境 绕过障碍的途径 在这些问题的解决过程中 探索 法无疑成为了一种最有效的方法 由此提出了迷宫问题等问题的探索法 要解决此类 问题 向各个方向考虑 由此找到一条最有效的解决途径 由此来解决问题 正是探 索法的探索解决问题的优点 由此有很多问题需要用这种方法解决 1 21 2 国内外研究的现状国内外研究的现状 探索法在现代研究和学习中 起着非常重要的作用 在各个科学 人文等领域占 据着非常重要的作用 有很多科学研究需要在问题的提出时 探索问题的各种有效途 径 由此来获得解决问题的最有效方法 1 31 3 任务与分析任务与分析 本课题主要的目的是用探索法解决各类问题 由此获得各类问题的最有效途径 探索法实现过程中 在对问题的解决过程中 先假设问题的各个解决途径 在对问题 进行分析 用探索法来研究发现和发明的规律和方法 解决迷宫问题时 分为 4 个方 向去试探路径 如果遇到下一个路径为 1 表示此路径不能行走 返回上一位置 再寻 找其他路径 如果不是 1 继续向前行走 知道找到出口 算法设计与分析课程设计 探索法的应用 2 2 2 程序的主要功能程序的主要功能 2 12 1 新建数组新建数组 1 在解决迷宫问题时 新建一个数组 用来判定迷宫问题的出口 2 对计算机作业调度问题 新建一个数组 对计算机各个正在运行的作业进行判 定 2 22 2 判定功能判定功能 1 对迷宫问题进行编译 分别编译判定迷宫中方位为上 下 左 右的位置可到 达 然后编译判定迷宫问题的入口 分别编译迷宫入口是否在上 下 左 右 2 对计算机作业调度问题编译 编译能判定计算机正在调度的进程 2 32 3 设定需要的界面设定需要的界面 1 设定一个已知的迷宫 由此能有前面的程序判定出迷宫的可以出行的路径 2 设定计算机作业调度的界面 由此来运行计算机作业调度的程序 西华大学数学与计算机学院课程设计说明书 3 3 3 程序运行平台程序运行平台 VC 6 0 具体操作如下 新建 win32 Console Application 工程 添加相应的源文件 再 添加新建工程 再编译 链接 执行等 算法设计与分析课程设计 探索法的应用 4 4 4 总体设计总体设计 图 4 1 迷宫问题系统总体框架图 主 函 数 方 位 为 上 可 方 位 为 下 方 位 为 左 方 位 为 右 入 口 在 左 入 口 在 右 西华大学数学与计算机学院课程设计说明书 5 图 4 2 计算机进程调度系统总体框架图 算法设计与分析课程设计 探索法的应用 6 5 5 程序类的说明程序类的说明 迷宫问题数据结构迷宫问题数据结构 int searchNext int c 3 4 int k int l void findEnterence int c 3 4 int k int l void searchPath int c 3 4 int k 0 l 0 findEnterence c searchNext c k l 计算机进程管理数据结构计算机进程管理数据结构 PCB 结构 struct PCB int pname int pri int runtime int waittime struct PCB next pcb 7 运行指针 struct PCB running 高优先级就绪队列头指针 struct PCB Hready 低优先级队列头指针 struct PCB Lready 等待队列头指针 struct PCB wait int sig 0 西华大学数学与计算机学院课程设计说明书 7 6 6 模块分析模块分析 6 16 1 迷宫问题主函数模块迷宫问题主函数模块 迷宫问题中 主要的头文件函数 int searchNext int c 3 4 int k int l void findEnterence int c 3 4 int k int l void searchPath int c 3 4 int k 0 l 0 findEnterence c searchNext c k l 6 26 2 迷宫问题中 方位为上 右 下 左的位置可到达迷宫问题中 方位为上 右 下 左的位置可到达 现实迷宫问题中 方位为上 右 下 左的位置时 可到达的情况 if k 0 return 1 break else printf no pass return 0 6 36 3 迷宫问题判断出口位置迷宫问题判断出口位置 判断迷宫问题的出口 int i k 保存行 l 保存列 入口是否在左边 西华大学数学与计算机学院课程设计说明书 9 for i 0 i m i if c i 0 2 k i l 0 return 6 46 4 预先设定迷宫预先设定迷宫 预先设定固定的迷宫 修改迷宫 由此来设置迷宫的路径 int c m n 2 1 1 1 0 0 0 0 1 1 1 3 searchPath c printf n return 0 6 56 5 计算机进程调度全局数据结构和变量计算机进程调度全局数据结构和变量 编写计算机进程调度全局数据结构 为运行程序做准备 PCB 结构 struct PCB int pname int pri int runtime int waittime 算法设计与分析课程设计 探索法的应用 10 struct PCB next pcb 7 运行指针 struct PCB running 高优先级就绪队列头指针 struct PCB Hready 低优先级队列头指针 struct PCB Lready 等待队列头指针 struct PCB wait int sig 0 6 66 6 计算机进程调度函数说明计算机进程调度函数说明 对程序中的函数进行说明 void delay 模拟进程 3 9 void proc struct PCB running 将 node 插入到 head 所指示的队列的尾部 void InsertIntoQueueTail struct PCB head struct PCB node 进程调度函数 int proc switch 进程等待函数 void proc wait 进程唤醒函数 int proc wakeup 西华大学数学与计算机学院课程设计说明书 11 7 7 系统测试系统测试 首先进入 VC 6 0 打开工程冯涛 cpp 然后进入源程序 接着编译 运行即可 对迷宫问题进行运行 预先设置迷宫 1 如下图 图 7 1 迷宫 1 算法设计与分析课程设计 探索法的应用 12 8 结论 探索法在对迷宫问题和计算机进程调度解决过程中有很大作用 在解决这类 问题的过程中 探索法是一种性能卓越的方法 在迷宫问题中 通过设计迷宫的出 口和各个方位 来解决获得迷宫的最好的出口 通过探索法来探索迷宫问题的最好 的路径 探索法在解决此类问题中效果明显优于其他算法 通过此次课程设计 我对用探索法解决迷宫问题等问题有了深入的认识 并且 更深入了解了 C 的使用 对以后的学习有很大的帮助 西华大学数学与计算机学院课