用动态规划算法求组合数C r n 。 例如,输入:5 3 则输出:10 c语言完整代码
时间: 2024-06-17 09:07:34 浏览: 15
动态规划算法可以用来求解组合数问题,其中C
r
n
表示从n个元素中选出r个元素的组合数。
动态规划的思路是:将问题分解成若干个子问题,通过子问题的解来求出原问题的解。对于组合数问题,可以使用递推公式:
C(r,n) = C(r-1,n-1) + C(r,n-1)
其中C(0,0) = 1, C(r,0) = 0 (r>0), C(r,n) = 0 (r>n)。
以下是C语言完整代码:
```
#include <stdio.h>
int main() {
int n, r;
scanf("%d %d", &n, &r);
int c[r+1][n+1];
// 初始化边界值
for (int i = 0; i <= r; i++) {
c[i] = 0;
}
for (int j = 0; j <= n; j++) {
c[j] = 1;
}
// 递推求解
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= n; j++) {
if (i > j) {
c[i][j] = 0;
} else {
c[i][j] = c[i-1][j-1] + c[i][j-1];
}
}
}
printf("%d", c[r][n]);
return 0;
}
```