指定子集个数的集合划分
实验名称指定子集个数的集合划分系别信科院
姓名曾会蜜学号3090717116班级计本09-1
实验地点1409J日期2011年10月实验时数4
指导教师叶苗同组成员独立完成成绩
•实验目的及要求
•明确递归和递推的基本概念
•用递归和递推解决指定子集个数的集合划分问题
•通过本例掌握递归和递推的程序设计方法
•实验环境及相关情况（包括使用的软件、实验设备）
•工具软件：Microsoft visual C++ 6.0
•硬件：主板，鼠标，键盘，显示器，U盘
•操作系统：Windows 7
•实验内容及步骤（包括简要的实验步骤流程）
1.根据题目确定思路,划分集合,可以找出其中的逻辑关系.
2.根据逻辑关系,运用递归的算法来求,划分为两种情况对于一种情况，等价于把前n-1个元素分成m-1份，然后n号元素单独放。

对于第二种情况，等价于把前n-1个元素分成m份，然后把n号元素放入这m个集合中的一个（也就是说有m种放法）
那麽总数就是
F(n,m) = F(n-1,m-1) + m * F(n-1,m)
3.根据分析建立递推方程
•实验结果（拷贝屏幕，加上必要的文字说明）
四.源代码
1.#include <stdio.h>
void main()
{
int n,k,s[11][11];
int i,j;
printf("输入集合的个数");
scanf("%d",&n);
printf("输入子集的个数");
scanf("%d",&k);
for(i=1;i<=10;i++)
for(j=1;j<=10;j++)
s[i][j]=0;
for(i=1;i<=10;i++)
s[i][i]=1;
for(i=1;i<=10;i++)
s[i][1]=1;
for(i=2;i<=10;i++)
for(j=2;j<=10;j++)
s[i][j]=j*s[i-1][j]+s[i-1][j-1];
for(i=1;i<=10;i++)
{
for(j=1;j<=10;j++)
printf("%6d",s[i][j]);
printf("\n");
}
printf("n=%d,k=%d,总共个数为： %d \n", n,k,s[n][k]); }
2.#include <stdio.h>
int recursion(int a, int b);
void main()
{
int a,b,c;
printf("输入集合个数");
scanf("%d",&a);
printf("输入子集个数");
scanf("%d",&b);
c=recursion(a,b);
printf("划分的总个数为%d\n",c);
}
int recursion(int a, int b)
{
int c=0;
if(a==b)
{
return 1;
}
if(a==0||b==0||a<b)
{
return 0;
}
if(b==1)
{
return 1;
}
c=b*recursion(a-1,b)+recursion(a-1,b-1);
return c;
}
五.总结
递推在解决有规律的问题时候,很方便,但难找出其规律。