`
- 浏览:
88360 次
- 性别:
- 来自:
哈尔滨
-
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<=r ;i++)<br> for(j=i+1;j<=r+1;j++)<br> for( k=j+1;k<=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(&ltime);<br> today = localtime(&ltime );<br> strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);<br> cout<<tmpbuf><<endl><br>}<br><br><br>void comb(int m,int k)<br>{ int i,j;<br> for (i=m;i>=k;i--)<br> { a[k]=i;<br> if (k>1)<br> comb(i-1,k-1);<br> else<br> { <br> counts++;<br> /*<br> for (j=a[0];j>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<<"m"<<endl><br> cin>>m;<br> cout<<"r"<<endl><br> cin>>r;<br> counts=0;<br> a[0]=r;<br> printtime();<br> comb(m,r);<br> cout<<counts><<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]>a[i],后一个数字比前一个大;<br>(2) a[i]-i<=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<=m-r ){ <br><br> count++;<br> /*<br> for (int j=0;j<r><br> cout<<setw><<a><br> cout<<endl><br> */<br> a[cur]++;<br><br> continue;<br> }<br> else{<br> if (cur==0){<br> cout<<count><<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(&ltime);<br> today = localtime(&ltime );<br> strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);<br> cout<<tmpbuf><<endl><br>}<br><br>int main (int argc, char *argv[])<br>{<br><br> int m,r;<br> cout<<"m"<<endl><br> cin>>m;<br> cout<<"r"<<endl><br> cin>>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
相关推荐
6位数,共有几种排列组合的算法,java实现
用程序实现有几种方法: 1)穷举法 程序如下【程序】#include<stdio>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
8位数字和字母组合大全,里含有四位六位八位的数组和密码的组合,密码批量测试神器,批量测试网站登陆密码测试,压力承受能力测试,大神必备神器!
单位结算,共14个账单(A列),但是只给28608元(欠钱的是大爷!),还没有告诉是哪几个账单凑出来的,于是找了这个财务凑数的东东。
-1《数字逻辑电路》复习题.doc
编程求解:输入两个整数 n 和 m,从数列 1,2,3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来。
从n个数组中取出所有排列组合(Java实现)
java 实现有数量不限的面值为100,50,20,10,5,1元的纸币,问要组成N(N^6)共有多少种组合方式;其中包括了爆搜的方法和动态规划的方法
逻辑覆盖测试的各种方法讲解:语句覆盖,判定覆盖,条件覆盖,条件/判定覆盖,条件组合覆盖,路径覆盖
本篇文章主要介绍了java 两个数组合并的方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
:介绍了趋势分析法、回归分析法、指数平滑法、单耗法、灰色模型法、负荷密度法和弹性系数法等电力负荷预测的方法,并以预测珠海市全社会年用电量...数据形式、计算难度和适用时间等方面对这几种预测方法进行了分析、比较...
针对红外人体图像成像质量较差的问题,提出一种基于模糊Havrda—Charvfit熵的快速阈值分割方法....在真实红外人体图像集上与几种经典的图像阈 值方法进行对比实验的结果,说明了该方法的有效性和鲁棒性.
针 对多分辨小波神经网络提出了BP和多分辨率学习组合 算法,解 决了传统学习算法网络隐层节点数难以确定的问题, 克服了BP 网络单尺度学习算法很难学习复杂的时间序列的不足 。以上证综 合指数为例,分别采用具有...
2. 能对几种算法给定任意序列不同的页面引用串和任意帧实内存块数的组合测试,显示页置换的过程。 3. 能统计和报告不同置换算法情况下依次淘汰的页号、缺页次数(页错误数)和缺页率。比较几种置换算法在给定条件下...
已经使用几种方法和算法来解决该问题。 以前使用的所有方法都有效,但也有局限性。 其中一些方法会在帧数很大时丢失对象,而另一些方法会在方向改变或高速滚动时丢失对象。 另外,当物体改变颜色时,提出的用于检测...
而在编历多维数组使用的较多的应该是 for 循环遍历和 foreach 遍历两个函数了,其中没什么特殊要求的话,基本上都是在使用 foreach 遍历函数,当然,我们可以通过这两个遍历函数来组合成各种各样的输出方式。...
value,key:value,...}的键值对的结构,在面向对象的语言中,key为对象的属性,value为对应的属性值,所以很容易理解,取值方法为 对象.key 获取属性值,这个属性值的类型可以是 数字、字符串、数组、对象几种。...
几种方法的组合更适合于绘制水利设施的有利区域。 这项研究的重点是建立水位有利区。 所使用的方法是遥感,确定含水层和腐泥土厚度的泵测试表。 为了确定补给量,已使用GR2M方法和排水密度。 数字高程模型(DEM)已...
文章在保证组合服务执行路径发现成功率的前提下,提出了两种限制跳数的组合服务执行路径发现方法,通过限制组合服务执行路径请求包广播的跳数来减少网络中请求包转发的数量,避免无用的传输消耗。实验证明提出的方法...
通过对几种常见滤波窗函数的分析和比较,设计了一种将汉宁窗和矩形窗相结合的新型滤波窗。由于组合窗的滤波精度与物体频谱分布情况(面型情况)有关,在复合光栅三维实时测量中,对频谱成分适中的Peaks函数物体进行...