集合划分问题
2023-03-14 22:40:28 时间
问题描述
n个元素的集合{1,2,.,n }可以划分为若干个非空子集。例如,当n=4 时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:
四个子集:{1},{2},{3},{4}},
。
三个子集:{{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.txt 提供输入数据。文件的第1 行是元素个数n 和非空子集数m。
问题分析
回顾问题:给定正整数n 和m,计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。假定多少个用F(m,n)来计算
若m=1,则F(m,n)=1 --> 所有元素放在一个大集合中
若m=n,则F(n,m)=1 --> 所有元素都是单元素集合,然后将单元素集合放在一个大集合中
最后剩下F(n,m),可以分为以下两个情况:
a. 向n-1个元素中划分的m个非空字节构成的集合中添加一个新的元素,则有mF(n-1,m)种情况
b. 向n-1个元素中划分的m-1的集合中添加一个元素的独立集合,则总非空集合有m-1+1=m个,则有1F(n-1,m-1)种情况
综合上面的情况,我们可以得出一个递归的式:
代码实现
#include "stdafx.h" #include "stdio.h" #include "iostream.h" #include<fstream>//用于文件输入输出 using namespace std; int setpart(int n,int m)//递归实现 { if(m==1 || m==n) return 1; return setpart(n-1,m-1)+m*setpart(n-1,m); } int main(int argc, char* argv[]) { ifstream infile("input.txt",ios::in); int m,n; infile>>n; infile>>m; cout << "元素个数为" <<n<<' '<<"组成集合的非空集合数:"<<m<< endl; int out; out=setpart(n,m); ofstream outfile; outfile.open("out.txt"); cout << "Writing to the file" << endl; cout << out << endl; outfile<<out<< endl; return 0; }
相关文章
- 使用 AWS Backup Audit Manager 监控、评估和证明备份合规性
- Amazon EC2!15 岁生日快乐!
- java lamda_Java 8中,lamda函数编程
- 关于Amazon EKS中Service和Ingress深入分析和研究
- 游戏公司多账号管理(一)
- 新增 — 由最新一代英特尔至强可扩展处理器提供支持的 Amazon EC2 M6i 实例
- 在AWS上使用AlphaFold进行蛋白质结构预测
- 在亚马逊云科技Marketplace上的SaaS架构设计——如何支持跨多账户对接
- minicap java_Java JLabel.LEFT属性代码示例
- 在亚马逊云科技Marketplace上的SaaS架构设计——如何支持多产品使用单一账户中心
- 关于Amazon EKS基于Gitlab的CICD实践二 基础架构和应用架构创建篇
- 利用 Amazon Transcribe Call Analytics 从客户对话中提取见解
- 在 2021 年,AWS 连续第 11 年在云基础设施和平台服务 Gartner 魔力象限 (CIPS) 被评为领导者
- 如何在亚马逊云科技Marketplace海外区上线SaaS产品
- 关于Amazon EKS基于Gitlab的CICD实践一 Gitlab的部署和配置篇
- python gRPC(一)
- 使用Amazon Step Functions Data Science SDK构建从AWS Glue Crawler到Glue Job的工作流程
- 基于rclone构建Cross Border Data Transfer服务
- java sendmessage_Java SendMessageToWX.Resp方法代码示例
- java radiogroup_Java RadioGroup.setLayoutParams方法代码示例