根据递推式子C(m,n)=C(m-1,n)+C(m-1,n-1),求组合数C(m,n)。注意递推的终止条件是C(m,1)=m;以及一些m和n取值的一些特殊情况,如m < 0或n < 0或m < n时,C(m,n)值为0,m和n相等时,C(m,n)=1等。
时间: 2024-02-22 15:55:48 浏览: 141
binomial.m:该程序计算二项式系数 C(n,m)。-matlab开发
好的,根据递推式子C(m,n)=C(m-1,n)+C(m-1,n-1),我们可以写出如下的递归函数来求组合数C(m,n):
```python
def combination(m: int, n: int) -> int:
if m < 0 or n < 0 or m < n:
return 0
elif m == n or n == 0:
return 1
else:
return combination(m-1, n) + combination(m-1, n-1)
```
其中,递归终止条件包括:
- C(m,1)=m
- m和n相等时,C(m,n)=1
- m < 0或n < 0或m < n时,C(m,n)值为0
在递归的过程中,每次调用combination(m-1, n)和combination(m-1, n-1)来计算C(m,n)。最终返回C(m,n)的值即可。
需要注意的是,由于递归调用会创建新的栈帧,因此在计算大的组合数时可能会出现栈溢出的问题。可以使用循环或者记忆化搜索等方法来避免这个问题。
阅读全文