首页 > 代码库 > 递归--递推之组合数
递归--递推之组合数
排列在上一篇中已经写到,是个典型的深搜题,下面是介绍的组合数, 组合的基本定义是, 但是除了用这种传统的方法来求,可以用递归的方式或者是递推的方式来求, 说道递推,只要会递归, 就会递推了。关键的一部是递推式,可以定义一个函数func(int n, int k); 表示求的值,公式先放在这func(n, k) = func(n-1, k-1)+func(n-1,k);
意思就是在n中选去k个数的组合一个多少个,这时就要分两种情况, 一种是选出一组数中包含最后一个元素,它的值就是func(n - 1, k - 1), 就是再从剩下的n - 1个元素中来选k - 1个, 还有一种就是不含最后一个元素, 那就是func(n - 1, k); 就是从剩下的n - 1个中选出k个来, 剩下的就是边界问题,一个就是当k为0的时候和n=k的时候,就是, 所以就是1, 还有就是= 1;还有当n < k的时候为0, 掌握好这些条件,写代码应该很轻松了
方法一(递归版):
1 #include <stdio.h> 2 3 int func(int n, int k) 4 { 5 if(k == n || k == 0) 6 return 1; 7 if(n == 0 || n < k) 8 return 0; 9 return func(n - 1, k - 1) + func(n - 1, k);10 }11 int main()12 {13 int n, k;14 while(~scanf("%d %d", &n, &k))15 {16 printf("%d\n", func(n, k));17 }18 19 return 0;20 }
方法二(递推版dp):
1 #include <stdio.h> 2 3 int main() 4 { 5 int dp[100][100]; 6 dp[1][1] = 1; 7 for(int i = 1; i < 100; i++) 8 { 9 dp[i][0] = 1;10 }11 for(int i = 2; i < 100; i++)12 {13 for(int j = 1; j <= i; j++)14 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];15 }16 int n, k;17 while(scanf("%d %d", &n, &k) == 2)18 {19 printf("%d\n", dp[n][k]);20 }21 return 0;22 }
递归--递推之组合数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。