15

重複の可能性:
n 番目の醜い数
式 (2^x)*(3^y)*(5^z) の K 番目に小さい数を見つける

この問題を迅速かつエレガントな方法で解決する方法を考えています。

2^x * 3^y * 5^z; の形式で記述できるすべての数値nを「醜い」と定義します。ここで、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 に答える
1

リスト (次のコードでは n) を使用して、前のすべての醜い数値を格納します。次の醜い数値は、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]

しかし、このアプローチは絶望的に停滞します。ナイーブすぎる。:)むしろエラトステネスのふるいのようなものを使用してください。

于 2011-09-07T12:19:27.103 に答える