[分治]-集合划分问题 [分治]-逆序对问题

男娘i 2022-06-16 03:07 261阅读 0赞

n 个元素的集合\{1,2,., n \}可以划分为若干个非空子集。例如，当n=4 时，集合\{1，2， 3，4\}可以划分为15 个不同的非空子集如下：

\{ \{1\}，\{2\}，\{3\}，\{4\}\}，

\{ \{1，3\}，\{2\}，\{4\}\}，

\{ \{1，4\}，\{2\}，\{3\}\}，

\{ \{2，3\}，\{1\}，\{4\}\}，

\{ \{2，4\}，\{1\}，\{3\}\}，

\{ \{3，4\}，\{1\}，\{2\}\}，

\{ \{1，2\}，\{3，4\}\}，

\{ \{1，3\}，\{2，4\}\}，

\{ \{1，4\}，\{2，3\}\}，

\{ \{1，2，3\}，\{4\}\}，

\{ \{1，2，4\}，\{3\}\}，

\{ \{1，3，4\}，\{2\}\}，

\{ \{2，3，4\}，\{1\}\}，

\{ \{1，2，3，4\}\}

给定正整数n和m，利用分治算法计算出n 个元素的集合\{1,2,., n \}可以划分为多少个不同的由m个非空子集组成的集合。

Input

元素个数n和非空子集数m。

Output

计算出共有多少个不同的由m 个非空子集组成的集合。

Sample Input  
4 2

Sample Output  
7

直接输出样例的同学小心挂科哦～

?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29

# include #

using namespace std;

int f(int n,int m)  
\{  
if(m==1||n==m)  
return 1;  
else  
return f(n-1,m-1)+f(n-1,m)\*m;  
\}

int main(void)  
\{  
int n,m;  
int sum=0;  
cin>>n>>m;  
sum=f(n,m);  
cout<

# include #

using namespace std;

int main()  
\{  
int n,a\[30000\],Count=0;  
cin>>n;  
for(int i=0;i

发表评论取消回复

表情：

评论列表（有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读

相关分治算法--选择问题

分治算法--选择问题

青旅半醒/ 2024年04月23日 20:14/ 0 赞/ 89 阅读

相关分治-芯片测试问题

文章目录芯片测试问题生成数据暴力分治源码芯片测试问题 ------------------

怼烎@/ 2022年12月14日 06:37/ 0 赞/ 184 阅读

相关算法设计与分析——分治与递归——整数划分问题

将正整数n表示为一系列正整数之和， n=n1+n2+n3+n4+......+nk （其中，n1>=n2>=n3>=n4........>=nk>0,k>=1）

待我称王封你为后i/ 2022年10月14日 01:14/ 0 赞/ 209 阅读

相关整数划分算法实现分治策略

将正整数n表示成一系列正整数之和。正整数n的这种表示成为正整数n的划分。正整数n的不同的划分个数成为正整数n的划分数。 int q(int n,int

淡淡的烟草味﹌/ 2022年08月21日 00:15/ 0 赞/ 265 阅读

相关求逆序数的分治算法

给我们一个序列, 让我们求其逆序数: 如3 2 1 4 逆序数为: 2+1+0+0=3 我们这样定义一个序列的逆序数: 序列a1 a2 a3 a2 ...an 这个序列

浅浅的花香味﹌/ 2022年07月12日 02:19/ 0 赞/ 186 阅读

相关求逆序数的分治算法

给我们一个序列, 让我们求其逆序数: 如3 2 1 4 逆序数为: 2+1+0+0=3 我们这样定义一个序列的逆序数: 序列a1 a2 a3 a2 ...an 这个序列

小咪咪/ 2022年07月12日 02:19/ 0 赞/ 215 阅读

相关 [分治]-集合划分问题 [分治]-逆序对问题

n 个元素的集合\{1,2,., n \}可以划分为若干个非空子集。例如，当n=4 时，集合\{1，2， 3，4\}可以划分为15 个不同的非空子集如下： \{ \{1\}，

男娘i/ 2022年06月16日 03:07/ 0 赞/ 262 阅读

相关循环赛问题（分治）

设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛一共进行n-1天。按此要

ゝ一世哀愁。/ 2022年06月06日 12:20/ 0 赞/ 182 阅读

相关最近点对问题（分治法）

问题：平面最近点对问题是指：在给出的同一个平面内的所有点的坐标，然后找出这些点中最近的两个点的距离. 代码： include <iostream> in

系统管理员/ 2022年04月13日 06:12/ 0 赞/ 381 阅读

相关最近对问题的分治算法

对n个预排序点的运行时间，有以下递推式： T(n) = 2T(n/2) + M(n) 应用针对O的主定理（其中 a=2, b=2, d=1),我们得到T(n) 的时间复杂

àì夳堔傛蜴生んèń/ 2021年11月16日 09:40/ 0 赞/ 275 阅读