子集和问题的回溯算法.doc

《子集和问题的回溯算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验报告2015-2016年第2学期实验班级：学生姓名：学号：指导老师：信息工程学院实验项目名称：子集和问题的回溯算法实验日期：2016年6月1日一、实验类型：验证性□设计性二、实验目的1、掌握回溯法解题的基本思想；2、掌握回溯算法的设计方法；3、针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。三、实验内容及要求1、认真阅读教材或参考书,掌握回溯法解题的基本思想,算法的抽象控制策略；2、了解子集和数问题及解向量的定长和变长状态空间表示；3、针对解向量的定长表示,设计状态空间树节点扩展的规范(限界)函数及实现

2、方法；4、分析深度优先扩展状态空间树节点或回溯的条件；5、分析和设计生成解向量各分量可选值的实现方法；6、设计和编制回溯算法的递归和迭代程序。【实验题】：组合数问题：找出从自然数1，2，…，n中任取r个数的所有组合。四、实验步骤#include#include#defineN100usingnamespacestd;inta[N];//暂存结果数组，排列voidcomb(intn,intr){inti,j;i=0;a[i]=1;do{if(a[i]-i<=n-r+1)/*还可以向前试探*/{if(i=

3、=r-1)/*已找到一个组合*/{for(j=0;j>n>>r;comb(n,r);return0;}一、实验结果1、实验图形1、结果分析输入r的值为4，产生组合的位数为3，根据程序定义，得到的所有组合为123、124、134、234。输入r

4、的值为6，产生组合的位数为4，根据程序定义，得到的所有组合为1234、1235、1236、1245、1246、1256、1345、1346、1356、1456、2345、2346、2356、2456、3456。3、实验总结在前面的实验中我们学会了掌握0—1背包问题的回溯算法和掌握符号三角形问题的回溯算法等相关的知识点问题，本次的实验中我们要学会的是对于针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现，在实验过程中发现自己还有很多不明白的地方，很多的地方都是一知半解，希望以后能得到更多的学习。总之，本次的实验让自己看到了了自己的

5、不足，让自己知道了接下来该加强的方向。