收藏本站 
网站首页 
网站地图 
>> 我们从网络和杂志上收集了近100000余篇各类电脑技术、网络技术、软件技术等方面的文章教程,我们的收录原则:不是精华拒不收录!
先飞电脑技术网技术文章
解决排列组合问题的通用算法
[ 作者:佚名    转贴自:网络转载    阅读次数:192    更新时间:2006-5-10 10:33:00   录入:刘光勇 ]         

很多网友发贴询问诸如:八皇后问题、彩票问题(从m中数中选择n(m>=n)的组合)等,其实这都可归结为排列组合的问题。解决这类问题,用for循环嵌套是不现实的(只能对指定的m、n编程,而且程序看上去异常繁琐),较好的方法是回朔法。下面给出这类问题的一般算法的c/c++描述:

int combine(int a[],int sub){
//a[1..?]表示候选集,sub表示一个排列(组合)的元素个数
{
   int total=sizeof(a);
   int order[sub+1];
   int count=0;//符合条件的排列(组合)的个数
   order[0]=-1;
   for(int i=1;i<=sub;i++)
      order[i]=i;
   int k=sub;
   bool flag=true;
   while(order[0]!=-1){
      if(flag){
         for(i=1;i<=sub;i++)//输出符合要求的组合
            printf("%d ",a[order[i]]);
         printf("\n");
         count++;
         flag=false;
      }
      order[k]++;
      if(order[k]==total+1){
         order[k--]=0;
         continue;
      }   
   ...
      //在此加入order[k]的限制条件
      //如果条件满足,则往下执行
      //否则continue;
      if(k<sub){
         order[++k]=order[k-1];
         continue;
      }
      if(k==sub)
         flag=true;
   }
   return count;
}

上一篇:计算机软件开发文档编写指南  下一篇: 对做硬件和软件的一点感想  

网站主页 | 收藏本页 | 联系我们 | 广告服务 | 站点地图 | 会员注册 | 招聘信息 | 内容指正

联系QQ:先飞电脑技术网站事务联系QQ,点击可以直接留言. 32933427 电话:13710542091 [世界排名] 鄂ICP备05005890号