排列(Permutation) 和 组合(Combination) 是数学中的基本概念,主要用于计算不同情况下的选择方式。
原因: 计算组合数时,如果直接使用公式C(n, m) = n! / (m!(n-m)!),当n或m较大时,可能会导致数值溢出或精度问题。
解决方法: 使用递推公式C(n, m) = C(n-1, m-1) + C(n-1, m),或者使用动态规划的方法来计算组合数,可以有效避免数值溢出和精度问题。
def factorial(n):
if n == 0:
return 1
result = 1
for i in range(1, n + 1):
result *= i
return result
def combination(n, m):
if m > n:
return 0
return factorial(n) // (factorial(m) * factorial(n - m))
# 使用动态规划计算组合数
def combination_dp(n, m):
if m > n:
return 0
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, min(i, m) + 1):
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
return dp[n][m]
# 示例
print(combination(5, 2)) # 输出 10
print(combination_dp(5, 2)) # 输出 10
通过以上内容,您可以全面了解排列和组合的基础概念、优势、类型、应用场景以及常见问题的解决方法。
领取专属 10元无门槛券
手把手带您无忧上云