根据递推式子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 08:55:48 浏览: 69
好的,根据递推式子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)的值即可。
需要注意的是,由于递归调用会创建新的栈帧,因此在计算大的组合数时可能会出现栈溢出的问题。可以使用循环或者记忆化搜索等方法来避免这个问题。
相关问题
根据递推式子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等。用c语言编写程序
以下是用 C 语言编写的程序,能够根据递推式子计算组合数 C(m,n):
```c
#include <stdio.h>
int combination(int m, int n) {
if (m < 0 || n < 0 || m < n) {
return 0;
} else if (m == n || n == 0) {
return 1;
} else {
int C[m+1][n+1];
for (int i = 0; i <= m; i++) {
C[i][0] = 1;
}
for (int j = 1; j <= n; j++) {
C[0][j] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
return C[m][n];
}
}
int main() {
int m, n;
printf("请输入m和n的值:");
scanf("%d %d", &m, &n);
printf("C(%d, %d) = %d\n", m, n, combination(m, n));
return 0;
}
```
程序中,我们使用一个二维数组 `C` 来保存计算出来的组合数。首先,我们对 `C` 进行初始化,使得 `C[i][0] = 1`,`C[0][j] = 0`。然后,我们使用双重循环来计算 `C(m,n)`,即 `C[m][n] = C[m-1][n] + C[m-1][n-1]`。最后,输出计算出来的结果即可。
需要注意的是,当 `m < 0` 或 `n < 0` 或 `m < n` 时,组合数的值为 0。当 `m == n` 或 `n == 0` 时,组合数的值为 1。这些情况也需要在程序中进行判断。
可以通过找规律发现,当m=1时,f(n,m)=n;当m>1时,有以下非递推规律: 当 n < m 时, f(n,m) = [f(n-1,m) + m] % n 当 n >= m 时,f(n,m) = f(n - n/m, m) - (n % m) 其中,[x]表示向下取整函数。 这个规律的时间复杂度为O(1),空间复杂度为O(1)。 将此规律转化为c语言或者c++代码
好的,以下是 C++ 代码实现:
```cpp
#include <iostream>
using namespace std;
int josephus(int n, int m) {
int ans = 0;
for (int i = 2; i <= n; ++i) {
ans = (ans + m) % i;
}
return ans + 1;
}
int main() {
int n, m;
cin >> n >> m;
cout << josephus(n, m) << endl;
return 0;
}
```
以上代码实现了非递归规律的方式,时间复杂度为 O(n),空间复杂度为 O(1)。