算法笔记 06_集合划分问题


★问题描述

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

★编程任务

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


★算法思想

//有 n 个元素的集合,在每次对其进行划分时,都可以划分成由 m 个子集构成的子集,并且易知:1 <= m <= n; 
//建立一个函数 F(n, m) 表示将 n 个元素的集合划分成由 m 个子集构成的集合的方法个数: 
//考虑以下几种情况: 
//1. 当 m == 1,则 F(n, m) = 1; 
//2. 当 n == m,则 F(n, m) = 1; 
//3. 若非以上两种,则 f(n, m) 可以由下面两种情况构成: 
// a.向 n - 1 个元素划分成的 m 个集合里面添加一个新的元素,则有 m * F(n - 1, m) 种方法; 
// 比如:1234 先将3个元素(这里 n - 1 为 3)123 划分成两个(设 m = 2)子集构成的集合{{12}{3}},然后将 4 分别加到这俩子集里:{{124}{3}} 或 {{12}{34}},也就是说每种情况都要乘上 m 种方法 
// b.向 n - 1 个元素划分成的 m - 1 个集合里添加一个由一个元素形成的独立的集合,则有 F(n - 1, m - 1) 种方法。 
// 比如:1234 先将3个元素 123 成 1 个(m - 1 = 1)子集构成的集合{{123}},然后将{4}这个独立子集加进去:{{123}{4}},即只有一种方法,没有乘数 
//综上:F(n,m) = F(n-1,m-1) + m * F(n-1,m) 
**

★C++ 代码如下 (Visual Studio 2017):

#include "stdafx.h"
#include<iostream>  
#include<cstdio>  
#include<stdio.h>
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;
}
    
void main()
{
    int n;    
    while (!0)
    {    
        cout << "Please input the total number of the elements(bigger than zero): ";        
        if (scanf_s("%d", &n) >= 1)
        {       
            int sum = 0;    //定义一个记录总数的变量 sum
            for (int i = 1;i <= n;i++)
            {
                sum += F(n, i);
            }            
            cout << "The result is: " << sum << endl;            
            cout << "_______________________________________________________________" << endl;
        }
    }
    system("pause");
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论