子集和问题的回溯算法
《算法分析与设计》
实验报告
2015-2016年第2学期
实验班级： 学生姓名： 学 号： 指导老师：
信息工程学院
实验项目名称：子集和问题的回溯算法 实验日期：2016年 6月 1 日
√验证性 □设计性 一、实验类型： □
二、实验目的
1、掌握回溯法解题的基本思想；
2、掌握回溯算法的设计方法；
3、针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。
三、实验内容及要求
1、认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；
2、了解子集和数问题及解向量的定长和变长状态空间表示；
3、针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；
4、分析深度优先扩展状态空间树节点或回溯的条件；
5、分析和设计生成解向量各分量可选值的实现方法；
6、设计和编制回溯算法的递归和迭代程序。
【实验题】：
组合数问题：找出从自然数1，2，…，n中任取r个数的所有组合。
四、实验步骤
#include
#include
#define N 100
using namespace std;
int a[N]; //暂存结果数组，排列
void comb(int n,int r)
{ int i,j; i=0; a[i]=1;
do
{
if(a[i]-i
{
if (i==r-1)/*已找到一个组合*/
{
for (j=0;j
coutcout
a[i]++;
continue;
}
i++;
a[i] = a[i-1] + 1; /*向前试探*/
}
else
{
if (i==0)
return;/*已找到所有解*/
a[--i]++;
} /*回溯*/
}
while (1);
}
int main()
{
int n,r;
cin>>n>>r;
comb(n,r);
return 0;
}
五、实验结果
1、实验图形
2、结果分析
输入r的值为4，产生组合的位数为3，根据程序定义，得到的所有组合为123、124、134、234。
输入r的值为6，产生组合的位数为4，根据程序定义，得到的所有组合为1234、1235、1236、1245、1246、1256、1345、1346、1356、1456、2345、2346、2356、2456、3456。
3、实验总结
在前面的实验中我们学会了掌握0—1背包问题的回溯算法和掌握符号三角形 问题的回溯算法等相关的知识点问题，本次的实验中我们要学会的是对于针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现，在实验过程中发现自己还有很多不明白的地方，很多的地方都是一知半解，希望以后能得到更多的学习。 总之，本次的实验让自己看到了了自己的不足，让自己知道了接下来该加强的方向。