歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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;
}

其實,設計遞歸的關鍵是如何設計。想不到,就百度。看代碼也是個快樂的過程,關鍵是仔細思考。
 
囫囵吞棗,對於程序員是要不得了。如果你無法做到,用手到後拈來。那麼,你學習這個東西是失敗的!

Copyright © Linux教程網 All Rights Reserved