【2014年の面接準備】再帰的な応用-配列組合せの実現

1.重複配列の問題がある
例題:3,2,1の3つの数字で1つの4桁を構成して、数字は繰り返すことができます.
ここでは明らかに3の4次方種の可能性があり,再帰的に以下のように実現できる.

void quanpailie1(int a[],int i,int n)
    {
         //i = n             
         if(i == n)
         {
              for(int i = 0;i < n; i++)
              {
                      cout << a[i] ;
              } 
                           
              count++;              
              cout<<endl; 
         }
         else
         {
             //            
             a[i] = 1;
             quanpailie1(a, i + 1, n);
             
             a[i] = 2;
             quanpailie1(a, i + 1, n);
             
             a[i] = 3;
             quanpailie1(a, i + 1, n);             
             
         }
    }

    int main()  
    {          
        int a[4];
        
        quanpailie1(a, 0, 4);
        cout<< "  " << pailie_num << "       !" <<endl;  
               
        system("PAUSE");          
        return 0;  
    }  

2.全サブセットを生成する組合せ問題
例題は{a 1,a 2,...,an}配列があり,その配列のすべての組合せを出力してみる.
ここでは、各数にサブセットを入れる場合と入れない場合の2つが得られる.
従って2のn次方種子セット(空セットを含む)が共にあり、空セットを含まなければ2のn次方減がある場合
Sample Input
4
1 2 3 4
Sample Output
1
12
123
1234
124
13
134
14
2
23
234
24
3
34
4

    //  a[]        ,
    //a[i] = 0   a2[i]   ,a[i] = 1   a2[i]   
    void quanzuhe(int a[],int i,int n,int a2[])
    {
         if(i == n)
         {
              int num = 0;              
              for(int i = 0;i < n; i++)
              {               
                      if(a[i] == 1) 
                      {       
                              cout << a2[i];
                              num++;
                      } 
              }                                         
              if(num != 0) cout<<endl; 
         }
         else
         {
             a[i] = 1;
             quanzuhe(a, i + 1, n, a2);
             
             a[i] = 0;
             quanzuhe(a, i + 1, n, a2);         
             
         }
    }

    int main()  
    {  
                
        int a[3];
        int a2[3] = {1,2,3};
        
        quanzuhe(a, 0, 3, a2);
               
        system("PAUSE");          
        return 0;  
    } 

3.指定された個数の組合せ問題を生成する
例えば{1,2,3,4,5}の3つを選択し,上記のコードを少し修正すれば実現できる.

    
    //  m          
    void zuhe(int a[],int i,int n,int a2[], int m)
    {
         if(i == n)
         {
              int num = 0;              
              for(int i = 0; i < n; i++)
              {               
                      if(a[i] == 1) 
                      {       
                              num++;
                      } 
              }
                                                       
              if(num == m)
              {
                     for(int i = 0; i < n; i++)
                     {               
                                     if(a[i] == 1) 
                                      {       
                                              cout<<a2[i];
                                      } 
                     }
                     cout<<endl;
              }
              
             
         }
         else
         {
             a[i] = 1;
             zuhe(a, i + 1, n, a2, m);
             
             a[i] = 0;
             zuhe(a, i + 1, n, a2, m);         
             
         }
    }

    int main()  
    {          
        int a[5];
        int a2[5] = {1,2,3,4,5};
        
        zuhe(a, 0, 5, a2, 3);
               
        system("PAUSE");          
        return 0;  
    }  
 

4.全配列問題

    
    static int g_sCnt = 0;  

    //permutation     .  
    void permutation(char* pStr, char* pBegin)  
    {  
           if(*pBegin == '\0')  
           {  
                  ++g_sCnt;  
                  cout << pStr << endl;  
           }  
           else  
           {  
                  for(char* pCh = pBegin; *pCh != '\0'; ++pCh)  
                  {  
                         //                  .  
                         char temp = *pCh;  
                         *pCh = *pBegin;  
                         *pBegin = temp;  
       
                         permutation(pStr,pBegin+1);  
                          
                         //     ，            .  
                         temp = *pCh;  
                         *pCh = *pBegin;  
                         *pBegin = temp;  
       
                  }//end for  
           }//end else  
    }  
    
    //         
    void permutation(char* pStr)  
    {  
        if(pStr== NULL)  
            {  
                  return;  
            }  
           else  
            {  
                  permutation(pStr,pStr);  
            }  
    }  
       
    int main()  
    {  
        char strSrc[] = "abc";  
        permutation(strSrc);  
        cout<< "  " << g_sCnt << "    !" <<endl;  
               
        system("PAUSE");          
        return 0;  
    }