星期日, 4月 08, 2012

求出n取k組合的列表 C++版

同樣是求出n取k組合的列表,今天要寫C++版本。

C++可以寫得很優雅,也可以像我一樣寫得像C。(我承認,真的太多年沒寫C++ XDDD)
以下是Combinations.h

#ifndef Combinations_Combinations_h
#define Combinations_Combinations_h
#include <string>
#include <list>
using namespace std;
        class Combinations
        {
            list<string> *calc(int all, int want);
        protected:
        private:
            void addList (char before[], char after[]);
            void calc(char before[], int all, int want);
            list<string> *result;
        };
#endif

以下是Combinations.cpp
#include <iostream>
#include "Combinations.h"
using namespace std;
    list<string> *Combinations::calc(int all, int want)
    {
        result = new list<string>();
        char fake[1];
        fake[0]=0;
        calc(fake, all, want);
        return result;
    }
    void Combinations::addList (char before[], char after[])
    {
        string temp;
        temp.append(before).append(after);
        result->push_back(temp);
    }
    void Combinations::calc(char before[], int all, int want)
    {
        int beforeLength = strlen(before);
        char strAll [all+1];
        strAll[all] =0;
        if(want == 0)
        {
            for(int i=0; i<all;i++)
            {
                strAll[i] = '0';
            }
            addList( before, strAll);
        }
        else if(all == want) {
            for(int i=0; i<all;i++)
            {
                strAll[i] = '1';
            }
            //Console.WriteLine("{0}{1}",  new string(before),  new string(strAll));
            addList( before, strAll);
        }
        else if(all == 1)
        {
            char allTemp[2];
            allTemp[1]=0;
            switch(want)
            {
                case 0:
                    //Console.WriteLine("{0}0", new string(before));
                    allTemp[0]='0';
                    break;
                case 1:
                    //Console.WriteLine("{0}1", new string(before));
                    allTemp[0]='1';
                    break;
            }
            addList( before, allTemp);
        }
        else // all must > want
        {
            char newbefore [beforeLength+2];
            for(int i=0; i< beforeLength; ++i)
            {
                newbefore[i] = before[i];
            }
            newbefore[beforeLength+1]=0;
            newbefore[beforeLength]='0';
            calc ( newbefore, all-1, want);
            newbefore[beforeLength]='1';
            calc ( newbefore, all-1, want-1);
        }
    }

以下是main.cpp
#include <iostream>
#include "Combinations.h"
using namespace std;
int main(int argc, const char * argv[])
{

    Combinations cb;

    list<string> *result = cb.calc(5, 1);
    for (list <string>::iterator str= result->begin ();  str != result->end (); str++)  {
        cout << *str << endl;
    }
    cout << "共:"<< result->size() <<"個" <<endl;
    return 0;
}

執行結果:
00001
00010
00100
01000
10000
共:5個

沒有留言: