Ani*_*tti 40 algorithm math primes factors hamming-numbers
只有素数因子为2,3或5的数字称为丑陋数字.
例:
1,2,3,4,5,6,8,9,10,12,15 ......
1可以被认为是2 ^ 0.
我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.
我写了一个简单的程序来计算给定数字是否丑陋.对于n> 500 - 它变得超级慢.我尝试使用memoization - 观察:ugly_number*2,ugly_number*3,ugly_number*5都很难看.即便如此,它也很慢.我尝试使用log的一些属性 - 因为这会将这个问题从乘法减少到另外 - 但是,运气不大.想与大家分享这个.任何有趣的想法？
使用类似于"Eratosthenes的筛子"的概念(感谢Anon)
for (int i(2), uglyCount(0); ; i++) {
if (i % 2 == 0)
continue;
if (i % 3 == 0)
continue;
if (i % 5 == 0)
continue;
uglyCount++;
if (uglyCount == n - 1)
break;
}
我是第n个难看的数字.
即便这样也很慢.我想找到第1500个难看的数字.
Nik*_*bak 40
一个简单的Java快速解决方案.使用Anon描述的方法..
这里TreeSet只是一个能够返回其中最小元素的容器.(不存储重复项.)
int n = 20;
SortedSet<Long> next = new TreeSet<Long>();
next.add((long) 1);
long cur = 0;
for (int i = 0; i < n; ++i) {
cur = next.first();
System.out.println("number " + (i + 1) + ": " + cur);
next.add(cur * 2);
next.add(cur * 3);
next.add(cur * 5);
next.remove(cur);
}
由于第1000个丑陋的数字是51200000,因此存储它们bool[]并不是一个真正的选择.
编辑
作为工作中的娱乐(调试愚蠢的Hibernate),这里是完全线性的解决方案.感谢marcog的想法!
int n = 1000;
int last2 = 0;
int last3 = 0;
int last5 = 0;
long[] result = new long[n];
result[0] = 1;
for (int i = 1; i < n; ++i) {
long prev = result[i - 1];
while (result[last2] * 2 <= prev) {
++last2;
}
while (result[last3] * 3 <= prev) {
++last3;
}
while (result[last5] * 5 <= prev) {
++last5;
}
long candidate1 = result[last2] * 2;
long candidate2 = result[last3] * 3;
long candidate3 = result[last5] * 5;
result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
}
System.out.println(result[n - 1]);
我们的想法是计算a[i],我们可以使用a[j]*2一些j < i.但我们还需要确保1)a[j]*2 > a[i - 1]和2)j尽可能小.
然后,a[i] = min(a[j]*2, a[k]*3, a[t]*5).
Ano*_*on. 10
我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.
我写了一个简单的程序来计算给定数字是否丑陋.
这看起来像是你试图解决的问题的错误方法 - 这是一个shlemiel算法.
您是否熟悉用于寻找质数的Eratosthenes筛选算法？类似的东西(利用每个丑陋的数字是另一个丑陋数字的2,3或5倍的知识)可能更好地解决这个问题.
通过与Sieve的比较,我并不是说"保持一系列的bool并消除你上升的可能性".我更多地指的是基于先前结果生成解决方案的一般方法.如果Sieve得到一个数字,然后从候选集中删除它的所有倍数,那么这个问题的一个好算法将从一个空集开始,然后将每个丑陋数字的正确倍数添加到那个.
我的回答是指Nikita Rybak给出的正确答案.因此,人们可以看到从第一种方法的想法转变为第二种方法的转变.
from collections import deque
def hamming():
h=1;next2,next3,next5=deque([]),deque([]),deque([])
while True:
yield h
next2.append(2*h)
next3.append(3*h)
next5.append(5*h)
h=min(next2[0],next3[0],next5[0])
if h == next2[0]: next2.popleft()
if h == next3[0]: next3.popleft()
if h == next5[0]: next5.popleft()
从Nikita Rybak的第一种方法改变的是,不是将下一个候选者添加到单个数据结构中,即树集,而是可以将它们中的每一个分别添加到3个FIFO列表中.这样,每个列表将始终保持排序,并且下一个最小候选者必须始终位于这些列表中的一个或多个列表的头部.
如果我们不再使用上面三个列表,我们将在Nikita Rybak的回答中得到第二个实现.这是通过仅在需要时评估那些候选者(包含在三个列表中)来完成的,因此不需要存储它们.
简单地说:
在第一种方法中,我们将每个新候选者放入单一数据结构中,这很糟糕,因为太多事情变得不明智.每次我们对结构进行查询时,这种糟糕的策略都不可避免地需要O(log(树大小))时间复杂度.但是,通过将它们放入单独的队列中,您将看到每个查询仅占用O(1),这就是整体性能降低到O(n)的原因!这是因为三个列表中的每一个都已经自行排序.
我相信你可以在亚线性时间内解决这个问题,可能是O(n ^ {2/3}).
为了让你的想法,如果你简化问题,让只有2和3的因素,就可以实现为O(n ^ {1/2})时开始通过搜索两个最小的功率至少是一样大第n个丑陋的数字,然后生成一个O(n ^ {1/2})候选者列表.这段代码应该让你知道如何做到这一点.它依赖于这样的事实,即仅包含2和3的幂的第n个数具有素数因子分解,其指数之和为O(n ^ {1/2}).
def foo(n):
p2 = 1 # current power of 2
p3 = 1 # current power of 3
e3 = 0 # exponent of current power of 3
t = 1 # number less than or equal to the current power of 2
while t < n:
p2 *= 2
if p3 * 3 < p2:
p3 *= 3
e3 += 1
t += 1 + e3
candidates = [p2]
c = p2
for i in range(e3):
c /= 2
c *= 3
if c > p2: c /= 2
candidates.append(c)
return sorted(candidates)[n - (t - len(candidates))]
同样的想法应该适用于三个允许的因素,但代码变得更加复杂.因子分解的幂的总和下降到O(n ^ {1/3}),但是你需要考虑更多的候选者,O(n ^ {2/3})更精确.
这里有很多很好的答案，但我无法理解这些答案，特别是这些答案中的任何一个（包括已接受的答案）如何保持Dijkstra 原始论文中的公理 2 ：
公理 2。如果 x 在序列中，那么 2 * x、3 * x 和 5 * x 也在序列中。
经过一些白板，很明显公理 2不是算法每次迭代的不变量，而是算法本身的目标。在每次迭代中，我们尝试恢复公理 2 中的条件。如果last是结果序列中的最后一个值S，公理 2 可以简单地改写为：
对于一些
x中S，在未来的价值S是最小的2x，3x以及5x，那就是大于last。我们称这个公理为 2'。
因此，如果我们可以发现x，我们可以计算出最小的2x，3x和5x在固定时间，并将其添加到S。
但是我们如何找到x呢？一种方法是，我们不这样做；相反，当我们添加新元素e来S，我们计算2e，3e和5e，并将它们添加到最低优先级队列。由于此操作保证e在 中S，因此简单地提取 PQ 的顶部元素满足公理 2'。
这种方法有效，但问题是我们生成了一堆可能最终不会使用的数字。请参阅此答案以获取示例；如果用户想要S（5）中的第 5 个元素，则此时的 PQ 成立6 6 8 9 10 10 12 15 15 20 25。我们不能浪费这个空间吗？
事实证明，我们可以做得更好。而不是存储所有这些数字，我们只是维护每个倍数，即三个柜台2i，3j和5k。这些是 中下一个数字的候选者S。当我们选择其中之一时，我们只会增加相应的计数器，而不是其他两个。通过这样做，我们不会急切地生成所有倍数，从而用第一种方法解决了空间问题。
让我们看看 的试运行n = 8，即数字9。我们从 开始1，正如 Dijkstra 论文中的公理 1 所述。
+---------+---+---+---+----+----+----+-------------------+
| # | i | j | k | 2i | 3j | 5k | S |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2 | 3 | 5 | {1} |
+---------+---+---+---+----+----+----+-------------------+
| 1 | 1 | 1 | 1 | 2 | 3 | 5 | {1,2} |
+---------+---+---+---+----+----+----+-------------------+
| 2 | 2 | 1 | 1 | 4 | 3 | 5 | {1,2,3} |
+---------+---+---+---+----+----+----+-------------------+
| 3 | 2 | 2 | 1 | 4 | 6 | 5 | {1,2,3,4} |
+---------+---+---+---+----+----+----+-------------------+
| 4 | 3 | 2 | 1 | 6 | 6 | 5 | {1,2,3,4,5} |
+---------+---+---+---+----+----+----+-------------------+
| 5 | 3 | 2 | 2 | 6 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 6 | 4 | 2 | 2 | 8 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 7 | 4 | 3 | 2 | 8 | 9 | 10 | {1,2,3,4,5,6,8} |
+---------+---+---+---+----+----+----+-------------------+
| 8 | 5 | 3 | 2 | 10 | 9 | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+
请注意，它S在第 6 次迭代时没有增长，因为6之前已经添加了最小候选。为避免必须记住所有先前元素的问题，我们修改算法以在相应倍数等于最小候选时增加所有计数器。这将我们带到了以下 Scala 实现。
def hamming(n: Int): Seq[BigInt] = {
@tailrec
def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
val leq = factor * xs(x) <= xs.last
if (leq) next(x + 1, factor, xs)
else x
}
@tailrec
def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
if (xs.size < n) {
val a = next(i, 2, xs)
val b = next(j, 3, xs)
val c = next(k, 5, xs)
val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min
val x = a + (if (2 * xs(a) == m) 1 else 0)
val y = b + (if (3 * xs(b) == m) 1 else 0)
val z = c + (if (5 * xs(c) == m) 1 else 0)
loop(x, y, z, xs :+ m)
} else xs
}
loop(0, 0, 0, IndexedSeq(BigInt(1)))
}