解题思路:首先找出递归关系,一个元素n,分为k份的集合,可以来自n-1个元素,k份集合多了一个元素,将新元素随机加到任何一份中,或,n-1个元素,k-1份,新元素单独作为一份,用数学关系式表示:f(n,k)=k*f(n-1,k)+f(n-1,k-1)
注意事项:递归最重要的是注意递归边界,这里的条件为n和k都要大于0,n>=k
参考代码:
#include<stdio.h>
long long f(int n,int k)
{
if (n<k) return 0;
if (n==0||k==0) return 0;
if (n==k||k==1) return 1; //只分成一份,或n个分成n份,都是只有一种分法
return k*f(n-1,k)+f(n-1,k-1);
}
int main()
{
int n,k;
cin>>n>>k;
long long sum=f(n,k);
cout<<sum;
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题9.1 (Java代码)浏览:466 |
Pascal三角 (C语言代码)格式错误浏览:514 |
DNA (C语言描述,蓝桥杯)浏览:1539 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:530 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:527 |
Hello, world! (C语言代码)浏览:807 |
盐水的故事 (C语言代码)浏览:1475 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:555 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:417 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:500 |