關(guān)于C++，小編有自己的一些心得體會(huì)，曾深入的學(xué)習(xí)過(guò)，不過(guò)學(xué)無(wú)止境，也請(qǐng)C++高手多多指教～那接下來(lái)先附上這篇C++中求組合數(shù)的各種方法總結(jié)，想學(xué)習(xí)的同學(xué)，我們一起來(lái)了解下其中的詳情吧。C++

【問(wèn)題】????? 組合問(wèn)題

問(wèn)題描述：找出從自然數(shù)1、2、... 、n中任取r個(gè)數(shù)的所有組合。例如n=5，r=3的所有組合為:

1,2,3
1,2,4
1,3,4
2,3,4
1,2,5
1,3,5
2,3,5
1,4,5
2,4,5
3,4,5

用程序?qū)崿F(xiàn)有幾種方法:

1)窮舉法

程序如下
【程序】
#include
const int n=5,r=3;
int??? i,j,k,counts=0;

int main()
{
???? for(i=1;i<=r ;i++)
??????? for(j=i+1;j<=r+1;j++)
??????????? for( k=j+1;k<=r+2;k++){
?????????????? counts++;
?????????????? printf("%4d%4d%4d/n",i,j,k);
?????????? }
printf("%d",counts);
return 0;
}
但是這個(gè)程序都有一個(gè)問(wèn)題，當(dāng)r變化時(shí)，循環(huán)重?cái)?shù)改變，這就影響了這一問(wèn)題的解，即沒(méi)有一般性。

2)遞歸法
分析所列的10個(gè)組合，可以采用這樣的遞歸思想來(lái)考慮求組合函數(shù)的算法。
設(shè)函數(shù)為void??? comb(int m,int k)為找出從自然數(shù)1、2、... 、m中任取k個(gè)數(shù)的所有組
合。當(dāng)組合的第一個(gè)數(shù)字選定時(shí)，其后的數(shù)字是從余下的m-1個(gè)數(shù)中取k-1數(shù)的組合。這
就將求m個(gè)數(shù)中取k個(gè)數(shù)的組合問(wèn)題轉(zhuǎn)化成求m-1個(gè)數(shù)中取k-1個(gè)數(shù)的組合問(wèn)題。設(shè)函數(shù)引
入工作數(shù)組a[ ]存放求出的組合的數(shù)字，約定函數(shù)將確定的k個(gè)數(shù)字組合的第一個(gè)數(shù)字放
在a[k]中，當(dāng)一個(gè)組合求出后，才將a[ ]中的一個(gè)組合輸出。第一個(gè)數(shù)可以是m、m-1、
...、k，函數(shù)將確定組合的第一個(gè)數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去頂組
合的其余元素，繼續(xù)遞歸去確定；或因已確定了組合的全部元素，輸出這個(gè)組合。細(xì)節(jié)
見(jiàn)以下程序中的函數(shù)comb。
【程序】
#include
#include

using namespace std;

# define????? MAXN????? 100
int a[MAXN];
int counts=0;

void printtime(void) //打印當(dāng)前時(shí)間的函數(shù)
{
????? char tmpbuf[128];
????? time_t ltime;
????? struct tm *today;

????? time( ????? today = localtime( ????? strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);
????? cout<});

void????? comb(int m,int k)
{???? int i,j;
????? for (i=m;i>=k;i--)
????? {???? a[k]=i;
????????? if (k>1)
????????????? comb(i-1,k-1);
????????? else
????????? {??
????????????? counts++;
????????????? /*
????????????? for (j=a[0];j>0;j--)
????????????????? printf("%4d",a[j]);
????????????? printf("/n");
????????????? */
????????? }
????? }
}

int main()
{??

????? int m,r;
????? cout<<"m"<????? cin>>m;
????? cout<<"r"<????? cin>>r;
????? counts=0;
????? a[0]=r;
????? printtime();
????? comb(m,r);
????? cout<????? printtime();
????? return 0;
};
;

?

這是我在網(wǎng)上找到的程序，稍微修改了一下。程序?qū)懙暮芎?jiǎn)潔，也具有通用性，解決了問(wèn)題。

3)回溯法

采用回溯法找問(wèn)題的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r-1]
中，組合的元素滿足以下性質(zhì)：

（1）???? a[i+1]>a[i]，后一個(gè)數(shù)字比前一個(gè)大；
（2）???? a[i]-i<=n-r+1。
按回溯法的思想，找解過(guò)程可以敘述如下：
????? 首先放棄組合數(shù)個(gè)數(shù)為r的條件，候選組合從只有一個(gè)數(shù)字1開(kāi)始。因該候選
解滿足除問(wèn)題規(guī)模之外的全部條件，擴(kuò)大其規(guī)模，并使其滿足上述條件（1），候選組合
改為1，2。繼續(xù)這一過(guò)程，得到候選組合1，2，3。該候選解滿足包括問(wèn)題規(guī)模在內(nèi)的全
部條件，因而是一個(gè)解。在該解的基礎(chǔ)上，選下一個(gè)候選解，因a[2]上的3調(diào)整為4，以
及以后調(diào)整為5都滿足問(wèn)題的全部要求，得到解1，2，4和1，2，5。由于對(duì)5不能再作調(diào)
整，就要從a[2]回溯到a[1]，這時(shí)，a[1]=2，可以調(diào)整為3，并向前試探，得到解1，3，
4。重復(fù)上述向前試探和向后回溯，直至要從a[0]再回溯時(shí)，說(shuō)明已經(jīng)找完問(wèn)題的全部
解。

在網(wǎng)上我始終沒(méi)有找到可以正常執(zhí)行的完整程序，所以我只好花了一天的時(shí)間來(lái)自己來(lái)寫(xiě)這個(gè)程序，并且改變輸出從0開(kāi)始而不是從1開(kāi)始，這樣做的目的是 為了擴(kuò)展程序的用途，適應(yīng)c/c++語(yǔ)言的需要，這樣輸出就可以當(dāng)作要選擇的組合數(shù)組的地址序列，可以對(duì)長(zhǎng)度為n任意類型數(shù)組找出r個(gè)組合。我對(duì)它進(jìn)行了 優(yōu)化，如果你認(rèn)為還有可以優(yōu)化的地方，請(qǐng)不惜賜教,。^_^

#include
#include
#include
using namespace std;

# define????? MAXN????? 100
int a[MAXN]; //定位數(shù)組,用于指示選取元素集合數(shù)組的位置，選取元素集合數(shù)組0 起始
void comb(int m,int r)
{??
????? int cur;//指示定位數(shù)組中哪個(gè)成員正在移進(jìn)

????? unsigned int count=0;

????? //初始化定位數(shù)組，0 起始的位置 ，開(kāi)始的選擇必是位置 0，1，2
????? for(int i=0;i????????? a[i]=i;;i++)

????? cur=r-1;//當(dāng)前是最后一個(gè)成員要移進(jìn)

?????? do{
????????? if (a[cur]-cur<=m-r ){?

????????????? count++;
????????????? /*
????????????? for (int j=0;j????????????????? cout<????????????? cout<????????????? */
????????????? a[cur]++;

????????????? continue;
????????? }
????????? else{
????????????? if (cur==0){
????????????????? cout<????????????????? break;
????????????? };
(4);j++)

????????????? a[--cur]++;
????????????? for(int i=1;i????????????????? a[cur+i]=a[cur]+i;
????????????? };i++){

????????????? if(a[cur]-cur????????????????? cur=r-1;???????????????
????????? }
????? }while (1);
})

?

?

void printtime(void) //打印當(dāng)前時(shí)間的函數(shù)
{
????? char tmpbuf[128];
????? time_t ltime;
????? struct tm *today;

????? time( ????? today = localtime( ????? strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);
????? cout<});

int main (int argc, char *argv[])
{

????? int m,r;
????? cout<<"m"<????? cin>>m;
????? cout<<"r"<????? cin>>r;
????? printtime();
????? comb(m,r);???
????? printtime();
????? return(0);
};
;

同上面的遞歸的程序進(jìn)行比較，同樣用g++ o2優(yōu)化。當(dāng)n=40，r=11，屏蔽掉輸出，得到的結(jié)果都是2311801440項(xiàng)，遞歸程序用了23至24秒，回溯用了19至20秒。

4）利用數(shù)組

? 定義：從n個(gè)數(shù)中取出m個(gè)數(shù)的組合。
? 實(shí)現(xiàn)機(jī)理：先創(chuàng)建一個(gè)字符串?dāng)?shù)組，其下標(biāo)表示 1 到 n 個(gè)數(shù)，數(shù)組元素的值為1表示其下標(biāo)代表的數(shù)被選中，為0則沒(méi)選中。????
??? 然后初始化，將數(shù)組前 m 個(gè)元素置 1，表示第一個(gè)組合為前 m 個(gè)數(shù)。????
??? 然后從左到右掃描數(shù)組元素值的 10 組合，找到第一個(gè) "10" 后交換 1 和 0 的位置,變?yōu)?01，而后將該10組合前的1和0重新組合（1放在前邊，其個(gè)數(shù)為10組合前1的個(gè)數(shù)，0放在后邊，其個(gè)數(shù)為10前0的個(gè)數(shù)，而后接10的倒轉(zhuǎn)組合 01）。當(dāng)m 個(gè) 1 全部移動(dòng)到最右端時(shí)，就得到了最后一個(gè)組合。????
??? 例如求 5 中選 3 的組合：????
??? 1???? 1???? 1???? 0???? 0???? //1,2,3????
??? 1???? 1???? 0???? 1???? 0???? //1,2,4????
??? 1???? 0???? 1???? 1???? 0???? //1,3,4????
??? 0???? 1???? 1???? 1???? 0???? //2,3,4????
??? 1???? 1???? 0???? 0???? 1???? //1,2,5????
??? 1???? 0???? 1???? 0???? 1???? //1,3,5????
??? 0???? 1???? 1???? 0???? 1???? //2,3,5????
??? 1???? 0???? 0???? 1???? 1???? //1,4,5????
??? 0???? 1???? 0???? 1???? 1???? //2,4,5????
??? 0???? 0???? 1???? 1???? 1???? //3,4,5??

以上就是C++中求組合數(shù)的幾種方法總結(jié)，如果大家想了解更多相關(guān)內(nèi)容，請(qǐng)持續(xù)關(guān)注本站，本站小編將在第一時(shí)間為大家?guī)?lái)更好的經(jīng)典內(nèi)容。