精华内容
下载资源
问答
  • 集合划分问题

    2021-03-24 17:38:39
    集合划分问题 问题描述: n个元素的集合{1,2,…,n}可以划分为若干非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下: 下面的描述太多了,你们都是看了《计算机算法设计与分析》那本书来的...

    集合划分问题

    问题描述:

    n个元素的集合{1,2,…,n}可以划分为若干非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:
    在这里插入图片描述
    下面的描述太多了,你们都是看了《计算机算法设计与分析》那本书来的吧?所以后面三行我就不描述了。(偷懒ing)
    PS:集合{{1,2},3,4}由三个子集组成(书中描述的大致内容)

    算法设计:

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

    算法分析:

    定义F(n,m)=此题的解
    当m=1时,F(n,m)=1;
    当n=m时,F(n,m)=1;

    假设原集合有m个元素,后输入了n-m个元素,此时将输入的元素和原集合的1个元素合并成一个子集,则此时集合依旧有m个元素,或者将原集合的n-m+1个元素合并成一个子集,此时集合也是m个元素,则这两种合并方法,合并出来的集合的不同种类之和,则是我们需要想要得出的答案。
    (上面一段话用了逆向的思维方式)
    这两种方法所得到的表达式则为:
    F(n-1,m-1)和F(n,m-1)*m
    答案就等于: F(n-1,m-1)+F(n,m-1)*m
    这样,则可以用递归的方法求出答案(在得出任一个递归的返回值之前,调用次数为2^n次)
    代码如下:

    #include<iostream>
    using namespace std;
    int F(int n,int m)
    {
    	if(m==1||m==n)
    		return 1;
    	else
    		return F(n-1,m-1)+m*F(n-1,m);
    }
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	if(m==1||m==n)
    	cout<<"1"<<endl;
    	else
    	if(m==0||n==0||n<m)
    	cout<<"ÊäÈë´íÎó£¡"<<endl;
    	else
    	cout<<F(n-1,m-1)+m*F(n-1,m)<<endl;
    	return 0;
    }
    

    拜拜

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,548
精华内容 619
关键字:

集合划分问题