高级算法问题("Nice Triangle")：质数金字塔，其中每个数字都依赖于其上面的数字

Question

我目前正在为高级算法和数据结构考试做准备，我似乎就是解决不了下面的一个实践问题:

1.14) "Nice Triangle">

"nice"三角形的定义如下:

1. 三角形由三个不同的数组成，即前三个素数(2,3和5)。
2. 每个数字以以下方式依赖于它下面的两个数字。
   • 号码相同，生成的号码也相同。(2,2 =>2)
   • 号码不同，结果号码为剩余号码。(2,3 =>5)

给定一个长度为L的整数N，对应三角形的底边，确定顶部的最后一个元素

例如:给定N = 25555(因此L = 5)，三角形看起来像这样:

2
3 5
2 5 5
3 5 5 5
2 5 5 5 5

=比;2是这个例子的结果

每个数都是素数这个事实和这个问题有什么关系?

通过使用朴素的方法(简单地计算每一行)，可以得到O(L^2)的时间复杂度。然而，教授说，这对O(L)是可能的，但我就是找不到任何模式!!

Answer 1

我不确定为什么这个问题会在高级算法课程中使用，但是是的，你可以在O(l) = O(log n)时间内完成。

有几种方法可以做到这一点，但它们都依赖于认识到:

1. 对于问题语句，使用什么数字并不重要。我们用0、1和2代替2、3和5。然后
2. 如果a和b为输入数字，c为输出数字，则c = -(a+b) mod 3
3. 你可以用c = a+b mod 3来构建整个三角形，然后每隔一行就消去。

在O(log n)时间内有两种方法:

• 对于输入中的每个数字d，计算将其添加到最终和中的次数(称为k)，将所有kd mod 3加起来，然后如果从偶数位数开始，则将结果取零。每个数字需要常数时间。另外:
• 认识到您可以在常数时间内对n个大小的值进行算术运算。用n中所有数字的位掩码生成一个值，每个数字占用2位。然后，通过使用位操作，您可以在常数时间内从前一行计算每一行，总共需要O(log n)时间。

下面是第二种方法在python中的实现:

def niceTriangle(n):
# a vector of 3-bit integers mod 3
rowvec = 0
# a vector of 1 for each number in the row
onevec = 0
# number of rows remaining
rows = 0
# mapping for digits 0-9
digitmap = [0, 0, 0, 1, 1, 2, 2, 2, 2, 2]
# first convert n into the first row
while n > 0:
digit = digitmap[n % 10]
n = n//10
rows += 1
onevec = (onevec << 3) + 1
rowvec = (rowvec << 3) + digit
if rows%2 == 0:
# we have an even number of rows -- negate everything
rowvec = ((rowvec&onevec)<<1) | ((rowvec>>1)&onevec)
while rows > 1:
# add each number to its neighbor
rowvec += (rowvec >> 3)
# isolate the entries >= 3, by adding 1 to each number and
# getting the 2^2 bit
gt3 = ((rowvec + onevec) >> 2) & onevec
# subtract 3 from all the greater entries
rowvec -= gt3*3
rows -= 1
return [2,3,5][rowvec%4]