pascal - 为大数计算 ${2n \choose n} - {2n \choose n-1}$ \PASCAL

Question

你好我需要计算这个二项式系数

${2n \choose n} - {2n \choose n-1}$

对于大数字，我不知道如何使用数据类型LongWord或QWord.

任何想法？:)

Answer 1

如果您尝试计算 n! 对于大于几百的 n，您将溢出帕斯卡浮点数，因此使用 (2n)!/(n!)^2 计算 {2n choose n} 的天真的方法可能不起作用，即使最终数字可能适合变成一个真正的没有溢出的，如(2n)！可能溢出。

您需要做的是混合乘法和除法，这样您就不会出现溢出或下溢。例如，假设 {2n choose n} 本身不会溢出，例如：

 X2nChoosen = 1.0;
 for i := 1 to n do
   X2nChoosen := X2nChooseN*(2*i)*(2*i-1)/(i*i);

Answer 2

在设计 Pascal 的时代，对数和计算尺是工程师常用的工具，以至于它导致包含一些基本的对数函数。

• ln(i)取正数的（自然）对数。“自然”是指e，欧拉常数。
• exp(i)计算欧拉常数的i, eⁱ 次方。

您可以利用对数恒等式integer在一定程度上克服限制。要使用二项式系数的阶乘公式，您可以编写：

type
    integerNonNegative = 0..maxInt;

function factorialLn(n: integerNonNegative): real;
var
    f: real value 0.0;
begin
    for n := n downto 2 do
    begin
        f := f + ln(n);
    end;
    
    factorialLn := f;
end;

function binomialCoefficient(
        protected n, k: integerNonNegative
    ): integerNonNegative;
begin
    binomialCoefficient := round(exp(
            factorialLn(n) -
            (factorialLn(k) + factorialLn(n - k))
        ));
end;

我认为，这很棒，因为它不需要您使用/加载额外的库，而且我们不要忘记学习它。例如，GMP，GNU 多精度库是 biiiiig，需要一些时间来沉浸其中。这样你就可以简单地写

binomialCoefficient(2 * n, n) - binomialCoefficient(2 * n, n - 1)

---

然而最好的方法当然是改进 你的 算法。在这种情况下，您对减小阶乘的幅度特别感兴趣。浏览一些处方我注意到你的表达看起来类似于

     ⎛ p − 1 ⎞   ⎛ p − 1 ⎞     p − 2 q  ⎛ p ⎞
     ⎜       ⎟ − ⎜       ⎟  =  ―――――――  ⎜   ⎟
     ⎝   q   ⎠   ⎝ q − 1 ⎠        p     ⎝ q ⎠

所以你做一些替换

                     p — 1  =  2 n                          │ + 1
                         p  =  2 n + 1

展开原来的等价

       ⎛ 2 n ⎞   ⎛  2 n  ⎞     2 n + 1 − 2 n  ⎛ 2 n + 1 ⎞
       ⎜     ⎟ − ⎜       ⎟  =  ―――――――――――――  ⎜         ⎟
       ⎝  n  ⎠   ⎝ n − 1 ⎠        2 n + 1     ⎝    n    ⎠

现在我们得到了一个产品而不是一个差异，我们扩展并合并它：

2 n + 1 − 2 n  ⎛ 2 n + 1 ⎞        1         (2 n + 1)!
―――――――――――――  ⎜         ⎟  =  ―――――――  ―――――――――――――――――
   2 n + 1     ⎝    n    ⎠     2 n + 1  n! (2 n + 1 − n)!

                                  1      (2 n)! (2 n + 1)   │
                            =  ―――――――  ―――――――――――――――――   │ cancel 2n+1
                               2 n + 1     n! (n + 1)!      │

                                  (2 n)! 
                            =  ―――――――――――
                               n! (n + 1)!

                                 2 n
                               ∏        i
                                 i = 1
                            =  ―――――――――――――――――――――――
                                 n
                               ∏        i   n! (n + 1)
                                 i = 1

                                 n            2 n
                               ∏        i   ∏           i
                                 i = 1        i = n + 1
                            =  ――――――――――――――――――――――――――
                                 n
                               ∏        i   n! (n + 1)
                                 i = 1

                                           2 n
                               (n + 1)   ∏           i
                                           i = n + 2
                            =  ――――――――――――――――――――――――――
                                 
                               (n + 1)   n!

                                 2 n
                               ∏           i
                                 i = n + 2
                            =  ―――――――――――――
                                    n!

另一方面，这表明我们只需要n − 2迭代。换句话说，计算以下不需要对数引入的任何开销，但同样精确，而且您不会超过 的限制integer，最后但并非最不重要的是它更快：

r := 1.0;
for i := 2 to n do
begin
    r := r / i * (n + i);
end;
writeLn(round(r));

这只是以程序风格编写的以下内容：

                   8! / 5!                     6 ⋅ 7 ⋅ 8
                   ―――――――  =  ―――――――――――――――――――――――――
                      3!       1 ⋅ 2 ⋅ 3

                                6       7       8
                            =  ―――  ⋅  ―――  ⋅  ―――
                                1       2       3

整齐吧？