算法课程设计--沈阳理工大学

《算法课程设计--沈阳理工大学》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、成绩评定表学生姓名班级学号专Yk信息与计算科学课程设计题目递归解决集合划分问题和回溯法解决最小机器重量问题评语组长签字：成绩日期20年月FI课程设计任务书学院理学院专业信息与计算科学学生姓名班级学号课程设计题目递归解决集合划分问题和冋溯法解决最小机器重量设计问题实践教学要求与任务：1、巩固和加深对计算机算法分析与设计基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。4、具体任务（1）递归解决集合划分问题（2）冋溯法解决最小机器重量

2、问题工作计划与进度安排：第一天查阅资相关料；第二、三天程序设计；第四天程序调试；第五天答辩指导教师：201年月曰专业负责人：201年月曰学院教学副院长：201年月曰摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要口的就是为了解决某一问题而提出的各种不同的解决方案，并且要针对具体问题做细致的空间与吋间复杂度分析。本文通过计算机算法分析设计出解最优二叉搜索树问题的动态规划算法和设计出解图的着色问题全部可行解的回溯法算法，利用C++语言编写程序实现算法。

3、递归通常把一个人型复杂的问题层层转化为一个与原问题相似的规模较小的问题來求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，人大地减少了程序的代码量。递归的能力在于用有限的语句來定义对象的无限集合回溯法算法是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能

4、再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键字：递归；回溯法；集合划分；C++目录目录41.课程设计口的52.课程设计题目53.概要设计53」递归…集合划分问题53.2冋溯法一•最小机器重量设计问题54•详细设计与实验

5、64.1集合划分问题64.1.1集合划分问题描述和分析64.1.2实验原理64」.3源代码74」.4运行结果84.2最小机器重量设计问题84.2.1最小机器重量设计问题描述84.2.2算法设计思想94.2.3设计过程94.2.4源代码114.2.5运行结果15总结16参考文献171・课程设计目的《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的

6、理解，可以训练我们算法设计的思维和培养算法的分析能力。2•课程设计题目递归：解决集合划分问题；冋溯法：解决最小机器重量问题。3•概要设计3・1递归…集合划分问题递归把一个大型问题转化为一个与原问题相似的小问题，递归策略只需少量的程序就可描述岀解题过程所需要的多次重复计（1）把一•个大型问题转化为一•个与原问题相似的小问题（2）递归就是在过程里调用自身；（3）设定一个明确的递归结束条件，作为递归出口。3.2回溯法…最小机器重量设计问题回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（

7、根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同吋也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。冋溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。用冋溯法解决

8、图的着色问题的步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数原则避免无效搜索。4•详细设计与实验4.1集合划分问题4.1.1集合划分问题描述和分析1)内容描述：n个元索的集合｛l,2,・,n｝可以划分为若干个非空子集。例如,当n=4时，集合｛1,2,3,4｝可以划分为15个不同的非空了集2)编程任务：给定正整数n和m,计算出n个元素的集合｛l,2,.,n｝可以划分为多少个不同的由m个非空子集组成的