离散题:给一任意群,求其所有子群的算法。

来源:百度知道 编辑:UC知道 时间:2024/06/05 02:02:01
RT,紧急,谢谢~
请求详解,谢谢~~

讨论某个特定的子群, 对于群中的每一个元素, 只有两种状态: 在/不在子群中
所以, 通过变化每个元素的这个在与不在的bool标记, 就可以生成所有子群了
比如, 对于3个元素的群的子群, 全集就是全部元素都位于子群中即111, 只有前两个的时候就是110, 只有最后一个的子群是001
类似的, 对于任何多个元素的子群, 就通过改变每个元素的状态就可以生成所有子群了

下面的算法, 把整形变量的每一位看做元素的存在标记, 即第3位为1表示第三个元素在这个子群中:

#include <stdio.h>

int main()
{
unsigned iLen = 0;
puts("集合元素的个数?(1~31)");
scanf("%u", &iLen);
if (iLen > 31 || iLen <= 0)
{
puts("超出范围");
return -1;
}

FILE *pFile = fopen("out.txt", "w");
if (pFile == NULL)
{
puts("打开文件失败");
return -2;
}

unsigned iMax = 1 << iLen;
for (unsigned i = 1; i < iMax; ++i)
{
for (int j = 0; j < iLen; ++j)
{
if ((i >> j) & 1)
{
fp