15

可能的重复：
第 n 个丑数
找到表达式 (2^x)*(3^y)*(5^z) 的第 K 个最小数

我想知道如何以快速而优雅的方式解决这个问题：

我们定义每个可以写成以下形式的数字n的“丑陋” ：2^x * 3^y * 5^z;，其中 x,y 和 z 是自然数。找到第 1500 个丑数。

例如，第一个“丑陋”的数字是：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

我试图通过这种方式使用蛮力解决这个问题：

import itertools as it

def is_ugly(n):
    '''Return `True` if *n* is an ugly number.'''

    if n == 1:
        return True
    while not n % 2:
        n //= 2
    while not n % 3:
        n //= 3
    while not n % 5:
        n //= 5
    return n == 1

def nth_ugly(n):
    '''Return the nth ugly number.'''

    num = 0
    for i in it.count(1):
        if is_ugly(i):
            num += 1
            if num == n:
                return i

但这需要相当多的时间，我想找到一个更快更好的解决方案。

我知道丑数的主要因素，但我想不出按照正确顺序生成这些数字的方法。

我认为必须有一种方法可以生成这些数字，而无需检查所有数字。问题是，主要因子的指数似乎是随机分布的。

看这张表：

n   |number| x | y | z |
------------------------
1   |  1   | 0 | 0 | 0 |
------------------------
2   |  2   | 1 | 0 | 0 |
------------------------
3   |  3   | 0 | 1 | 0 |
------------------------
4   |  4   | 2 | 0 | 0 |
------------------------
5   |  5   | 0 | 0 | 1 |
------------------------
6   |  6   | 1 | 1 | 0 |
------------------------
7   |  8   | 3 | 0 | 0 |
------------------------
8   |  9   | 0 | 2 | 0 |
------------------------
9   |  10  | 1 | 0 | 1 |
------------------------
10  |  12  | 2 | 1 | 0 |
------------------------
11  |  15  | 0 | 1 | 1 |
------------------------
12  |  16  | 4 | 0 | 0 |
------------------------
13  |  18  | 1 | 2 | 0 |
------------------------
14  |  20  | 2 | 0 | 1 |
------------------------
15  |  24  | 3 | 1 | 0 |
------------------------

如您所见，x、y 和 z 值似乎不遵循任何规则。

你们中有人能找到解决这个问题的方法吗？

我正在考虑尝试将问题划分为不同的部分。由于问题是由指数的随机性决定的，我可以尝试独立生成 2s、3s、5s 的幂，然后生成 2^x*3^y、2^x*5^z 等形式的数字。最后把它们放在一起，但我不知道这是否能解决我的问题。

4

4 回答 4

11

这是一个完整的解决方案。O(n) 复杂度，它按顺序生成每个数字。

# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF

n = 15
bases = [2, 3, 5]

nums = [1] * n
candidates_indexes = [0 for _ in bases]
candidates = [base for base in bases]

for i in range(1, n):
    nextn = min(candidates)
    nums[i] = nextn

    for index, val in enumerate(candidates):
        if val == nextn:
            candidates_indexes[index] += 1
            candidates[index] = bases[index] * nums[candidates_indexes[index]]

print(nums)
于 2011-09-07T17:20:44.667 回答
2

这是使用堆的解决方案。这个想法是我们跟踪指数以及丑陋的产品。对于每次迭代，该算法最多执行 3 个 find_min 操作和 3 个插入操作，find_mins 可能是多余的，因为您可以通过将一个添加到任何指数来获得每个操作，并且存在三个指数。我们执行了 3 次插入，因为我们向每个指数添加一个并将其插入到堆中。为了找到第 n 个丑数，我们因此必须执行 6 * O(log n) 的 N 次操作，因此该算法的时间复杂度为 O(n log n)。堆本身，因为每次迭代只能以恒定的量增长，所以是 SPACE(O(n))

>>> import heapq, itertools
>>> class UglyGen(object):
...     def __init__(self, x, y, z):
...         self.x, self.y, self.z = x, y, z
...         self.value = 2**self.x * 3**self.y * 5**self.z
...     def incr(self):
...         x, y, z = self.x, self.y, self.z
...         return (UglyGen(x+1, y, z),
...                 UglyGen(x, y+1, z),
...                 UglyGen(x, y, z+1))
...     def __lt__(self, other):
...         if not isinstance(other, UglyGen):
...             return NotImplemented
...         return self.value < other.value
... 
>>> def gen_ugly():
...     gens = [UglyGen(0, 0, 0)]
...     last = 0
...     while gens:
...         while gens[0].value == last:
...             heapq.heappop(gens)
...         top = heapq.heappop(gens)
...         succ_items = top.incr()
...         for succ in succ_items:
...             heapq.heappush(gens, succ)
...         last = top.value
...         yield last
... 
>>> def find_nth_ugly(n):
...     for n0, u in itertools.izip(xrange(n), gen_ugly()):
...         pass
...     return u
... 
>>> find_nth_ugly(15)
24
于 2011-09-07T18:10:33.303 回答
1

使用一个列表（以下代码中的 n）存储所有 prev 丑数，下一个丑数是大于 n[-1] 的 (n*2, n*3, n*5) 的最小数： 

n = [1]
while len(n) < 1500:
    n.append(min([next(x*s for x in n if x*s>n[-1]) for s in (2,3,5)]))    
print n[-1]

这是一个 O(n^2) 解决方案，所以不要尝试大数字。

于 2011-09-07T13:27:01.147 回答
0

我建议你逐步解决这个问题，并将你找到的所有丑陋的数字存储在一个列表中。

那么当检查一个数字是否丑陋时，你只需要检查它是否是你的数字之一乘以 2、3 或 5。

编辑：我只是尝试像这样实现

ugly = [1]
candidate = 2
while len(ugly) < 1500:
    for u in ugly:
        if any([(u * x == candidate) for x in (2, 3 ,5)]):
            ugly.append(candidate)
            break
    candidate += 1

print ugly[-1]

但这种方法毫无希望地停滞不前。太天真了。:) 而是使用某种 Eratosthenes 筛。

于 2011-09-07T12:19:27.103 回答