倒乘法金字塔
Inverted Multiplication Pyramid
我有一个倒金字塔。顶部是从 1 到 N 的数字。
下面，我们写出 (N – 1) 个数，每个数都是它上面两个数的乘积。每行依此类推。
例如 (n = 4):
1 2 3 4
2 6 12
12 72
864
我必须找到最终数字的第一位数字。这可以在 O(N) 中完成吗？也许有特定的算法？
首先让我们看一下因素
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)
现在你 "only" 必须得到结果的第一个数字 d<sub>n</sub>。您可以通过计算
dn = floor( pn / 10floor( log10(pn) ) )
= floor( 10log10(pn) / 10floor( log10(pn) ) )
= floor( 10log10(pn) - floor( log10(pn) ) )
为了避免巨大的数字，你可以直接通过
计算log(p<sub>n</sub>)
log(pn) = Σk=1,...,n binom(n-1,k-1)⋅log(k)
示例：
d₄ = floor( 10log₁₀(864) - floor( log₁₀(864) ) )
= floor( 102.936513742 - 2 )
= floor( 100.936513742)
= floor( 8.64 )
= 8
要计算 log(p<sub>n</sub>)，您必须进行 n 乘法和 n-1 加法.在此之后，您只需计算固定数量的操作，因此这将是 运行 in O(n).
我有一个倒金字塔。顶部是从 1 到 N 的数字。 下面，我们写出 (N – 1) 个数，每个数都是它上面两个数的乘积。每行依此类推。
例如 (n = 4):
1 2 3 4
2 6 12
12 72
864
我必须找到最终数字的第一位数字。这可以在 O(N) 中完成吗？也许有特定的算法？
首先让我们看一下因素
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)
现在你 "only" 必须得到结果的第一个数字 d<sub>n</sub>。您可以通过计算
dn = floor( pn / 10floor( log10(pn) ) ) = floor( 10log10(pn) / 10floor( log10(pn) ) ) = floor( 10log10(pn) - floor( log10(pn) ) )
为了避免巨大的数字，你可以直接通过
计算log(p<sub>n</sub>)
log(pn) = Σk=1,...,n binom(n-1,k-1)⋅log(k)
示例：
d₄ = floor( 10log₁₀(864) - floor( log₁₀(864) ) ) = floor( 102.936513742 - 2 ) = floor( 100.936513742) = floor( 8.64 ) = 8
要计算 log(p<sub>n</sub>)，您必须进行 n 乘法和 n-1 加法.在此之后，您只需计算固定数量的操作，因此这将是 运行 in O(n).