电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: C++中求组合数的各种方法总结详解 [打印本页]

作者: yuyang911220 时间: 2017-4-23 16:05 标题: C++中求组合数的各种方法总结详解

【问题】    组合问题
问题描述：找出从自然数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.h>
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++){
            counts++;
            printf("%4d%4d%4d/n",i,j,k);
         }
printf("%d",counts);
return 0;
}
但是这个程序都有一个问题，当r变化时，循环重数改变，这就影响了这一问题的解，即没有一般性。

2)递归法
分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。
设函数为void comb(int m,int k)为找出从自然数1、2、... 、m中任取k个数的所有组
合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这
就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引
入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放
在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、
...、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组
合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节
见以下程序中的函数comb。
【程序】
#include <time.h>
#include <iostream>
using namespace std;
# define    MAXN    100
int a[MAXN];
int counts=0;
void printtime(void) //打印当前时间的函数
{
   char tmpbuf[128];
   time_t ltime;
   struct tm *today;
   time(<ime);
   today = localtime(<ime );
   strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today);
   cout<<tmpbuf<<endl;
}

void    comb(int m,int k)
{    int i,j;
   for (i=m;i>=k;i--)
   {    a[k]=i;
      if (k>1)
            comb(i-1,k-1);
      else
      {
            counts++;
            /*
            for (j=a[0];j>0;j--)
               printf("%4d",a[j]);
            printf("/n");
            */
      }
   }
}
int main()
{
   int m,r;
   cout<<"m"<<endl;
   cin>>m;
   cout<<"r"<<endl;
   cin>>r;
   counts=0;
   a[0]=r;
   printtime();
   comb(m,r);
   cout<<counts<<endl;
   printtime();
   return 0;
}

这是我在网上找到的程序，稍微修改了一下。程序写的很简洁，也具有通用性，解决了问题。
3)回溯法
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]
中，组合的元素满足以下性质：
（1）    a[i+1]>a[i]，后一个数字比前一个大；
（2）    a[i]-i<=n-r+1。
按回溯法的思想，找解过程可以叙述如下：
   首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选
解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合
改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全
部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以
及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调
整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，
4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部
解。
在网上我始终没有找到可以正常执行的完整程序，所以我只好花了一天的时间来自己来写这个程序，并且改变输出从0开始而不是从1开始，这样做的目的是为了扩展程序的用途，适应c/c++语言的需要，这样输出就可以当作要选择的组合数组的地址序列，可以对长度为n任意类型数组找出r个组合。我对它进行了优化，如果你认为还有可以优化的地方，请不惜赐教,。^_^

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)