4

我们如何打印出所有可以表示为 64 位长整数的完美幂：4, 8, 9, 16, 25, 27, .... 完美幂是可以写成 ab 的整数 a并且b≥2。这不是作业问题，我在算法设计书的求职面试问题部分找到了它。提示，这一章是基于优先级队列的。

我的大多数想法本质上都是二次的，不断寻找能力，直到它们不再适合 64 位，但这不是面试官会寻找的。另外，我无法理解 PQ 在这里的帮助。

4

3 回答 3

4

使用一个小的优先级队列，每个电源一个条目，是列出数字的合理方法。请参阅以下 python 代码。

import Queue             # in Python 3 say:  queue
pmax, vmax = 10, 150
Q=Queue.PriorityQueue(pmax)
p = 2
for e in range(2,pmax):
    p *= 2
    Q.put((p,2,e))

print 1,1,2
while not Q.empty():
    (v, b, e) = Q.get()
    if v < vmax:
        print v, b, e
        b += 1
        Q.put((b**e, b, e))

使用上面代码中的 pmax、vmax，它会产生以下输出。对于建议的问题，将pmaxandvmax替换为64and 2**64。

1 1 2
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
100 10 2
121 11 2
125 5 3
128 2 7
144 12 2

该方法的复杂度为 O(vmax^0.5 * log(pmax))。这是因为完美正方形的数量比完美立方体、四次方等的数量占主导地位，并且对于每个正方形，我们都进行 O(log(pmax)) 工作get并进行put排队操作。对于更高的功率，我们在计算时会做 O(log(pmax)) 工作b**e。

当 时vmax,pmax =64, 2**64，将有大约 2*(2^32 + 2^21 + 2^16 + 2^12 + ...) 队列操作，即大约 2^33 队列操作。

添加注释：此注释针对 cf16 的评论，“仅注释一条，我不认为“完美正方形的数量优于完美立方体的数量，四次方等。” 它们都是无限的。但是，是的，如果我们考虑有限集”。的确，在事物的整体数学方案中，基数是相同的。也就是说，如果P(j)是整数的所有j' 次幂的集合，则P(j) == P(k)所有整数的基数j,k > 0。任意两组幂的元素都可以相互一一对应。

然而，当以升序计算完美幂时，无论计算多少次，无论是否有限，传递平方的工作都超过了任何其他幂。对于任何给定的x ， x区域中的完美k次幂的密度随着k的增加呈指数下降。随着x的增加， x区域中完美k次方的密度与 ( x 1/k )/ x成正比，因此随着x的增加，与平方相比，三次方、四次方等变得非常罕见。

作为一个具体的例子，在 1e8 和 1e9 之间的完美幂中，(2; 3; 4; 5; 6) 次方的数量约为 (21622; 535; 77; 24; 10)。1e8 和 1e9 之间的平方数是任何高于平方数的实例的 30 倍以上。以下是两个数的完美平方数与更高完美幂数的比值：10¹⁰–10¹⁵，r≈301；10¹⁵–10²⁰，r≈2K；10²⁰–10²⁵，r≈15K；10²⁵–10³⁰，r≈100K。简而言之，随着x的增加，当完美的幂按升序传递时，正方形越来越占主导地位。

于 2012-10-19T06:38:47.970 回答
2

优先级队列有助于，例如，如果您想避免输出中的重复，或者如果您想列出特别排序的值。

优先队列通常可以用排序代替，反之亦然。因此，您可以生成 a b的所有组合，然后对结果进行排序并删除相邻的重复项。在这个应用程序中，这种方法似乎有点轻微但可能不会像姐妹答案之一所见证的那样显着降低内存效率。

如果您设法在执行过程中删除重复项，则优先级队列可能优于排序；或者如果您想避免存储和处理要在内存中生成的整个结果。另一个姐妹的答案是后者的一个例子，但只要稍作修改，它就可以很容易地做到这两点。

在这里，一个数组占用了大约 16 GB 的 RAM，而一个少于 64 个项目的队列在最坏的情况下占用了几千字节。如此巨大的内存消耗差异也转化为 RAM 访问时间与缓存访问时间的差异，因此即使底层数据结构通过维护自身而产生一些开销并且与朴素算法相比需要更多指令，但内存精简算法最终可能会更快使用排序。

因为输入的大小是固定的，所以从技术上讲，您想到的方法本质上是二次方的，这在技术上是不可能的。有两个嵌套循环不会使算法成为二次的，直到你可以说每个这样的循环的上限与输入大小成正比，甚至通常不是这样）。真正重要的是最里面的逻辑实际执行了多少次。

在这种情况下，竞争是在可行常数和不可行常数之间进行的。

于 2012-10-19T07:05:01.827 回答
1

我可以看到优先级队列有意义的唯一方法是，您希望在数字可用时以严格递增的顺序打印数字，当然不要两次打印任何数字。因此，您从一个素数生成器开始（它使用 Eratosthenes 筛或一些更智能的技术来生成序列 2、3、5、7、11，...）。您首先将表示 2^2 = 4 的三元组放入队列中。然后你重复一个过程，从队列中删除最小的项目（具有最小求幂结果的三元组），打印它，将指数加一，然后将它放回队列（其优先级由新的结果确定）取幂）。您可以将此过程与根据需要生成新素数的过程交错（有时在输出 p^2 之前）。

由于我们可能拥有的最大指数基数是 2^32 (2^32)^2 = 2^64，因此队列中的元素数不应超过小于 2^32 的素数数，显然是 203,280,221，我猜这是一个易于处理的数字。

于 2012-10-19T05:37:19.777 回答