`
doujiu
  • 浏览: 88360 次
  • 性别: Icon_minigender_1
  • 来自: 哈尔滨
社区版块
存档分类
最新评论

求组合数的几种方法

阅读更多
C++求组合数 - johnchangbo的专栏 - CSDN博客

【问题】 组合问题
问题描述:找出从自然数1、2、... 、n中任取r个数的所有组合。例如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

用程序实现有几种方法:
1)穷举法

程序如下
【程序】
#include<stdio><br>const int n=5,r=3;<br>int i,j,k,counts=0;<br><br>int main()<br>{<br> for(i=1;i&lt;=r ;i++)<br> for(j=i+1;j&lt;=r+1;j++)<br> for( k=j+1;k&lt;=r+2;k++){<br> counts++;<br> printf("%4d%4d%4d\n",i,j,k);<br> }<br>printf("%d",counts);<br>return 0;<br>}<br>但是这个程序都有一个问题,当r变化时,循环重数改变,这就影响了这一问题的解,即没有一般性。<br><br><br>2)递归法<br>分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。<br>设函数为void comb(int m,int k)为找出从自然数1、2、... 、m中任取k个数的所有组<br>合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这<br>就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引<br>入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放<br>在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、<br>...、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组<br>合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节<br>见以下程序中的函数comb。<br>【程序】<br>#include <time><br>#include <iostream><br><br>using namespace std;<br><br># define MAXN 100<br>int a[MAXN];<br>int counts=0;<br><br>void printtime(void) //打印当前时间的函数<br>{<br> char tmpbuf[128];<br> time_t ltime;<br> struct tm *today;<br><br> time(&amp;ltime);<br> today = localtime(&amp;ltime );<br> strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);<br> cout&lt;<tmpbuf>&lt;<endl><br>}<br><br><br>void comb(int m,int k)<br>{ int i,j;<br> for (i=m;i&gt;=k;i--)<br> { a[k]=i;<br> if (k&gt;1)<br> comb(i-1,k-1);<br> else<br> { <br> counts++;<br> /*<br> for (j=a[0];j&gt;0;j--)<br> printf("%4d",a[j]);<br> printf("\n");<br> */<br> }<br> }<br>}<br><br>int main()<br>{ <br><br> int m,r;<br> cout&lt;&lt;"m"&lt;<endl><br> cin&gt;&gt;m;<br> cout&lt;&lt;"r"&lt;<endl><br> cin&gt;&gt;r;<br> counts=0;<br> a[0]=r;<br> printtime();<br> comb(m,r);<br> cout&lt;<counts>&lt;<endl><br> printtime();<br> return 0;<br>}<br><br><br>这是我在网上找到的程序,稍微修改了一下。程序写的很简洁,也具有通用性,解决了问题。<br><br>3)回溯法<br><br>采用回溯法找问题的解,将找到的组合以从小到大顺序存于a[0],a[1],…,a[r-1]<br>中,组合的元素满足以下性质:<br><br>(1) a[i+1]&gt;a[i],后一个数字比前一个大;<br>(2) a[i]-i&lt;=n-r+1。<br>按回溯法的思想,找解过程可以叙述如下:<br> 首先放弃组合数个数为r的条件,候选组合从只有一个数字1开始。因该候选<br>解满足除问题规模之外的全部条件,扩大其规模,并使其满足上述条件(1),候选组合<br>改为1,2。继续这一过程,得到候选组合1,2,3。该候选解满足包括问题规模在内的全<br>部条件,因而是一个解。在该解的基础上,选下一个候选解,因a[2]上的3调整为4,以<br>及以后调整为5都满足问题的全部要求,得到解1,2,4和1,2,5。由于对5不能再作调<br>整,就要从a[2]回溯到a[1],这时,a[1]=2,可以调整为3,并向前试探,得到解1,3,<br>4。重复上述向前试探和向后回溯,直至要从a[0]再回溯时,说明已经找完问题的全部<br>解。<br><br>在网上我始终没有找到可以正常执行的完整程序,所以我只好花了一天的时间来自己来写这个程序,并且改变输出从0开始而不是从1开始,这样做的目的是 为了扩展程序的用途,适应c/c++语言的需要,这样输出就可以当作要选择的组合数组的地址序列,可以对长度为n任意类型数组找出r个组合。我对它进行了 优化,如果你认为还有可以优化的地方,请不惜赐教,。^_^<br><br>#include <time><br>#include <iostream><br>#include <iomanip><br>using namespace std;<br><br># define MAXN 100<br>int a[MAXN]; //定位数组,用于指示选取元素集合数组的位置,选取元素集合数组0 起始<br>void comb(int m,int r)<br>{ <br> int cur;//指示定位数组中哪个成员正在移进<br><br> unsigned int count=0;<br><br> //初始化定位数组,0 起始的位置 ,开始的选择必是位置 0,1,2<br> for(int i=0;i<r><br> a[i]=i;<br><br> cur=r-1;//当前是最后一个成员要移进<br><br> do{<br> if (a[cur]-cur&lt;=m-r ){ <br><br> count++;<br> /*<br> for (int j=0;j<r><br> cout&lt;<setw>&lt;<a><br> cout&lt;<endl><br> */<br> a[cur]++;<br><br> continue;<br> }<br> else{<br> if (cur==0){<br> cout&lt;<count>&lt;<endl><br> break;<br> }<br><br> a[--cur]++;<br> for(int i=1;i<r-cur><br> a[cur+i]=a[cur]+i;<br> }<br><br> if(a[cur]-cur<m-r><br> cur=r-1; <br> }<br> }while (1);<br>}<br><br>void printtime(void) //打印当前时间的函数<br>{<br> char tmpbuf[128];<br> time_t ltime;<br> struct tm *today;<br><br> time(&amp;ltime);<br> today = localtime(&amp;ltime );<br> strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);<br> cout&lt;<tmpbuf>&lt;<endl><br>}<br><br>int main (int argc, char *argv[])<br>{<br><br> int m,r;<br> cout&lt;&lt;"m"&lt;<endl><br> cin&gt;&gt;m;<br> cout&lt;&lt;"r"&lt;<endl><br> cin&gt;&gt;r;<br> printtime();<br> comb(m,r); <br> printtime();<br> return(0);<br>}<br><br>同上面的递归的程序进行比较,同样用g++ o2优化。当n=40,r=11,屏蔽掉输出,得到的结果都是2311801440项,递归程序用了23至24秒,回溯用了19至20秒。<br><br>4)利用数组<br><br> 定义:从n个数中取出m个数的组合。<br> 实现机理:先创建一个字符串数组,其下标表示 1 到 n 个数,数组元素的值为1表示其下标代表的数被选中,为0则没选中。 <br> 然后初始化,将数组前 m 个元素置 1,表示第一个组合为前 m 个数。 <br> 然后从左到右扫描数组元素值的 10 组合,找到第一个 "10" 后交换 1 和 0 的位置,变为 01,而后将该10组合前的1和0重新组合(1放在前边,其个数为10组合前1的个数,0放在后边,其个数为10前0的个数,而后接10的倒转组合 01)。当m 个 1 全部移动到最右端时,就得到了最后一个组合。 <br> 例如求 5 中选 3 的组合: <br> 1 1 1 0 0 //1,2,3 <br> 1 1 0 1 0 //1,2,4 <br> 1 0 1 1 0 //1,3,4 <br> 0 1 1 1 0 //2,3,4 <br> 1 1 0 0 1 //1,2,5 <br> 1 0 1 0 1 //1,3,5 <br> 0 1 1 0 1 //2,3,5 <br> 1 0 0 1 1 //1,4,5 <br> 0 1 0 1 1 //2,4,5 <br> 0 0 1 1 1 //3,4,5 <br><br></endl></endl></endl></tmpbuf></m-r></r-cur></endl></count></endl></a></setw></r></r></iomanip></iostream></time></endl></counts></endl></endl></endl></tmpbuf></iostream></time></stdio>


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics