C++递归求解N个元素的所有子集

  我在复习C++遇到了设计递归函数的问题。这个例子,很好的显示了设计递归的方式,思想。

  这与斐波那数列不同,这个例子更有应用意义。

问题:

试编写一个递归函数,用来输入n个元素的所有子集。

  例如:三个元素{a,b,c}

  输出:

  {a,b,c}

  {ab}

  {ac}

  {bc}

  {a}

  {b}

  {c}

  {}

设计思路:
 
  首先,递归是使用的if else结构。
 
  然后,就是if中填条件,再在else写调用自身的函数。  
  详细思路,请看代码。

代码:

#include <string.h>
#include
<iostream> using namespace std;

void build(char str[],int n)
{
   
if(n==0)//控制输出
    {
        cout
<<"{";
       
for(int i=0;i<5;++i)
           
if(str[i]!=' ')
                {
                    cout
<<str[i];
                }
        cout
<<"}"<<endl;
    }
   
else
    {
       
/*** 先递归 ***/
        build(str,n
-1);
       
if(n>0)
        {
           
char newstr[5] = {' '};//去掉就把该位置的元素置成空
            /*** 还原之前的状态 ***/ strcpy(newstr,str); /*** 越来越少的元素 ***/
            newstr[n
-1]= ' ';
           
/*** 再次递归 ***/
            build(newstr,n
-1);
        }
    }
}

测试代码:

/***
将整个搜索过程表示为搜索树的形式,问题自然就很简单了。

每一个元素对于一个子集来说,只有两中状态:0表示不属于该子集,1表示属于该子集。
程序中的数组a就是采用这种表示。
因此,搜索过程表示为树的形式就是这样的:

a
0/ \1
b c
0/ \1 0/ \1
...........

因此:
代码中的第一个“trail(t,i+1,n);”就是搜索当前扩展节点的左子树(因为a[i]此时的值为0)。
代码中的“a[i]=1-a[i];”就是变换当前扩展节点的状态,也就是从左子树换到右子树。
代码中的第二个“trail(t,i+1,n);”就是搜索当前扩展节点的右子树。

**
*/
#include
<string.h>
#include
<iostream>
using namespace std;

void build(char str[],int n)
{
   
if(n==0)//控制输出
    {
        cout
<<"{";
       
for(int i=0;i<5;++i)
           
if(str[i]!=' ')
                {
                    cout
<<str[i];
                }
        cout
<<"}"<<endl;
    }
   
else
    {
       
/*** 先递归 ***/
        build(str,n
-1);
       
if(n>0)
        {
           
char newstr[5] = {' '};//去掉就把该位置的元素置成空
            /*** 还原之前的状态 ***/
            strcpy(newstr,str);
           
/*** 越来越少的元素 ***/
            newstr[n
-1]= ' ';
           
/*** 再次递归 ***/
            build(newstr,n
-1);
        }
    }
}

int main()
{
   
char string[5]= "abc ";//实例集合放在数组中
    build(string,3);
   
return 0;
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/29c63b5af634323135fadff4e2e3585f.html