C++中求組合數(shù)的各種方法總結(jié)詳解
【問(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<stdio.h>
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 <time.h>
#include <iostream>
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(<ime);
today = localtime(<ime );
strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);
cout<<tmpbuf<<endl;
}
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"<<endl;
cin>>m;
cout<<"r"<<endl;
cin>>r;
counts=0;
a[0]=r;
printtime();
comb(m,r);
cout<<counts<<endl;
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 <time.h>
#include <iostream>
#include <iomanip>
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<r;i++)
a[i]=i;
cur=r-1;//當(dāng)前是最后一個(gè)成員要移進(jìn)
do{
if (a[cur]-cur<=m-r ){
count++;
/*
for (int j=0;j<r;j++)
cout<<setw(4)<<a[j];
cout<<endl;
*/
a[cur]++;
continue;
}
else{
if (cur==0){
cout<<count<<endl;
break;
}
a[--cur]++;
for(int i=1;i<r-cur;i++){
a[cur+i]=a[cur]+i;
}
if(a[cur]-cur<m-r)
cur=r-1;
}
}while (1);
}
void printtime(void) //打印當(dāng)前時(shí)間的函數(shù)
{
char tmpbuf[128];
time_t ltime;
struct tm *today;
time(<ime);
today = localtime(<ime );
strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);
cout<<tmpbuf<<endl;
}
int main (int argc, char *argv[])
{
int m,r;
cout<<"m"<<endl;
cin>>m;
cout<<"r"<<endl;
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
相關(guān)文章
用C++實(shí)現(xiàn)strcpy(),返回一個(gè)char*類型的深入分析
本篇文章是對(duì)用C++實(shí)現(xiàn)strcpy(),返回一個(gè)char*類型進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05嵌入式C語(yǔ)言查表法在項(xiàng)目中的應(yīng)用
今天小編就為大家分享一篇關(guān)于嵌入式C語(yǔ)言查表法在項(xiàng)目中的應(yīng)用,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-12-12C語(yǔ)言解決青蛙跳臺(tái)階問(wèn)題(升級(jí)版)
所謂的青蛙跳臺(tái)階問(wèn)題,就是指一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。本文將用C語(yǔ)言解決這一問(wèn)題,需要的可以參考一下2022-01-01c++ 內(nèi)聯(lián)函數(shù)和普通函數(shù)的區(qū)別
內(nèi)聯(lián)函數(shù)是c++為了提高程序的運(yùn)行速度做的改進(jìn),那么內(nèi)聯(lián)函數(shù)和普通函數(shù)的區(qū)別是什么,本文就來(lái)詳細(xì)的介紹一下,感興趣的朋友可以了解一下2021-05-05在Visual Studio中配置C++最新版netCDF庫(kù)的方法
本文介紹在Windows電腦的Visual Studio軟件中,配置C++ 語(yǔ)言最新版netCDF庫(kù)的方法,文中通過(guò)圖文結(jié)合的形式介紹的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下2024-03-03