子集遞歸演算法

㈠ 演算法的子集和數問題

回溯演算法設計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);