文档介绍：沈阳理工大学课程设计 I 成绩评定表学生姓名唐智班级学号 1209010324 专业信息与计算科学课程设计题目评语组长签字: 成绩日期 20年月日沈阳理工大学课程设计 II 课程设计任务书学院理学院专业信息与计算科学学生姓名郭卫班级学号 1209010315 课程设计题目分治法——黄金分配回溯法——填字游戏实践教学要求与任务:1、巩固和加深对计算机算法分析与设计基本知识的理解。 2、初步掌握简单软件的分析方法和设计方法。 3、了解与课程有关的工程技术规范,能正确解释和分析设计结果。 4 、具体任务(1 )分治算法解决黄金分配问题。(2 )回溯法解决填字游戏问题。工作计划与进度安排: 第一天查阅资相关料; 第二、三天程序设计; 第四天程序调试; 第五天答辩指导教师: 201 年月日专业负责人: 201 年月日学院教学副院长: 201 年月日沈阳理工大学课程设计摘要算法设计与分析,其实可以解释为一类优化问题,一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案,并且要针对具体问题做细致的空间与时间复杂度分析。本文通过计算机算法分析设计出解最优二叉搜索树问题的动态规划算法和 0-1 背包问题的回溯法算法,利用 C++ 语言编写程序实现算法。动态规划算法是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。首先找出最优解的性质,并刻画其结构特征, 然后递归的定义最优值(写出动态规划方程)并且以自底向上的方式计算出最优值,最后根据计算最优值时得到的信息,构造一个最优解。回溯法算法是确定了解空间的组织结构后,回溯法就是从开始节点(根结点) 出发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。换句话说, 这个节点,这个结点不再是一个活结点。此时,应往回(回溯)移动至最近一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索,直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键词:动态规划;二叉搜索树; 回溯法;剪枝原则; C++ 沈阳理工大学课程设计目录一、课程设计目的........................................................................................................ 1 二、课程设计内容........................................................................................................ 1 三、概要设计................................................................................................................ 1 动态规划—最优二叉搜索树........................................................................ 1 回溯法—0-1 背包......................................................................................... 1 四、详细设计与实现.................................................................................................... 2 动态规划—最优二叉搜索树........................................................................ 2 最优二叉搜索树问题描述和分析..................................................... 2 最优子结构性质................................................................................. 3 递归计算最优值................................