打印组合(递归)
发布时间
阅读量:
阅读量
组合打印问题:已知数值n与k(满足1<=k<=n),需要生成并输出所有C(n,m)的组合形式。例如,当n=5且k=3时,所有可能的组合如下所示:
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
若仅需计算组合数,则属于较为基础的[单向递归]问题,因其可通过递推公式得出:C(n,k) = C(n-1,k-1) + C(n-1,k),同时满足边界条件C(n,1)=n以及C(n,0)=0;然而,[生成并输出所有可能的组合]则具有更高的复杂度。
在本题中,我们选择以降序方式输出结果,即按照数值从高到低排列。
我的思路是:第一个数字可取自n、n-1、...、k这几个值。假设第一个数字选定为x,则后续的第2至第k个数字应从x-1到1之间选取。当确定倒数第二个数字为y时,最后一个数字可依次列举为y-1、...、1等选项。在实际输出过程中,只需依次列出第一个至倒数第二个数字,并循环添加最后一个数字的所有可能性即可。
按照上述策略,求解从5个元素中选取3个的所有组合过程如下:从序列5、4、3、2、1中选取三个元素:
5 4 [3、2、1] —— 在选定前两个元素为5和4后,分别加上3、2和1构成三种不同的组合方式。
5 3 [2、1] —— 在选定前两个元素为5和3
全部评论 (0)
还没有任何评论哟~
