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

---

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

#include <time.h>
#include <iostream>
#include <iomanip>
using namespace std;
# define      MAXN      100
int a[MAXN]; //定位数组,用于指示选取元素集合数组的位置，选取元素集合数组0 起始
void comb(int m,int r)
{   
      int cur;//指示定位数组中哪个成员正在移进
      unsigned int count=0;
      //初始化定位数组，0 起始的位置 ，开始的选择必是位置 0，1，2
      for(int i=0;i<r;i++)
          a=i;
      cur=r-1;//当前是最后一个成员要移进
       do{
          if (a[cur]-cur<=m-r ){  
              count++;
              /*
              for (int j=0;j<r;j++)
                  cout<<setw(4)<<a[j];
              cout<<endl;
              */
              a[cur]++;

              continue;
          }
          else{
              if (cur==0){
                  cout<<count<<endl;
                  break;
              }
              a[--cur]++;
              for(int i=1;i<r-cur;i++){
                  a[cur+i]=a[cur]+i;
              }
              if(a[cur]-cur<m-r)
                  cur=r-1;               
          }
      }while (1);
}


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;
}
int main (int argc, char *argv[])
{
      int m,r;
      cout<<"m"<<endl;
      cin>>m;
      cout<<"r"<<endl;
      cin>>r;
      printtime();
      comb(m,r);   
      printtime();
      return(0);
}
同上面的递归的程序进行比较，同样用g++ o2优化。当n=40，r=11，屏蔽掉输出，得到的结果都是2311801440项，递归程序用了23至24秒，回溯用了19至20秒。

4）利用数组
  定义：从n个数中取出m个数的组合。
  实现机理：先创建一个字符串数组，其下标表示 1 到 n 个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。     
    然后初始化，将数组前 m 个元素置 1，表示第一个组合为前 m 个数。     
    然后从左到右扫描数组元素值的 10 组合，找到第一个 "10" 后交换 1 和 0 的位置,变为 01，而后将该10组合前的1和0重新组合（1放在前边，其个数为10组合前1的个数，0放在后边，其个数为10前0的个数，而后接10的倒转组合 01）。当m 个 1 全部移动到最右端时，就得到了最后一个组合。     
    例如求 5 中选 3 的组合：     
    1     1     1     0     0     //1,2,3     
    1     1     0     1     0     //1,2,4     
    1     0     1     1     0     //1,3,4     
    0     1     1     1     0     //2,3,4     
    1     1     0     0     1     //1,2,5     
    1     0     1     0     1     //1,3,5     
    0     1     1     0     1     //2,3,5     
    1     0     0     1     1     //1,4,5     
    0     1     0     1     1     //2,4,5     
    0     0     1     1     1     //3,4,5

---

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

Powered by Discuz! 7.0.0