网站界面设计的主要内容,做网站如何获利,网站开发之ios知识扩展,在哪个网站做旅游攻略好1、题目#xff08;《离散数学及其应用》第6版P75 20 题#xff09; 给出可以列出有限集合所有子集的步骤。 2、 解题思路 假设有集合A {a1, a2 … an}#xff0c;列出其所有子集。 先列出含有1个元素的所有子集#xff1a;{a1},{a2} … {an}然后列出含有2个元素的所有子…1、题目《离散数学及其应用》第6版P75 20 题 给出可以列出有限集合所有子集的步骤。 2、 解题思路 假设有集合A {a1, a2 … an}列出其所有子集。 先列出含有1个元素的所有子集{a1},{a2} … {an}然后列出含有2个元素的所有子集{a1,a2},{a1,a3}…{an-1,an}同上所示一直列到含有n个元素的所有子集可以看出问题就简化为求在 A 集合中求含有固定 x 个元素的所有子集注意子集中每个ai只能包含一次。 这实际上类似这么个问题袋子中有编号为1到10的10个球每次取一个球取出后不放回袋子取3次问取出的3个球的编号可能的所有组合。 方法 取第1个球时有110种取法取第2个球时如果知道第1个球取的编号是a则第2个球有除a以外的9种取法但要注意{1,2}和{2,1}是同一个子集如何保证不取已经取过了的同一组编号的球我们可以观察到如果让{1,2}2个球按编号大小排列只有一种排列方式即{1,2},所以只要保证第2个球的编号比第一个球的编号大即可保证不会取到{2,1} 所以我们可以在取第2个球时从 (a1) 开始取即可保证不会取到重复的排列方式 同时我们取第3个球时一样需要知道第1、2个球的编号这实际上就是一个递归问题了假设已知取到第1个球为a第2个球为b则第三个球的取法为 {(b1) …10)} 3、算法 //功能从m个元素元素不重复中取出n个元素n m的所有取法
//参数vectorHead 前nBit_x - 1个元素已取了的头部vector
//参数nHeadBit 当前处理的元素在vectorSet中的位置
//参数nBit_x 当前要处理的子集的元素位置
//参数nChildSetSize 要取的n个元素的子集的大小
//参数vectorSet m个元素的总集
//参数vectorChildSetBuffer 存放子集的buffer
//返回当前操作的步数
int GetChildSetByDec(std::vectorint vectorHead, int nHeadBit, int nBit_x, int nChildSetSize, std::vectorint vectorSet, std::vectorstd::vectorint vectorChildSetBuffer)
{int nRet 0;for (int i nHeadBit; i vectorSet.size(); i){nRet;std::vectorint vectorNewHead vectorHead;vectorNewHead.push_back(vectorSet[i]);if (nBit_x nChildSetSize - 1){//如果已经处理到最后一位了则添加到buffer中vectorChildSetBuffer.push_back(vectorNewHead);}else{//如果还没处理到最后一位则递归GetChildSetByDec(vectorNewHead, i 1, nBit_x 1, nChildSetSize, vectorSet, vectorChildSetBuffer);}}return nRet;
}//功能从m个元素元素不重复中取出n个元素n m的所有取法
//参数nChildSize 要取的n个元素的子集的大小
//参数vectorBuffer 存放所有数组的buffer
//参数vectorSet m个元素的总集
//返回无
void GetChildSet(std::vectorstd::vectorint vectorChildSetBuffer, std::vectorint vectorSet)
{//依次列出从1个元素到n个元素的集合for (int i 1; i vectorSet.size(); i){std::vectorint vectorHead;GetChildSetByDec(vectorHead, 0, 0, i, vectorSet, vectorChildSetBuffer);}
} 说明 这里用的 vectorChildAggregateBuffer 来存放返回的子集vectorChildAggregateBuffer 是一个STL容器中向量的向量如果没有用过STL可以理解为数组的指针Array[][],这里用Vector是为了存储操作方便。GetChildAggregateByDec() 函数即用递归实现上面例子中10个球中取3个球的所有取法遍历。GetChildAggregateByDec() 中运用了将n个元素映射为 Array[n] 数组一一对应的思想程序运行结果 如有其他思路解题欢迎大家跟帖讨论转载于:https://www.cnblogs.com/organic/p/5015246.html
