一道简单的题，估计是思路有问题 - 编程论坛

#2

realfree2009-07-22 14:22

你这个思路基本上是完全错误的

，而且这貌似也不是一道特别简单的题

[[it] 本帖最后由 realfree 于 2009-7-22 14:24 编辑 [/it]]

#3

mfkblue2009-07-22 16:46

基本上是照书抄的。跟着代码在纸上画了下，第一次输是abc不错，第二次输出时,k=0;i=1, 交换后list="bac" 所以输出时应该也是bac，但实际运行不是的，这题真难懂。
#include <iostream.h>
#include <stdlib.h>
inline swap(char &a,char &b)
{
char t=a;
a=b;
b=t;
}

void sub(char list[],int k,int m)
{
    int i;
    if(k==m)
    {
        for(i=0;i<=m;i++)
            cout<<list[i];
        cout<<endl;
    }
    else
    {
        for(i=k;i<=m;i++)
        {
        swap(list[k],list[i]);
        sub(list,k+1,m);
        swap(list[k],list[i]);
        }
    }
}

void main()
{
    char list[]="abc";
    sub(list,0,3);
}

#4

pangding2009-07-22 21:26

回复 3楼 mfkblue

嗯，我也觉得不是一道很简单的题。呵呵~

#5

mfkblue2009-07-22 22:45

大家都说看完c和c++的基础后要看看数据结构，这就是数据结构的算法应用第一章的题目。

#6

leeco2009-07-22 22:57

程序代码：

char a[]="abcd";

const int n=sizeof(a)-1;
int x[sizeof(a)];

void dfs(int d)
{
    putchar('{');
    for(int i=0;i<d;i++)
    {
        putchar(a[x[i]]);
    }
    putchar('}');
    putchar('\n');
    if(d==n) return ;
    for(int i=(d?x[d-1]+1:0);i<n;i++)
    {
        x[d]=i;
        dfs(d+1);
    }
}

int main()
{
    dfs(0);
}

#7

pangding2009-07-23 11:23

回复 6楼 leeco

嗯，漂亮

我昨天晚上了也想了半天这题。想到的方法和你有点像，但我用的是循环不是递归，不太符合题目要求。但是可以按楼主说的顺序输出。不过现在还没写好~ 嘿嘿，我有空再试试，可能没你的方法好~

#8

pangding2009-07-23 11:59

回复 7楼 pangding

写好了~

程序代码：

#include <stdio.h>

#define N 5
char s[N] = { 'a', 'b', 'c', 'd', 'e' };
int index[N];

void __put(int k)  // 辅助函数，用于输出形如“{***}”的格式。
{
    putchar('{');
    for (int i = 0; i < k; i++)
        putchar(s[index[i]]);
    putchar('}'); putchar('\n');
}
bool __inc(int n, int k)  // 辅助函数。用于sub_aux。计算不重复的脚标。
{
    int j = k - 1;
    if (++index[j] < n) return true;

    while (j > 0) {
        --j, --n;
        if (++index[j] < n) {
            while (++j < k)
                index[j] = index[j-1] + 1;
            return true;
        }
    }
    return false;
}

void sub_aux(int n, int k)  // 这个函数的是，把一个含有n个元素的集合的所有含有元素个数为k的子集输出。
{
    for (int i = 0; i < k; i++)
        index[i] = i;
    do {
        __put(k);
    } while(__inc(n, k));
}

void sub(int n)
{
    puts("{}");    // 先输出空集。
    for (int i = 1; i <= n; i++)
        sub_aux(n, i);   // 输出n元集的i元子集。
}

int main()
{
    sub(N);

    return 0;
}

嘿嘿，再加点注释，我这个編的不好，算法没有Le同学的清楚~

[[it] 本帖最后由 pangding 于 2009-7-23 12:06 编辑 [/it]]

#9

ET_bug2009-07-23 12:21

leeco同学的代码很高效，短小精悍，值得学习呀！！！

当然pangding版主自强不息，致力原创，也是精神可嘉！！嘿嘿

#10

ET_bug2009-07-23 12:23

呃。。发错图片了！！应该是

才对

#11

pangding2009-07-23 16:02

回复 10楼 ET_bug

呵呵，多谢支持~

#12

mfkblue2009-07-23 21:31

如果不是你们俩人夸他，我还在怀疑中，这代码是不是有问题。
而且我还没看懂leeco写的代码。

#13

ET_bug2009-07-23 22:00

你没运行吗?我运行可以得到下面的结果..leeco是个牛人呀.敬仰...

{}
{a}
{ab}
{abc}
{abcd}
{abd}
{ac}
{acd}
{ad}
{b}
{bc}
{bcd}
{bd}
{c}
{cd}
{d}
请按任意键继续. . .

#14

mfkblue2009-07-23 22:31

回复 13楼 ET_bug

for(int i=(d?x[d-1]+1:0);i<n;i++) 这句话编译不过去

#15

ET_bug2009-07-23 22:36

回复 14楼 mfkblue

.....我的没问题呀!!

#16

mfkblue2009-07-23 22:40

pangding的输出还蛮正常，可不是递归.
if (++index[j] < n) 这句也看不懂

这道题还真不是一道简单题

#17

bmc2009-07-24 00:10

顶下8楼和10楼的前辈，好代码

#18

pangding2009-07-24 00:39

以下是引用mfkblue在2009-7-23 22:31的发言：

for(int i=(d?x[d-1]+1:0);i<n;i++) 这句话编译不过去

编译器给的错误提示是什么？

#19

莫云今次2009-07-24 01:18

简单的回溯法
#include <iostream.h>
const int Maxn = 32;
bool flag[Maxn];
void PowerSet(int i,int n) {
    int j;
    if (i>n) { //输出幂集的一个元素；
         for(j=1;j<=n;j++)
                    if (flag[j] == true)  cout<<j;
              cout<<endl;
    }
    else {  flag[i] = true;   //取第i个元素；
              PowerSet(i+1,n);
           flag[i] = false;   //不取第i个元素；
           PowerSet(i+1,n);
    }
void main()
{   int i;
     for(i=0;i<Maxn;i++)
          flag[i] = false;
      PowerSet(1,5);
}

#20

mfkblue2009-07-24 16:21

回复 18楼 pangding

for(i=(d?x[d-1]+1:0);i<n;i++) 错误只是重复定义了，去掉int后输出也正常了.这步没看明白什么作用，昨天事多比较忙,连为什么错都没看见，现再来慢慢研究下.

[[it] 本帖最后由 mfkblue 于 2009-7-24 16:33 编辑 [/it]]

#21

fjwddzzc1232009-07-24 16:34

回复 20楼 mfkblue

有赋值当d=0时 i=0 则 x[d]=i也就是 x[0]=0 后面 d=1时 x[d-1]也就是 x[0] 都有被赋值

#22

mfkblue2009-07-24 17:45

leeco的代码从四点多一直用debug一步步看到现在，还是改了下，把 i=(d?x[d-1]+1:0);这句拆了放在for循环的上面，不然每次进for循环时都头晕。基本明白了程序怎么走的，但可以肯定的是，这个距离差太远了，看的心情一步步走底啊。x[]里面的值走的太厉害了。背下他的代码是没问题，想到这个思路就不太可能了

#23

fjwddzzc1232009-07-24 19:08

...debug 是什么我还不知道哎差距啊心情一步步走到底啊

#24

mfkblue2009-07-24 22:16

回复 19楼莫云今次

简单的回溯

递归里面还要调用两次，想跟着走一遍都难，调用五次以后就找不清楚返回到哪一步了。

#25

黯然神伤2009-07-24 22:23

我也得好好学学~~~编程无极限啊

#26

pangding2009-07-24 23:09

回复 24楼 mfkblue

感觉像这种递归的不能全靠跟走，那样了解算法运行的过程可能还行，但想自己写出来就难了。比如简单的Fib数列都很难知道它是怎么递归算的，但并不一定非得知道是怎么算的才能写出来。
主要是想原理。比如你说莫云姐写的那个可以这么想：
对于第i个元素，所有的子集能分成两类，一类是包括这个元素的，一类是不包括的。
比如{abc}这个集合，对于a它的子集可以分成这两类：
{a}     {}
{ab}    {b}
{ac}    {c}
{abc}   {bc}
这8个。而且这么分不重不漏(幂集定理其实就是这么证的~)
于是这个问题可以化简为找出{bc}的所有子集。
它的所有子集其实就是右边那列，如果可以找的出，{abc}的所有子集就是{bc}的全部子集，加上每个都加一个a的。

按这个思路就可以把求一个n元集的幂集转化为求一个n-1元集的幂集。空集只有空集这一个子集(空集定理)。所以就可能递归了~

呵呵，大概说说，我也是看她的代码想的，不代表她本人的想法~

#27

pangding2009-07-24 23:21

回复 24楼 mfkblue

我说说我的那个想法，其实这几个里，我那个可能是最容易理解的(我觉得

)。

看看你给的例子，就知道求子集可以按照子集的基数找。先找出空集，基数为0。然后再找单元集，再找找双元集，三元集……

于是，要编一个辅助函数，找一个n元集的k元子集。当然考虑到这个函数比较有用(因为有时候可能需要一个k元子集，所有把这个功能单拿出来还是有一定意义的~)

然后就得看这样的子集怎么找了。观察一下规律：
如果我是12345这个集合，找三元子集，怎么找？最有规律的写法可能是像以下这样：
123
124
125
134
135
145
234
235
245
345
一共10个，肯定找齐了。如果把它们看成数的话是不是由小到大的？这样就不会重不会漏了。有点像数位间不许重复的5进制一样~
编一个函数，根据n和k，能把符合这样规律的数找出来就行了。在我那里是 __inc 这个函数。由于只是辅助功能，用双下划线开的头，其实这不是好习惯，而且取inc这个名字也很不妥当(increse，简称inc），很可能与保留的某个函数重名。呵呵

#28

pangding2009-07-24 23:27

回复 27楼 pangding

其实我一开始也想用递归的，方法可能和莫云姐那个很像。不过想了一下，就换方法了，因为感觉后来写的那个好一点(输出也好控制，效率可能也高一点)。

不过当时要是能想到Le同学的递归方法，我可能就不优化了，感觉已经很方便了。而且效率不低。

#29

mfkblue2009-07-24 23:53

回复 26楼 pangding

你说到abc,就是找出bc所以的子集，再加a，就abc所有的子集，这个道理就是我现在看的书上讲的一样了，道理是明白了，写起来就糊涂了.
fib那个里虽然也调用两次，但是因为按照公式写的，倒是很快写出来了。
你写的这道题的代码我还没认真看，今天就看他们那两个人代码去了。结论是跟昨天没看差不多,云山雾绕，稀里糊涂.
我没考虑不用递归的办法，但我估计应该是能写出来的，不太确定

#30

leeco2009-07-26 16:18

回复 29楼 mfkblue

我写了一个更飘逸的和你题目里给的输出顺序一样的代码

程序代码：

#include <iostream>
#include <queue>
using namespace std;

char a[]="abc";
const int n=sizeof(a)-1;

void Out(int data)
{
    putchar('{');
    for(int i=0;i<n;i++)
    {
        if(data&(1<<(n-1-i)))
        {
            putchar(a[i]);
        }
    }
    putchar('}');
    putchar('\n');
}

void bfs()
{
    queue<int> Q;
    Q.push(1<<n);
    while(!Q.empty())
    {
        int t = Q.front();
        Q.pop();
        Out(t);
        for(int i=((t&(-t))>>1); i; i>>=1)
        {
            Q.push(t | i);
        }
    }
}

int main()
{
    bfs();
}

#31

leeco2009-07-26 16:19

回复 29楼 mfkblue

忘了强调这个是非递归的了，补充一下

#32

pangding2009-07-27 00:04

回复 31楼 leeco

呵呵，真不容易想出这种写法。一题多解，这算是很锻炼了

#33

mfkblue2009-07-31 21:24

queue 第一次看见这个头文件啊。
不知道用法，代码更加看不懂了...
ctrl+c以后再看!

#34

black4232009-08-11 11:19

学习了

#35

夜罗刹2009-08-11 12:08

回复 30楼 leeco

真的是很飘逸....queue解决这个问题还真是有用，受教了...

#36

罗罗小菜鸟2009-08-11 20:05

Lecco同学的递归玩得太帅啦！

#37

罗罗小菜鸟2009-08-11 20:06

啊，不是递归啊，见识太浅薄啦！呵呵

#38

qbhainan2009-08-13 16:56

牛人呀