уродливое число - PullRequest
Новая
       71

уродливое число

37 голосов
/ 05 января 2011

Числа, чьи единственные простые множители 2, 3 или 5, называются некрасивыми числами.

Пример:

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

1 можно рассматривать как 2 ^ 0.

Я работаю над поиском уродливого номера. Обратите внимание, что эти числа чрезвычайно редко распределяются, так как n становится большим.

Я написал тривиальную программу, которая вычисляет, является ли данное число безобразным или нет. Для n> 500 - это стало очень медленно. Я попытался использовать памятку - наблюдение: ugly_number * 2, ugly_number * 3, ugly_number * 5 все безобразно. Даже при том, что это медленно. Я попытался использовать некоторые свойства журнала - так как это уменьшит эту проблему от умножения до сложения - но пока не так много удачи. Мысль поделиться этим со всеми вами. Есть интересные идеи?

Использование концепции, аналогичной "Сите Эратосфена" (спасибо, Анон) 

    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;
    }

I-е уродливое число.

Даже это довольно медленно. Я пытаюсь найти 1500-е уродливое число.

Ответы [ 12 ]

0 голосов
/ 30 августа 2015

Вот еще один O (n) подход (решение Python), основанный на идее объединения трех отсортированных списков. Задача состоит в том, чтобы найти следующее уродливое число в порядке возрастания. Например, мы знаем, что первые семь уродливых чисел [1,2,3,4,5,6,8]. Уродливые числа на самом деле из следующих трех списков:

  • список 1: 1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2, 6 * 2, 8 * 2 ... (умножить каждое уродливое число на 2)
  • список 2: 1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3, 6 * 3, 8 * 3 ... (умножьте каждое уродливое число на 3)
  • список 3: 1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5, 6 * 5, 8 * 5 ... (умножить каждое уродливое число на 5)

Таким образом, n-е уродливое число - это n-е число списка, объединенного из трех списков выше:

1, 1 * 2, 1 * 3, 2 * 2, 1 * 5, 2 * 3 ... 

def nthuglynumber(n):
    p2, p3, p5 = 0,0,0
    uglynumber = [1]
    while len(uglynumber) < n:
        ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
        next = min(ugly2, ugly3, ugly5)
        if next == ugly2: p2 += 1        # multiply each number
        if next == ugly3: p3 += 1        # only once by each
        if next == ugly5: p5 += 1        # of the three factors
        uglynumber += [next]
    return uglynumber[-1]
  1. ШАГ I: вычисление трех следующих возможных уродливых чисел из трех списков
    • ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
  2. ШАГ II, найдите одно следующее уродливое число как наименьшее из трех приведенных выше:
    • next = min(ugly2, ugly3, ugly5)
  3. ШАГ III: перемещение указателя вперед, если его уродливый номер был следующим уродливым числом
    • if next == ugly2: p2+=1
    • if next == ugly3: p3+=1
    • if next == ugly5: p5+=1
    • примечание: не с использованием if с elif или else
  4. ШАГ IV: добавление следующего уродливого номера в объединенный список uglynumber
    • uglynumber += [next]
0 голосов
/ 02 октября 2014

Эта проблема может быть решена в O (1).

Если мы уберем 1 и посмотрим на числа от 2 до 30, мы заметим, что есть 22 числа.

Теперь, для любого числа x из 22 чисел, указанных выше, будет число x + 30 между 31 и 60, что также ужасно.Таким образом, мы можем найти не менее 22 чисел от 31 до 60. Теперь для каждого некрасивого числа от 31 до 60 мы можем записать его как s + 30. Так что s тоже будет безобразным, так как s + 30 делится на 2, 3или 5. Таким образом, между 31 и 60 будет ровно 22 числа. Эта логика может повторяться для каждого блока из 30 чисел после этого.

Таким образом, будет 23 числа в первых 30 числах и 22 для каждых 30 после этого.То есть, первые 23 уродства будут происходить между 1 и 30, 45 уродств будут происходить между 1 и 60, 67 уродств будут происходить между 1 и 30 и т. Д.

Теперь, если мне дают n, скажем, 137, яможно увидеть, что 137/22 = 6,22.Ответ будет лежать между 6 * 30 и 7 * 30 или между 180 и 210. К 180 у меня будет 6 * 22 + 1 = 133-е уродливое число в 180. У меня будет 154-е уродливое число в 210. Поэтому я ищу4-е уродливое число (так как 137 = 133 + 4) в интервале [2, 30], которое равно 5. Тогда 137-е уродливое число равно 180 + 5 = 185.

Другой пример: если я хочу 1500-енекрасивое число, я считаю 1500/22 = 68 блоков.Таким образом, у меня будет 22 * ​​68 + 1 = 1497-е уродство в 30 * 68 = 2040. Следующие три уродства в блоке [2, 30] - 2, 3 и 4. Таким образом, наше необходимое уродство - в 2040 + 4 =2044.

Суть в том, что я могу просто составить список уродливых чисел между [2, 30] и просто найти ответ, выполнив поиск в O (1).

Страница:
...