排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。
排列与组合在日常生活中应用较广,比如在考虑某些事物在某种情况下出现的次数时,往往需要用到排列和组合。
【例1】取值组合。
有一个集合拥有m个元素{1,2,…,m},任意的从集合中取出n个元素,则这n个元素所形成的可能子集有哪些?
假设有5个元素的集合,取出3个元素的可能子集如下:
{1,2,3}、{1,2,4}、{1,2,5}、{1,3,4}、{1,3,5}、
{1,4,5}、{2,3,4}、{2,3,5}、{2,4,5}、{3,4,5}。
编写一个程序,输入整数m和n,输出m个元素中,取出n个元素的各种情况。
(1)编程思路。
用递归程序来解决问题。
从m个数中,取出n个数的所有组合。设m个数已存于数组a[1..m]中。为使结果唯一,可以分别求出包括a[m]和不包括a[m]的所有组合。即包括a[m]时,求出从a[1..m-1]中取出n-1个元素的所有组合(子问题,递归);不包括a[m]时,求出从a[1..m-1]中取出n个元素的所有组合(同样是子问题,递归)。
(2)源程序。
#include <iostream>
using namespace std;
#define maxsize 20
void nkcombination(int i,int k,int j,int a[],int b[])
// 从n(a[0])个数中连续取出k个数的所有组合,n个数已存入数组a中。
// i为待取数在数组a中的下标,j为结果数组b中的下标。
{
if (k==0)
{
for (int p=1;p<=b[0];p++)
cout<<b[p]<<” “;
cout<<endl;
}
else if (i+k-1<=a[0])
{
b[j]=a[i]; j++;
nkcombination(i+1,k-1,j,a,b);
// 包括a[i]时,递归求出从a[i+1..n]中取出k-1个元素的所有组合
nkcombination(i+1,k,j-1,a,b);
// 不包括a[i]时,递归求出从a[i+1..n]中取出k个元素的所有组合
}
}
int main()
{
int set[maxsize],result[maxsize];
int m,n,i;
cout<<“输入给定元素个数 m :”;
cin>>m;
for (i=1;i<=m;i++)
set[i]=i;
cout<<“输入取出元素个数 n:”;
cin>>n;
set[0]=m; result[0]=n;
nkcombination(1,n,1,set,result);
return 0;
}
【例2】选数。
已知n个整数x1,x2,…,xn,以及一个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时,可得全部的组合与它们的和为:3+7+12=22,3+7+19=29,7+12+19=38,3+12+19=34。编写一个程序计算出和为质数的组合共有多少种。
例如上例,只有一种组合的和为质数:3+7+19=29。
(1)编程思路。
本例是求从n个数中选k个数的组合,并使其和为素数。求解此题时,先按例1的方法生成k个数的组合,再判断k个数的和是否为质数,若为质数则输出和式并计数。
(2)源程序。
#include <iostream>
#include <cmath>
using namespace std;
#define maxsize 20
int cnt=0;
bool isprime(int num)
{
int m;
if(num==2) return true;
for(m=2;m<=(int)sqrt((double)num);m++)
if (num%m==0)
return false;
return true;
}
void nkcombination(int i,int k,int j,int a[],int b[])
{
if (k==0)
{
int p,s;
for (p=1,s=0;p<=b[0];p++)
s=s+b[p];
if (isprime(s))
{
cnt++;
for (p=1;p<b[0];p++)
cout<<b[p]<<” + “;
cout<<b[p]<<“=”<<s<<endl;
}
}
else if (i+k-1<=a[0])
{
b[j]=a[i]; j++;
nkcombination(i+1,k-1,j,a,b);
nkcombination(i+1,k,j-1,a,b);
}
}
int main()
{
int set[maxsize],result[maxsize];
int n,k,i;
cout<<“输入给定整数的个数 n :”;
cin>>n;
cout<<“依次输入”<<n<<“个整数:”;
for (i=1;i<=n;i++)
cin>>set[i];
cout<<“输入取出元素个数 k:”;
cin>>k;
set[0]=n; result[0]=k;
nkcombination(1,k,1,set,result);
cout<<“count=”<<cnt<<endl;
return 0;
}
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602940.html