求解递归过程

死幽亡灵

求字符串子集，能实现。求讲解递归过程

#include <conio.h>
#include <iostream>
using namespace std;
char *collect = { "abcd" };
int init[100];//max = 100
int len = strlen( collect );
void doSet( int num )
{
         if( num == 0 )

         {
                 for( int i = 0; i< len; i++ )

         if( init[i] == 0 )

                 cout<<collect[i];

         cout<<endl;
         return;
         }

         for( int i = 0; i<=1; i++ )
                {
                         init[len-num] = i;
                                printf("%d ",i);
                       
                        doSet( num -1 );   
                 }
}
int  main()
{                printf("%d",len);
                doSet( len );
                getch();
                return 0;
}

大神、朋友帮帮忙

n0noper

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

char *collect = { "abcd" };
int init[100];//max = 100 
int len = strlen( collect );

void doSet( int num ) 
{ 
        if( num == 0 )
        { 
                for (int n = 0; n < len; ++n)                // ADD AT 2016-3-2 BY n0noper NOTE:添加这一句输出，结果就非常明显了
                        cout << init[n] << " ";
                
                for( int i = 0; i< len; i++ )
                {
                        if( init[i] == 0 )
                                cout<<collect[i]; 
                }
                        
                cout<<endl; 
                return; 
        } 
        
        for( int i = 0; i<=1; i++ )                                // 每一位分为0/1两个状态，0为显示，1为不显示
        {
                init[len-num] = i; 
                
//                printf("%d ",i);                                        // LOGOUT AT 2016-3-2 BY n0noper
                
                doSet( num -1 );    
        } 
} 
int  main() 
{                
        printf("%d\n",len);
        doSet( len ); 
        getch(); 
        return 0;
}
/*
        算法使用"排列组合"实现。 这么理解就容易了：四个学生A、B、C、D，他们都会抽烟，同一时刻，他们四人的抽烟状态(正在抽/没有抽)组合有多少种情况？
        
        再如例子程序，例如：字符串abc，字串一共几种？ (根据程序思想，建立用于显示的数组Show[len]，len为字符串长度)
        1. 当字符串第一位a显示时，第二位b则有两种可能：显示(值为0)、不显示(值为1);当第二位b为显示时，第三位c也有两种可能：显示或不显示。                // 每一位的后一位可能性判断和处理相同，所以写成了递归
                Show[0]=0, Show[1]=0, Show[2]=0;        // abc都显示
                Show[0]=0, Show[1]=0, Show[2]=1;        // c不显示
                Show[0]=0, Show[1]=1, Show[2]=0;        // b不显示
                ...

        2. 当字符串第一位a不显示时，第二位b也是两种可能：显示与不显示;此时，第三位c重新计算，又有两种可能：显示或不显示。
                Show[0]=1, Show[1]=0, Show[2]=0;        // abc都显示
                Show[0]=1, Show[1]=0, Show[2]=1;        // c不显示
                Show[0]=1, Show[1]=1, Show[2]=0;        // b不显示
                ...

        这种排列组合题目，注意改变的唯一性。字符串四个字符，保证其中三个不变，只变化一个就容易理解了。
*/

死幽亡灵

结果
来看是这样，程序怎么压栈怎么出栈，给我说说吧，谢谢，帮人帮到底

n0noper

不知道你想知道这个程序里init模拟的栈操作？还是想知道递归程序的栈操作？
       
这里简单说一下init模拟的栈操作:        (程序中把init数组看做一个栈)
num=4, init[0]=0    [0|                        // 最后为栈模拟图，←为压栈，压入的为i的值
num=3, init[1]=0    [0|0|             
num=2, init[2]=0    [0|0|0|
num=1, init[3]=0    [0|0|0|0|

    for循环中，再次调用doSet时，num-1为0，此时即根据init的值打印出一个字串。
    然后，doSet执行完毕，回到for循环(此时num为1)，i递增，栈如下：

num=1, init[3]=1    [0|0|0|1|

  上述两步就完成了一次压栈、出栈。因为一个数组元素替换就相当于先将栈顶元素(init[len-num])取出，然后将另一个值
  放入到原来位置。容易理解的代码如下：
  for中的操作
        init.push(i);        // i压入栈顶
        doSet(num-1);

  doSet()中的操作为:
        if (0 == num)
        {
                ... // 显示子串
                init.pop();        // 栈顶元素出栈
        }


不知道你想知道的是不是这个，其实这种东西纸笔一画就得到了，这样写出来反而不容易理解。如果不明白，咱们可以录个视频，理解了就算了。

也不知道你学到什么程度了，可能说的有点肤浅，说得不好的地方见谅哈。有什么问题，再讨论。


        注：盆友，我等级不够，加不了好友，骚瑞！

死幽亡灵

也好吧，麻烦你了

jzh823

踩踩