山东大学数据结构第1-3课作业.pdfVIP

第第一章作章作业 5. 试编试编写一个递归个递归函数数，用来输来输出n 个个元素的素的 所有子集。例如，三个元素{a, b, c} 的所有子 集是：{ } （空集），{a}, {b}, {c}, {a, b}, {a, c}, {{b,, c}} 和{{a,, b,, c}} 。 1 基本思想： 用一个一维数组x[1:n]表示大小为n的数组的一 个子集个子集。。 如果第j个元素包含在子集中，那么x[j]=1 ，否 则则x[j]x[j]=00； 例如原数组为{a,b},那么他的子集为{0，0}， {0，1}，{1，0}，{1，1}。分别对应子集{Ø}， {{b}},{{a}},{{a,b}} ． 2 函数实现： #include iostream.h //// 定义全局变量定义全局变量，ｎ在主函数种初始化在主函数种初始化 int x[20], // 子集向量，假设大小为20 n; // 数组元素个数 void Subsets(int i ，int n) {// 输出数组a[i:n].的所有子集 // 只有只有x[[i:n]] 在每次递归调用时改变在每次递归调用时改变，x[[1:i-1],], 已经被确定为了被确定为了0 或或1 if (i == n) {// x[n] 可以是0或1 // 输出不包含元素n的子集 x[n]x[n] = 0;0; for (int j = 1; j = n; j++) cout x[j] ; coutcout endl;endl; //输出包含元素n的子集 x[[n]] = 11; for (j = 1; j = n; j++) cout x[j] ; cout endl; return; 3 } // 子集中不包含元素ｉ的情况 x[i] = 0; // 递归调用产生不含有元素ｉ的所有子集 Subsets(i+1,n); //子集中包含元素ｉ的情况 x[i]x[i] = 1;1; //递归调用产生含有元素ｉ的所有子集 Subsets(i+1Subsets(i+1,n);n); } 4 #include iostream intint x[100];x[100]; //// 子集向量子集向量，，假设大小为假设大小为100100 template class T void Subsets(int i ,int n ,T a[]) {//{// 输出数组输出数组a[i:n]a[i:n].的所有子集的所有子集 // 只有x[i:n] 在每次递归调用时改变，x[1:i-1], 已经被确定为了0 或1 if (i == n) {// x[n] 可以是0或1 //// 输出不包含元素输出不包含元素nn的子集的子集 x[n] = 0; int temp=0; ffor ((int j = 1; j = n; j++)) { if(x[j]!=0) {cout a[j] ;temp=1;} } if(temp==0) cout空集; cout endl;