文档库

最新最全的文档下载
当前位置:文档库 > 计算出n个元素的集合{1,2,……,n}可以划分为多少个不同的非空子集

计算出n个元素的集合{1,2,……,n}可以划分为多少个不同的非空子集

问题描述

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

{{1},{2},{3},{4}} {{1,3},{2,4}}

{{1,2},{3},{4}} {{1,4},{2,3}}

{{1,3},{2},{4}} {{1,2,3},{4}}

{{1,4},{2},{3}} {{1,2,4},{3}}

{{2,3},{1},{4}} {{2,3,4},{1}}

{{2,4},{1},{3}} {{1,2,3,4}}

{{3,4},{1},{2}}

2.算法设计

给定正整数n,计算出n个元素的集合{1,2,……,n}可以划分为多少个不同的非空子集。

3.输入输出

输入输出

5 52

4.算法

设n个元素的集合可以划分为F(n,m)个不同的由m个非空子集组成的集合。

考虑3个元素的集合,可划分为:

①1个子集的集合:{{1,2,3}}

②2个子集的集合:{{1,2},{3}},{{1,3},{2}},{{2,3},{1}}

③3个子集的集合:{{1},{2},{3}}

∴F(3,1)=1;F(3,2)=3;F(3,3)=1;

如果要求F(4,2) ,步骤如下:

A.往①里添一个元素{4},得到{{1,2,3},{4}}

B.往②里的任意一个子集添一个4,得到

{{1,2,4},{3}},{{1,2},{3,4}},

{{1,3,4},{2}},{{1,3},{2,4}},

{{2,3,4},{1}},{{2,3},{1,4}}

∴F(4,2)=F(3,1)+2*F(3,2)=1+2*3=7

推广,得F(n,m)=F(n-1,m-1)+m*F(n-1,m)

5.代码

彩99彩票官网