子集递归算法

㈠ 算法的子集和数问题

回溯算法设计2008-05-29 10:15 P.M.[实验目的]

1. 掌握回溯法解题的基本思想；

2. 掌握回溯算法的设计方法；

3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。

[预习要求]

1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；

2. 了解子集和数问题及解向量的定长和变长状态空间表示；

3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；

4. 分析深度优先扩展状态空间树节点或回溯的条件；

5. 分析和设计生成解向量各分量可选值的实现方法；

6. 设计和编制回溯算法的递归和迭代程序。

[参考数据类型或变量]

float s; // 表示有可能抵达答案节点的子路径上的元素之和；

float r; // 尚未测试的剩余集合元素之和；

float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化；

int x[n]; // 定长表示的解向量, 各元素初始值为0；

[参考子程序接口与功能描述]

void RecursiveSubset(float s, float r, int k)

功能: 针对问题实例的递归回溯算法。

void IterativeSubset(int m)

功能: 针对问题实例的迭代回溯算法。

void InitializeInstanse(void)

功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。

[实验步骤]

1. 录入、修改并测试你的程序，直至正确为止；

2. 针对问题实例，实录运行时的输入、输出界面；

3. 将你的程序和实录的界面存盘备用。

[实验报告要求]

1. 阐述实验目的和实验内容；

2. 提交模块化的实验程序源代码；

3. 简述程序的测试过程，提交实录的输入、输出界面；

4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。

[思考与练习]

1. 试针对解向量的变长表示设计回溯算法，上机测试正确性。

2. 试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。

#include<stdio.h>
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和；*/
float r; /*尚未测试的剩余集合元素之和；*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化；*/
int x[n]; /*定长表示的解向量, 各元素初始值为0；*/
int M;
int k;

void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}

else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");

㈡ 求高手解答一个算法!!!!!!

#include<stdio.h>
int n,a[100],r; /*数组a为记录集合的元素*/
int ans[100]; /*记录子集的元素*/
void solve(int k,int p) /*在子集数组ans里已有k个元素,p为ans最后的元素下标*/
{
int i;
if(k>r) /*已经找到一个子集*/
{
for(i=1;i<=r;i++) /*显示子集*/
printf("%d ",ans[i]);
printf("\n");
return;
}
if(p>n) /*找不到子集*/
return;
for(i=p+1;i<=n;i++) /*递归查找子集*/
{
ans[k]=a[i]; /*当前元素放进子集数组*/
solve(k+1,i); /*下一个元素*/
}
}
void main()
{
int i;
scanf("%d%d",&n,&r);
for(i=1;i<=n;i++) /*初始集合数组元素*/
a[i]=i;
solve(1,0); /*查找开始*/
}

上面的程序还可以优化,可以让速度更快些,更省空间!你自己看看吧!还有最好是看懂程序,不要照抄!你还可以用其他方法,这是用了递归回溯算法!

㈢ java树级对象递归查找子集问题

packagecom.demo.dept;

/**
*@authordongbin.yu
*@from2016-05-06
*@sinceV1.0
*/
publicclassDept{

privateintid;

privateStringname;

privateintparentId;

publicintgetId(){
returnid;
}

publicvoidsetId(intid){
this.id=id;
}

publicStringgetName(){
returnname;
}

publicvoidsetName(Stringname){
this.name=name;
}

publicintgetParentId(){
returnparentId;
}

publicvoidsetParentId(intparentId){
this.parentId=parentId;
}

publicDept(intid,Stringname,intparentId){
this.id=id;
this.name=name;
this.parentId=parentId;
}
}

packagecom.demo.dept;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

/**
*@authordongbin.yu
*@from2016-05-06
*@sinceV1.0
*/
publicclassDeptTest{

privatestaticList<Dept>depts=newArrayList<>();

static{
depts.add(newDept(1,"部门1",0));
depts.add(newDept(2,"部门2",1));
depts.add(newDept(3,"部门3",1));
depts.add(newDept(4,"部门4",1));
depts.add(newDept(5,"部门5",2));
depts.add(newDept(6,"部门6",3));
depts.add(newDept(7,"部门7",2));
depts.add(newDept(8,"部门8",2));
depts.add(newDept(9,"部门9",1));
depts.add(newDept(10,"部门10",5));
}

publicstaticvoidmain(String[]args){
Map<Integer,List<Integer>>deptMap=newHashMap<>();

for(Deptdept:depts){
deptMap.put(dept.getId(),getChildDept(dept.getId()));
}

System.out.println(deptMap);

}

privatestaticList<Integer>getChildDept(intid){
List<Integer>ids=newArrayList<>();

for(Deptdept:depts){
if(dept.getParentId()==id){
//添加第一次父id符合的
ids.add(dept.getId());
//添加嵌套父id符合的
ids.addAll(getChildDept(dept.getId()));
}
}
Collections.sort(ids);
returnids;
}

}

㈣ 用c++求2-10个正整数的子集，递归算法求解。

如果你说的是打印出所有可能的集合的话..
#include<iostream>

void printSet(int*, int);
int* Set(int*, int, int);

void getSubSet(int* set, int len) {
if(len > 0) {
printSet(set, len);
for(int i = 0; i < len; i++) {
getSubSet(Set(set, len, i), len - 1);
}
}
}

int* Set(int* set, int len, int index) { //return a set with less 1 count. specfic the index.
int j = 0;
int *set2 = new int[len - 1];
for(int i = 0; i < len; i++) {
if(index != i) {
set2[j++] = set[i];
}
}
return set2;
}

void printSet(int* set, int len) {
using namespace std;
cout << "{ ";
for(int i = 0; i < len; i++) {
cout << set[i] << ", ";
}
cout << "}" << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
int i = 0;
while(1) {
cout << "Getting all subsets..." << endl;
cout << "How many numbers do you wanna input ? " ;
cin >> i;
if(cin.good() && i >= 2 && i <= 10) break;
cin.clear();
}
int* set = new int[i];
for(int j = 0; j < i; j++) {
cout << endl << "Input number " << j + 1 << ": ";
cin >> set[j];
if(!cin.good()) {
cout << "Bad input, quitting...";
system("pause");
return 0;
}
}
printSet(set, i);
system("pause");
cout << endl << "Now printing Set... " << endl;
getSubSet(set, i);
delete[] set;
cout << endl << "Finished, press any key to quit. " << endl;
system("pause");
return 0;
}

㈤ 写一个递归算法

用C++实现的，希望对你有所帮助：（还有种的经典的算法：000，001，010...111每一位表示是否包含这个元素，自己可以再想想）
#include<iostream>
using namespace std;
template<class T>
void powerset(T *a,T* b,int n1,int n2,int n)
{
if(n1==-1)
{
int j=n-1;
if(j<n2+1){cout<<"空集";}
for(;j>=n2+1;j--)
{
if(j==n-1){cout<<"{";}
if(j==n2+1){cout<<b[j]<<"}";}
else {cout<<b[j]<<",";}
}
cout<<endl;
}
else
{
for(int i=n1-1;i>=-1;i--)
{
if(i!=-1){b[n2-1]=a[i];}
powerset(a,b,i,n2-1,n);
}

}
}
template<class T>
void ChildUnion(T* a,int n)
{
T* b=new T[n];
powerset(a,b,n,n,n);

delete []b;

}
void main()
{
int a[4]={0,1,2,3};
ChildUnion(a,4);
}

㈥ 求用递归法求一个集合的子集的C++代码！！

参考下面的

找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3

的所有组合为：

（1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数comb。
【程序】
# include
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}

void main()
{ a[0]=3;
comb(5,3);
}

㈦ python 子集的算法优化； 找寻一个list的所有满足特定条件的子集

使用 itertools呀

importitertools

#有序
printlist(itertools.permutations([1,2,3,4],2))
[(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)]

#无序
printlist(itertools.combinations([1,2,3,4],2))
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

㈧ 请问递归算法的时间复杂度如何计算呢

递归算法的时间复杂度在算法中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，常用以下四种方法：

1.代入法(Substitution Method)

代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。

2.递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的.

3.但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省.

㈨ 递归输出集合子集

思路： 对于某个集合元素 e 和某个子集subset, e要不就在这个集合中，要不就不在。 故，只需枚举所有元素的在或不在某子集， 即可枚举所有子集。

不标准伪代码： 不妨设集合元素为 e[0] 到 e[n-1] 共n个, 用数组 flag[0] 到 flag[n-1] 代表i元素是否在当前集合

void Output( i )
{
if ( i == 集合元素个数n)
{
根据flag数组输出当前集合(在或不在);
return;
}
flag[i] = 在当前集合;
Output(i + 1);
flag[i] = 不在当前集合；
Output(i + 1);
}

初始化时 flag[0] 到flag[n-1]都为 ‘不在当前集合’;
初始调用 Output(0);