用C语言写出题目p2822的代码
时间: 2024-03-20 15:44:18 浏览: 7
这道题目可以使用杨辉三角,或者组合数的性质,或者递推公式来求解。
方法一:使用杨辉三角
我们可以使用杨辉三角来求解组合数,即将组合数看作杨辉三角中的数,第 $n$ 行第 $m$ 个数即为 $\binom{n-1}{m-1}$,因此可以直接按照杨辉三角的方式递推求解。
时间复杂度为 $O(n^2)$。
C 语言代码:
```
#include <stdio.h>
int main()
{
int n, m;
while (scanf("%d%d", &n, &m), n || m)
{
long long c = 1;
for (int i = 1; i <= m; i ++ )
{
c = c * (n - i + 1) / i;
}
printf("%lld\n", c);
}
return 0;
}
```
方法二:使用组合数的性质
根据组合数的性质,我们可以有以下递推公式:
$$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$$
边界条件为:
$$\binom{n}{0}=\binom{n}{n}=1$$
因此,我们可以使用递推公式计算组合数,时间复杂度为 $O(n^2)$。
C 语言代码:
```
#include <stdio.h>
int main()
{
int n, m;
while (scanf("%d%d", &n, &m), n || m)
{
int c[n + 1][n + 1];
for (int i = 0; i <= n; i ++ )
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j ++ )
{
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
printf("%d\n", c[n][m]);
}
return 0;
}
```
方法三:使用递推公式
根据组合数的递推公式,我们可以得到以下递推公式:
$$\binom{n}{m}=\frac{n-m+1}{m}\binom{n}{m-1}$$
边界条件为:
$$\binom{n}{0}=1$$
因此,我们可以使用递推公式计算组合数,时间复杂度为 $O(n)$。
C 语言代码:
```
#include <stdio.h>
int main()
{
int n, m;
while (scanf("%d%d", &n, &m), n || m)
{
int c = 1;
for (int i = 1; i <= m; i ++ )
{
c = c * (n - i + 1) / i;
}
printf("%d\n", c);
}
return 0;
}
```