Уродливое число
Числа, чьи единственные простые множители составляют 2, 3 или 5, называются уродливыми числами.
Пример:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,...
1 можно рассматривать как 2^0.
Я работаю над поиском n-го уродливого номера. Обратите внимание, что эти числа чрезвычайно редко распределяются, так как n становится большим.
Я написал тривиальную программу, которая вычисляет, является ли данное число безобразным или нет. Для n > 500 - это стало очень медленно. Я попытался использовать памятку - наблюдение: ugly_number * 2, ugly_number * 3, ugly_number * 5 все безобразно. Даже при том, что это медленно. Я попытался использовать некоторые свойства журнала - так как это уменьшит эту проблему от умножения до сложения - но пока не так много удачи. Мысль поделиться этим со всеми вами. Есть интересные идеи?
Используя концепцию, похожую на "Сито Эратосфена" (спасибо 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;
}
я - это уродливое число.
Даже это довольно медленно. Я пытаюсь найти 1500-й уродливый номер.
12 ответов
Простое быстрое решение в Java. Использует подход, описанный Аноном.,
Вот 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);
}
С тысячного уродливого числа 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),
Я работаю над поиском n-го уродливого номера. Обратите внимание, что эти числа чрезвычайно редко распределяются, так как n становится большим.
Я написал тривиальную программу, которая вычисляет, является ли данное число некрасивым или нет.
Это похоже на неправильный подход к проблеме, которую вы пытаетесь решить, - это что-то вроде алгоритма Шлемиеля.
Вы знакомы с алгоритмом Сита Эратосфена для поиска простых чисел? Нечто подобное (использование знания, что каждое уродливое число в 2, 3 или 5 раз больше другого уродливого числа), вероятно, будет работать лучше для решения этой проблемы.
В сравнении с Ситом я не имею в виду "держать множество булев и исключать возможности по мере роста". Я больше ссылаюсь на общий метод генерации решений, основанный на предыдущих результатах. Если сито получает число, а затем удаляет все его кратные из набора кандидатов, хороший алгоритм для этой задачи будет начинаться с пустого набора, а затем к нему добавляются правильные кратные каждого уродливого числа.
Мой ответ относится к правильному ответу Никиты Рыбака. Чтобы можно было увидеть переход от идеи первого подхода к идее второго.
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()
Что отличается от первого подхода Никиты Рыбака, так это то, что вместо добавления следующих кандидатов в единую структуру данных, то есть в набор деревьев, можно добавить каждого из них по отдельности в 3 списка FIFO. Таким образом, каждый список будет постоянно отсортирован, и следующий наименьший кандидат всегда должен быть во главе одного или нескольких из этих списков.
Если мы исключим использование трех перечисленных выше списков, мы получим вторую реализацию в ответе Никиты Рыбака. Это делается путем оценки этих кандидатов (которые должны содержаться в трех списках) только при необходимости, так что нет необходимости хранить их.
Проще говоря:
При первом подходе мы помещаем каждого нового кандидата в единую структуру данных, и это плохо, потому что слишком много вещей смешиваются неразумно. Эта плохая стратегия неизбежно влечет за собой сложность времени O(log(размер дерева)) каждый раз, когда мы делаем запрос к структуре. Однако, поместив их в отдельные очереди, вы увидите, что каждый запрос занимает только O(1), и поэтому общая производительность снижается до O(n)!!! Это связано с тем, что каждый из трех списков уже отсортирован.
Я полагаю, что вы можете решить эту проблему в сублинейное время, возможно O(n^{2/3}).
Чтобы дать вам представление о том, что если вы упростите задачу, разрешив коэффициенты только 2 и 3, вы можете достичь времени O(n^{1/2}), начиная с поиска наименьшей степени двух, которая по крайней мере равна n-ое уродливое число, а затем генерирует список из O(n^{1/2}) кандидатов. Этот код должен дать вам представление, как это сделать. Он основан на том факте, что n-е число, содержащее только степени 2 и 3, имеет простую факторизацию, сумма показателей которой равна 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}), чтобы быть более точным.
Здесь много хороших ответов, но мне было трудно понять их, в частности, как любой из этих ответов, включая принятый, поддерживал аксиому 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'.
Этот подход работает, но проблема в том, что мы генерируем кучу чисел, которые мы можем не использовать. Посмотрите этот ответ для примера; если пользователь хочет 5-й элемент в S (5), PQ в этот момент имеет место 6 6 8 9 10 10 12 15 15 20 25, Можем ли мы не тратить это пространство впустую?
Оказывается, мы можем сделать лучше. Вместо того, чтобы хранить все эти числа, мы просто поддерживаем три счетчика для каждого из кратных, а именно: 2i, 3j, а также 5k, Это кандидаты на следующий номер в S, Когда мы выбираем один из них, мы увеличиваем только соответствующий счетчик, а не два других. Таким образом, мы не с готовностью генерируем все кратные числа, таким образом, решая проблему пространства с первым подходом.
Давайте посмотрим пробный пробег для n = 8т.е. число 9, Начнем с 1, как указано в аксиоме 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)))
}
В основном поиск может быть сделан O(n):
Учтите, что вы ведете частичную историю некрасивых чисел. Теперь на каждом шаге вы должны найти следующий. Оно должно быть равно числу из истории, умноженному на 2, 3 или 5. Выберите наименьшее из них, добавьте его в историю и отбросьте из него некоторые числа, чтобы наименьшее из списка, умноженное на 5, было больше, чем по величине.
Это будет быстро, потому что поиск следующего номера будет простым:
мин (самый большой * 2, самый маленький * 5, один из середины * 3),
это больше, чем самое большое число в списке. Если их мало, список всегда будет содержать несколько чисел, поэтому поиск числа, которое нужно умножить на 3, будет быстрым.
Вот правильное решение в ML. Функция ugly() вернет поток (ленивый список) чисел Хэмминга. Функция nth может использоваться в этом потоке.
При этом используется метод Sieve, следующие элементы рассчитываются только при необходимости.
datatype stream = Item of int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));
fun nth(s,1)=head(s)
| nth(s,n)=nth(tail(s),n-1);
fun merge(xs,ys)=if (head xs=head ys) then
cons(head xs,fn()=>merge(tail xs,tail ys))
else if (head xs<head ys) then
cons(head xs,fn()=>merge(tail xs,ys))
else
cons(head ys,fn()=>merge(xs,tail ys));
fun double n=n*2;
fun triple n=n*3;
fun ij()=
cons(1,fn()=>
merge(maps double (ij()),maps triple (ij())));
fun quint n=n*5;
fun ugly()=
cons(1,fn()=>
merge((tail (ij())),maps quint (ugly())));
Это был первый год работы CS:-)
Чтобы найти n-ое уродливое число в O (n^(2/3)), алгоритм jonderry будет работать просто отлично. Обратите внимание, что используемые числа огромны, поэтому у любого алгоритма, пытающегося проверить, уродливое число или нет, нет шансов.
Найти все n самых маленьких уродливых чисел в порядке возрастания легко, используя очередь приоритетов за время O (n log n) и пространство O (n): сначала создайте очередь с приоритетами чисел с наименьшими числами, первоначально включая только номер 1. Затем повторите n раз: удалите наименьшее число x из приоритетной очереди. Если x не был удален ранее, то x - это следующее большее уродливое число, и мы добавляем 2x, 3x и 5x в очередь с приоритетами. (Если кто-то не знает термин очередь с приоритетами, это похоже на кучу в алгоритме heapsort). Вот начало алгоритма:
1 -> 2 3 5
1 2 -> 3 4 5 6 10
1 2 3 -> 4 5 6 6 9 10 15
1 2 3 4 -> 5 6 6 8 9 10 12 15 20
1 2 3 4 5 -> 6 6 8 9 10 10 12 15 15 20 25
1 2 3 4 5 6 -> 6 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 -> 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 8 -> 9 10 10 12 12 15 15 16 18 20 24 25 30 40
Доказательство времени выполнения: Извлекаем уродливое число из очереди n раз. Изначально у нас есть один элемент в очереди, и после извлечения некрасивого числа мы добавляем три элемента, увеличивая число на 2. Таким образом, после того, как найдено не очень уродливое число, мы имеем не более 2n + 1 элементов в очереди. Извлечение элемента может быть сделано в логарифмическом времени. Мы извлекаем больше чисел, чем только уродливые числа, но не более чем уродливые числа плюс 2n - 1 других чисел (тех, которые могли быть в сите после n-1 шагов). Таким образом, общее время составляет менее 3n удалений элементов в логарифмическом времени = O (n log n), а общее пространство составляет не более 2n + 1 элементов = O (n).
Используя 3 генератора параллельно и выбирая наименьший на каждой итерации, вот программа на языке C для вычисления всех уродливых чисел меньше 218 менее чем за 1 секунду:
#include <limits.h>
#include <stdio.h>
#if 0
typedef unsigned long long ugly_t;
#define UGLY_MAX (~(ugly_t)0)
#else
typedef __uint128_t ugly_t;
#define UGLY_MAX (~(ugly_t)0)
#endif
int print_ugly(int i, ugly_t u) {
char buf[64], *p = buf + sizeof(buf);
*--p = '\0';
do { *--p = '0' + u % 10; } while ((u /= 10) != 0);
return printf("%d: %s\n", i, p);
}
int main() {
int i = 0, n2 = 0, n3 = 0, n5 = 0;
ugly_t u, ug2 = 1, ug3 = 1, ug5 = 1;
#define UGLY_COUNT 110000
ugly_t ugly[UGLY_COUNT];
while (i < UGLY_COUNT) {
u = ug2;
if (u > ug3) u = ug3;
if (u > ug5) u = ug5;
if (u == UGLY_MAX)
break;
ugly[i++] = u;
print_ugly(i, u);
if (u == ug2) {
if (ugly[n2] <= UGLY_MAX / 2)
ug2 = 2 * ugly[n2++];
else
ug2 = UGLY_MAX;
}
if (u == ug3) {
if (ugly[n3] <= UGLY_MAX / 3)
ug3 = 3 * ugly[n3++];
else
ug3 = UGLY_MAX;
}
if (u == ug5) {
if (ugly[n5] <= UGLY_MAX / 5)
ug5 = 5 * ugly[n5++];
else
ug5 = UGLY_MAX;
}
}
return 0;
}
Вот последние 10 строк вывода:
100517: 338915443777200000000000000000000000000 100518: 339129266201729628114355465608000000000 100519: 339186548067800934969350553600000000000 100520: 339298130282929870605468750000000000000 100521: 339467078447341918945312500000000000000 100522: 339569540691046437734055936000000000000 100523: 339738624000000000000000000000000000000 100524: 339952965770562084651663360000000000000 100525: 340010386766614455386112000000000000000 100526: 340122240000000000000000000000000000000
Вот версия на Javascript, которую можно использовать с QuickJS:
import * as std from "std";
function main() {
var i = 0, n2 = 0, n3 = 0, n5 = 0;
var u, ug2 = 1n, ug3 = 1n, ug5 = 1n;
var ugly = [];
for (;;) {
u = ug2;
if (u > ug3) u = ug3;
if (u > ug5) u = ug5;
ugly[i++] = u;
std.printf("%d: %s\n", i, String(u));
if (u >= 0x100000000000000000000000000000000n)
break;
if (u == ug2)
ug2 = 2n * ugly[n2++];
if (u == ug3)
ug3 = 3n * ugly[n3++];
if (u == ug5)
ug5 = 5n * ugly[n5++];
}
return 0;
}
main();
Я предполагаю, что мы можем использовать Динамическое Программирование (DP) и вычислить n-ой Гадкий Число. Полное объяснение можно найти на http://www.geeksforgeeks.org/ugly-numbers/
#include <iostream>
#define MAX 1000
using namespace std;
// Find Minimum among three numbers
long int min(long int x, long int y, long int z) {
if(x<=y) {
if(x<=z) {
return x;
} else {
return z;
}
} else {
if(y<=z) {
return y;
} else {
return z;
}
}
}
// Actual Method that computes all Ugly Numbers till the required range
long int uglyNumber(int count) {
long int arr[MAX], val;
// index of last multiple of 2 --> i2
// index of last multiple of 3 --> i3
// index of last multiple of 5 --> i5
int i2, i3, i5, lastIndex;
arr[0] = 1;
i2 = i3 = i5 = 0;
lastIndex = 1;
while(lastIndex<=count-1) {
val = min(2*arr[i2], 3*arr[i3], 5*arr[i5]);
arr[lastIndex] = val;
lastIndex++;
if(val == 2*arr[i2]) {
i2++;
}
if(val == 3*arr[i3]) {
i3++;
}
if(val == 5*arr[i5]) {
i5++;
}
}
return arr[lastIndex-1];
}
// Starting point of program
int main() {
long int num;
int count;
cout<<"Which Ugly Number : ";
cin>>count;
num = uglyNumber(count);
cout<<endl<<num;
return 0;
}
Мы видим, что это довольно быстро, просто измените значение MAX, чтобы вычислить более высокое Ugly Number
Вот мой код, идея состоит в том, чтобы разделить число на 2 (пока оно не даст остаток 0), а затем 3 и 5 . Если наконец число становится единым, это уродливое число. Вы можете считать и даже печатать все уродливые числа до n.
int count = 0;
for (int i = 2; i <= n; i++) {
int temp = i;
while (temp % 2 == 0) temp=temp / 2;
while (temp % 3 == 0) temp=temp / 3;
while (temp % 5 == 0) temp=temp / 5;
if (temp == 1) {
cout << i << endl;
count++;
}
}
Эта проблема может быть решена в 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. Поэтому я ищу Четвёртое уродливое число (так как 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).
Вот еще один O(n) подход (решение Python), основанный на идее объединения трех отсортированных списков. реальная задача состоит в том, чтобы найти следующий, более страшный номер? например, мы знаем, что первые пять уродливых чисел - [1,2,3,4,5]. уродливые числа на самом деле из следующих трех списков:
- список 1: 1*2, 2*2, 3*2, 4*2, 5*2 ...;
- список 2: 1*3, 2*3, 3*3, 4*3, 5*3 ...;
- список 3: 1*5, 2*5, 3*5, 4*5, 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
if next==ugly3: p3+=1
if next==ugly5: p5+=1
uglynumber+=[next]
return uglynumber[-1]
- ШАГ I: вычисление текущих некрасивых чисел из трех списков
- ugly2, ugly3, ugly5=uglynumber[p2]*2,uglynumber[p3]*3,uglynumber[p5]*5
- ШАГ II, найдите следующий, более страшный номер:
- следующий =min(ugly2, ugly3, ugly5)
- ШАГ III: перемещение указателя вперед, если его уродливый номер является следующим большим числом
- если следующий ==ugly2: p2+=1
- если следующий ==ugly3: p3+=1
- если следующий ==ugly5: p5+=1
- обратите внимание: здесь не используется if, elif и др.
- ШАГ IV: добавление следующего, большего, некрасивого номера в объединенный список unglynumber
- uglynumber + = [следующий]