使用修正公式计算二项式系数时答案错误

siesta 发表于 Dev

午休

我正在尝试使用以下公式编写一个函数来计算二项式系数：

我遇到的问题是我无法获得正确的答案。这是我尝试编写函数的两种方式的示例。

def binomial(n, i):
    total = 0

    for j in range(1, (n-i+1)):
        n = float(n)
        i = float(i)
        j = float(j)        

        product = (i+j) / j

        if total == 0:
            total = product
        else:
            total = total * product

    print '%.f' %total

或者像这样使用numpy

import numpy as np

def binomial_np(n, i):
    array = np.zeros(n-i+1)

    for j in range(1, (n-i+1)):
        s = float(j)
        n = float(n)
        i = float(i)

        array[j] = (i+s)/s

    array = array[1 : ]
    array = np.prod(array)    

    print '%.f' %array

两种功能都能产生几乎正确的结果。在论坛上四处逛逛后，我确实找到了其他一些可以产生正确结果的示例，例如Python Binomial Coefficient中的一个示例。

import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == x:
    print(1)
elif y == 1:         # see georg's comment
    print(x)
elif y > x:          # will be executed only if y != 1 and y != x
    print(0)
else:                # will be executed only if y != 1 and y != x and x <= y
    a = math.factorial(x)
    b = math.factorial(y)
    c = math.factorial(x-y)  # that appears to be useful to get the correct result
    div = a // (b * c)
    print(div)

我真正要解决的问题是，我编写公式的方式是否有问题，或者由于Python中的float和小数位数而无法以这种方式获得正确的答案。希望有人能为我在这里做错的事情指明正确的方向。

罗里·道顿（Rory Daulton）

轻微的差异似乎来自使用浮点算法。但是，如果确定n并且i是整数，则例程中根本不需要浮点值。你可以做

def binomial(n, i):
    result = 1
    for j in range(1, n-i+1):
        result = result * (i+j) // j
    return result

之所以有效，是因为两个连续数字的乘积可被1 * 2整除，三个连续数字的乘积可被1 * 2 * 3整除，... ni个连续数字的积可被（ni）整除！上面代码中的计算被排序为仅得到整数的结果，因此您可以得到确切的答案。这是因为我的代码不像(i+j)/j您的代码那样计算。它计算result * (i+j)，然后除以j。该代码在将整数值保持尽可能小方面也做得相当好，这将提高速度。

如果是，如果n或是i浮点数而不是整数，则此方法可能无效。另请注意，此代码不会检查0 <= i <= n，应该这样做。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。