递归（四）：组合

      排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

      排列与组合在日常生活中应用较广，比如在考虑某些事物在某种情况下出现的次数时，往往需要用到排列和组合。

【例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;

}  

posted on 2019-06-26 19:43 aTeacher 阅读(...) 评论(...) 编辑 收藏