倒立乘法金字塔

Question

我有一个倒金字塔。顶部有数字1到N。 下面我们写出（N - 1）个数字，每个数字都是上面两个数字的乘积。每行都是这样。

例如（Ñ = 4）：

1  2  3  4 
    2  6  12 
     12  72 
      864 

我必须找到最终数目的第一位。这可以在O（N）中完成吗？也许有一个特定的算法？

Answer 1

首先让我们看看因素

1¹   2¹   3¹   4¹ 
    1¹⋅2¹  2¹⋅3¹  3¹⋅4¹ 
     1¹⋅2²⋅3¹ 2¹⋅3²⋅4¹ 
      1¹⋅2³⋅3³⋅4¹ 

如果你看你看杨辉三角形的指数。

因此，对于你的乘法金字塔的最后一个元素的表现公式是

 
pn = Πk=1,...,n nbinom(n-1,k-1) 

现在，你“只”必须得到结果的第一位dn。你可以通过计算

 
dn = floor(pn/10floor(log10(pn))) 
    = floor(10log10(pn)/10floor(log10(pn))) 
    = floor(10log10(pn) - floor(log10(pn))) 

为了避免巨大的数字做到这一点，你可以直接通过

 
log(pn) = Σk=1,...,n binom(n-1,k-1)⋅log(k) 

实例计算log(pn)：

 
d₄ = floor(10log₁₀(864) - floor(log₁₀(864))) 
    = floor(102.936513742 - 2) 
    = floor(100.936513742) 
    = floor(8.64) 
    = 8 

要计算log(pn)，你所要做的n乘法和n-1补充。在此之后，您只需计算一个固定数量的操作，所以这将在O(n)中运行。