开发者社区> 铭毅天下> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

组合数打印

简介: 方法1:【思路】1)将1,2,3,4存入数组中,然后从4个数中选出1个数,即为selVal;2)接下来的工作即是从剩余的3个数中选取2个数,需要存储除selVal外的剩余3个数;3)选取后打印selVal和选的2个数即可。
+关注继续查看

组合数打印

//[北京直真笔试题]比如给定4个数,分别为1,2,3,4。现在要求从中选取3个的组合数,不能重复。


即打印:123,124,234...。


方法1:【思路】1)将1,2,3,4存入数组中,然后从4个数中选出1个数,即为selVal;2)接下来的工作即是从剩余的3个数中选取2个数,需要存储除selVal外的剩余3个数;3)选取后打印selVal和选的2个数即可。


【分析】:时间复杂度O(n3),空间复杂度O(n)。


const int g_nCnt = 4;

int g_nArr[g_nCnt] ={1,2,3,4};

//从3个里面选2个数的排列方式.

void selTwoFromThree(intnArray[], int nSize, int nAlreadySel)

{

for(int i = 0; i < nSize; i++)

  {

          for(int j = i+1; j < nSize; j++)

          {

                   cout << nAlreadySel << "\t"<< nArray[i] << "\t" << nArray[j] << endl; //先i后j

                   cout << nAlreadySel << "\t"<< nArray[j] << "\t" << nArray[i] << endl; //先j后i

          }

 }

}

void printArray(intnArray[], int nSize)

{

int nAleardySel = 0;

for(int i = 0; i < nSize; i++)

{

          int *pArrAdd = new int[3];

          int k = 0;

          nAleardySel = nArray[i];

          for(int j = 0; j < nSize; j++)

          {

                   if(nArray[j] != nAleardySel)

                   {

                            pArrAdd[k++] = nArray[j];

                   }//end if

          }//end for j

         

          selTwoFromThree(pArrAdd,g_nCnt-1,nAleardySel);

          cout << endl;

}//end fori

}

方法2:【思路】 将4个数中选择的3个数看做百位数,因此就变成了打印的过程,变成了从4个数中选3个数组成的全排列4*4*4=64个中选择百位、十位、个位不重复的4*3*2=24个数的过程。


【分析】:时间复杂度O(n3),空间复杂度O(1)。不需要额外的开辟空间。


#define MAXN 4

void combineSelPrint(intmaxCnt)

{

static int count = 0;

for(int i=1;i<=MAXN;i++)//百位的情况

{

          for(int j=1;j<=MAXN;j++)//十位的情况

          {

                   if(j != i)

                   {

                            for(int k=1;k<=MAXN;k++)//个位的情况

                            {

                                      if(k != j && k != i)

                                      {

                                               printf("%d,%d,%d\n",i,j,k);

                                               ++count;

                                      }

                            }//end for k

                   }//end if j

          }//end for j

}//end for i

cout << "--------------count = " << count<< "-------------" << endl;

}

int main()

{

combineSelPrint(MAXN);

return 0;

}


【思考?】:有没有时间复杂度低的算法?或者递归实现的好方法?


【方法3】:递归实现组合数打印,C(n,m),从n个数中选出m个数(m<=n)个的全部组合打印。


有很多文章讨论如何打印全排列的,毕竟它是很多遍历问题的基础嘛。这里介绍的是如何打印组合数。

先看一个例子:

C(5,3) = 10

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


大家注意到没有,

1 | 2 3

1 | 2 4

1 | 2 5

1 | 3 4

1 | 3 5

1 | 4 5

------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。

2 | 3 4

2 | 3 5

2 | 4 5

------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。

3 | 4 5

------ C(2, 2)∵只能在{4, 5}中挑2个出来。



这样就很容易写出递归算法来。

Algorithm combination(n, k, A[l..n+l-1])

1. if k = 0

2. print ary[1..k]

3. else

4. for i←1 to n-k+1

5. ary[index++] = A[l+i-1]

6. combination(n-i,k-1, A[l+i..n+l-1])

7. --index

8. endfor

大家可能会疑惑干嘛要弄出个index,还有一加一减的(你手工算一下就知道了)。



【实现部分】


int *dst_array,top=0;//中间数组,存放中间求解过程,count计数所有的组合个数

int cnt = 0;

//打印长度为n的数组元素

static void printA(int*parray,int n)

{

   int i;

   for(i=0;i<n;i++)

   {

       printf("%d ",parray[i]);

   }

}

//递归打印组合数

static  void print_combine(int *pArray,int n,int m)

{

   if(n < m || m==0)  

   {

          return ;//情况一:不符合条件,返回

   }

   print_combine(pArray+1,n-1,m);//情况二:不包含当前元素的所有的组合

   dst_array[top++]=pArray[0];//情况三:包含当前元素

   if(m==1)

    {  //情况三-1:截止到当前元素

       printA(dst_array,top);

       printf("\n");

       cnt++;

       top--;

       return;

   }

   print_combine(pArray+1,n-1,m-1);//情况三-2:包含当前元素但尚未截止

   top--;//返回前恢复top值

}

int main()

{

   int n,m,*parray;//存放数据的数组,及n和m

   printf("---以下实现从n个数中选出m个数的全组合打印(n个数为1,2,3....n---\n");

   printf("---请输入n 和m \n---");

   scanf("%d%d",&n,&m);

   printf("\n---以下是输出结果---\n");

   parray=(int *)malloc(sizeof(int)*n);

   dst_array=(int *)malloc(sizeof(int)*m);

   int i;

   for(i=0;i<n;i++)

   {

          //初始化数组

       //scanf("%d",&parray[i]);

          parray[i] = i+1;

   }

   print_combine(parray,n,m);//求数组中所有数的组合

   printf("=====C(%d,%d)共计:%d个=====",n,m,cnt);

   free(parray);

   free(dst_array);

   return 0;

}


       方法三参考: http://bbs.pfan.cn/post-270256.html

    http://blog.csdn.net/challenge_c_plusplus/article/details/6641950


   笔者调试了方法三,好用。但是笔者对其中递归的部分的原理甚是不解,有些疑惑,望大家介绍下。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java - JDK1.8 List 打印输出技巧
Java - JDK1.8 List 打印输出技巧
86 0
Java打印Excel
本文讲解如何用Java打印Excel。
136 0
转换流与打印流
编码引出的问题 import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; /* FileReader可以读取IDE默认编码格式(UTF-8)的文件 FileReader读取系统默认编码(
26 0
Java高并发秒杀系统【观后总结】(三)
在慕课网上发现了一个JavaWeb项目,内容讲的是高并发秒杀,觉得挺有意思的,就进去学习了一番。
57 0
Java高并发秒杀系统【观后总结】(四)
在慕课网上发现了一个JavaWeb项目,内容讲的是高并发秒杀,觉得挺有意思的,就进去学习了一番。
85 0
Java高并发秒杀系统【观后总结】
项目简介 在慕课网上发现了一个JavaWeb项目,内容讲的是高并发秒杀,觉得挺有意思的,就进去学习了一番。 记录在该项目中学到了什么玩意.. 该项目源码对应的gitHub地址(由观看其视频的人编写,并非视频源代码):https://github.com/codingXiaxw/seckill 我结合其资料和观看视频的时候整理出从该项目学到了什么... 项目Dao层 日志记录工具: Mybatis之前没注意到的配置属性: 使用jdbc的getGeneratekeys获取自增主键值,这个属性还是挺有用的。
1531 0
Spring与Hibernate两种组合方式
Spring与Hibernate大致有两种组合方式,主要区别是一种是在Hibernate中的hibernate.cfg.xml中配置数据源,一种是借助Spring的jdbc方式在Spring的applicationContext.
736 0
+关注
348
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载