《从n个数中取m个数的所有组合》由会员分享，可在线阅读，更多相关《从n个数中取m个数的所有组合（5页珍藏版）》请在金锄头文库上搜索。
1、本算法用于实现从一个含有n个数字的数组中，任意取其中m个元素的所有组合的实现情况，推导理由：以1,2,3,4,5 数组为例，很明显，当只取一个元素时有5 种，即单独的一个 元素；取2个时候，就是C(5, 2)=10种，即任意取2个数，以此类推。下面给出算法实现：1，单独存入一个元素，并存到所有组合中去；2，每加入一个新元素，则该新元素为一个单独的组合，同时，该 新元素与(前面的)所有组合都可以组成一个新组合。即一步一步地每个加1。例如当前面 的所有组合只有(1)时，存入一个2，则2单独存一下；然后2与1组成一个新组合，所 有插入2以后，新的所有组合就是：(1)，(2)，(1,2)；接下来插入新
2、元素3，则元素3也可 以单独成为一个组合存入，同时元素3 还可以与前面的任意一个组成一个新组合，则插入3 以后，新的所有组合为：(1)，(2)，(3)，(1,3)，(2,3)(1,2， 3)，以此类推。3.最后统计(排序)所有组合的个数，以及每一种组合中元素的个数。对应输出元素个 数为m的组合即可。下面给出示例程序：/*vectorvector*/ void My_zuhe(int n,int r)multimapint,vector mm,mm2;vector nn,temp,bb;vectorvector target;multimapint,vector:iterator pos;vec
3、tor:iterator ita,ita_bb;typedef pairint,vector pr;for(int i=1;in)return;int m=1,k;ita_bb=bb.begin();temp.push_back(*ita_bb);mm.insert(pr(temp.size(),temp);temp.clear();+ita_bb;while(ita_bb != bb.end()k=*ita_bb;for(pos=mm.begin();pos!=mm.end();+pos)temp=pos-second;temp.push_back(k);mm2.insert(pr(temp
4、.size(),temp);temp.clear();for(pos=mm2.begin();pos!=mm2.end();+pos)mm.insert(*pos);mm2.clear();temp.push_back(k);mm.insert(pr(temp.size(),temp); temp.clear();+ita_bb;for(pos=mm.begin();pos != mm.end();+pos)if(pos-first =r) target.push_back(pos-second);sort(target.begin(),target.end(); vectorvector:i
5、terator tt_pos;coutIn all we have target.size() kinds, and they are:0) coutendl;coutbegin();ita != tt_pos-end();+ita) cout*ita, ;cout) ;/return target;主函数调用为：#include stdafx.h#include example23_apply_offer.hvoid main()My_zuhe(10,2); coutendl;实验结果展示C（10，2）raw C:Wi n dewssyste m 3 2cmd. exeIn all we h
6、ave 4Ekinds . and they are :1,5,1, 6,j2,7. ?O,4, o,5,、O, G& 7.、Rr、1fl.、4.乩4,8,4,9,4, 10,5, 10,jC（5，3）C（5，4）例题 2： 题目描述给定一个正整数k（3k15）,把所有k的方幕及所有有限个互不相等的k的方幕之和构成一个递增 的序列，例如，当k=3时，这个序列是：1， 3， 4， 9， 10， 12， 13,（该序列实际上就是：3人0, 3人1, 3人0+3人1, 3人2, 3人0+3人2, 3人1 + 3人2,3人0+3T+3人2,）请你求出这个序列的第N项的值（用10进制数表示）。例如，对于
7、k=3, N = 100,正确答案应该是981。输入格式输入只有1行，为2个正整数，用一个空格隔开：k N（k、N的含义与上述的问题描述一致，且3k15, 10N1000）。 输出格式输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1 *10人9）。（整数前不要有空格和其他符号）。样例输入3 100d 1样例输出【解题思路】运用刚才介绍的算法，只需求出每个组合中所有元素的和即可，同时进行排序 和查重，删除重复的元素即可。实验程序如下：int kkfangmi（int k,int n）set mm; set:iterator pos; vector nn;vector:iterator ita;int m=1,temp,i;mm.insert(1);while(mm.size()n)temp=1;for(i=0;im;i+) temp=k*temp;for(pos=mm.begin();pos!=mm.end();+pos) i=(*pos)+temp; nn.push_back(i); for(ita=nn.begin();ita!=nn.end();+ita) mm.insert(*ita);nn.clear();mm.insert(temp);m+;pos=mm.begin();for(i=0;in-1;i+)+pos;return *pos;实验结果展示
