跳到主要內容

求出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個

留言

這個網誌中的熱門文章

在Windows Server設定L2TP over IPSec VPN

簡單地說,macOS Sierra與iOS 10發表後,大家忽然發現Apple不再支援PPTP,所以一定得設定其他的VPN型態。若不要另外裝client,用L2TP是最方便的,SSL VPN雖然好,但若沒有安裝Agent要連線到任一電腦或是非網頁服務還是挺麻煩的。

自然人憑證讀卡機驅動程式

鳥毅用的是第一代的自然人憑證讀卡機,EZ100PU(後來有同事買EZmini可以讀SIM卡似乎更好),每年報稅時用一次。 本來只是要申請些政府業務,一時之間找不到光碟,沒想到在 驅動程式下載 居然看到Linux和Mac的驅動程式,剩下的就是政府單位的網頁和程式應該改版了吧!!!

DBeaver 介面語言

DBeaver是我個人頗常用的一套跨平台Database管理工具,最近升級後發現Windows版本居然變成簡體中文,而且無法切換為英文。