题目描述
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,计算出n个元素的集合{1,2,……, n }可以划分为多少个不同的非空子集。
输入
输入数据只有1行是元素个数n(n≤20)。
输出
输出一个整数,表示计算出的不同的非空子集数。
样例输入
5
样例输出
52
参考代码
#include<stdio.h>
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;
scanf("%d",&n);
int sum=0;
for (int i=1;i<=n;i++)
sum+=f(n,i);
printf("%d",sum);
return 0;
}
解析
暂无