求解递归过程

死幽亡灵

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

#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

1. #include <conio.h>
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. char *collect = { "abcd" };
   
6. int init[100];//max = 100
   
7. int len = strlen( collect );
   
8. 
   
9. void doSet( int num )
   
10. {
    
11.         if( num == 0 )
    
12.         {
    
13.                 for (int n = 0; n < len; ++n)                // ADD AT 2016-3-2 BY n0noper NOTE:添加这一句输出，结果就非常明显了
    
14.                         cout << init[n] << " ";
    
15.                
    
16.                 for( int i = 0; i< len; i++ )
    
17.                 {
    
18.                         if( init[i] == 0 )
    
19.                                 cout<<collect[i];
    
20.                 }
    
21.                        
    
22.                 cout<<endl;
    
23.                 return;
    
24.         }
    
25.        
    
26.         for( int i = 0; i<=1; i++ )                                // 每一位分为0/1两个状态，0为显示，1为不显示
    
27.         {
    
28.                 init[len-num] = i;
    
29.                
    
30. //                printf("%d ",i);                                        // LOGOUT AT 2016-3-2 BY n0noper
    
31.                
    
32.                 doSet( num -1 );   
    
33.         }
    
34. }
    
35. int  main()
    
36. {               
    
37.         printf("%d\n",len);
    
38.         doSet( len );
    
39.         getch();
    
40.         return 0;
    
41. }
    
42. /*
    
43.         算法使用"排列组合"实现。 这么理解就容易了：四个学生A、B、C、D，他们都会抽烟，同一时刻，他们四人的抽烟状态(正在抽/没有抽)组合有多少种情况？
    
44.        
    
45.         再如例子程序，例如：字符串abc，字串一共几种？ (根据程序思想，建立用于显示的数组Show[len]，len为字符串长度)
    
46.         1. 当字符串第一位a显示时，第二位b则有两种可能：显示(值为0)、不显示(值为1);当第二位b为显示时，第三位c也有两种可能：显示或不显示。                // 每一位的后一位可能性判断和处理相同，所以写成了递归
    
47.                 Show[0]=0, Show[1]=0, Show[2]=0;        // abc都显示
    
48.                 Show[0]=0, Show[1]=0, Show[2]=1;        // c不显示
    
49.                 Show[0]=0, Show[1]=1, Show[2]=0;        // b不显示
    
50.                 ...
    
51. 
    
52.         2. 当字符串第一位a不显示时，第二位b也是两种可能：显示与不显示;此时，第三位c重新计算，又有两种可能：显示或不显示。
    
53.                 Show[0]=1, Show[1]=0, Show[2]=0;        // abc都显示
    
54.                 Show[0]=1, Show[1]=0, Show[2]=1;        // c不显示
    
55.                 Show[0]=1, Show[1]=1, Show[2]=0;        // b不显示
    
56.                 ...
    
57. 
    
58.         这种排列组合题目，注意改变的唯一性。字符串四个字符，保证其中三个不变，只变化一个就容易理解了。
    
59. */

复制代码

死幽亡灵

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

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

踩踩