C++中求组合数的各种方法总结详解_c++计算组合数 - CSDN文库

179 浏览量更新于2023-03-16 评论 1 收藏 70KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

C++中求组合数的各种方法总结详解中求组合数的各种方法总结详解

本篇文章是对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;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

weixin_38707061

粉丝: 2
资源: 921

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈