精选优质文档-倾情为你奉上实验6 子集和问题的回溯算法设计与实现一、实验目的1、掌握回溯法解题的基本思想；2、掌握回溯算法的设计方法；3、针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。二、实验内容1、认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；2、了解子集和数问题及解向量的定长和变长状态空间表示；3、针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；4、分析深度优先扩展状态空间树节点或回溯的条件；5、分析和设计生成解向量各分量可选值的实现方法；6、设计和编制回溯算法的递归和迭代程序。【实验题】：组合数问题：找出从自然数1，2，n中任取r个数的所有组合。3、 算法的原理方法回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候
