Мой друг берет интервью на работу. Один из вопросов на собеседовании заставил меня задуматься, просто хотелось получить обратную связь.
Есть 2 неотрицательных целых числа: i и j. Учитывая следующее уравнение, найдите (оптимальное) решение для итерации по i и j таким образом, чтобы выходные данные были отсортированы.
2^i * 5^j
Итак, первые несколько раундов будут выглядеть так:
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
Как ни старайся, я не вижу картины. Твои мысли?
algorithm
optimization
hamming-numbers
smooth-numbers
Крис Эберле
источник
источник
2^2 < 5
но2^3 > 5
так в этот момент вы увеличиваете J. Я думаю, что вы можете произвести вывод в O (n), а не O (nlgn). @ tom-zynch два вложенных цикла - это O (n ^ 2). Этот вопрос очень актуаленОтветы:
Дейкстра получает красноречивое решение в «Дисциплине программирования». Он приписывает проблему Хэммингу. Вот моя реализация решения Дейкстры.
источник
вот более изощренный способ сделать это (более изощренный, чем мой предыдущий ответ, то есть):
Представьте, что числа помещены в матрицу:
что вам нужно сделать, это «пройтись» по этой матрице, начиная с
(0,0)
. Вы также должны отслеживать, каковы ваши возможные следующие шаги. Когда вы начинаете(0,0)
вас есть только два варианта: либо(0,1)
или(1,0)
: так как значение(0,1)
меньше, вы выбираете , что. затем сделайте то же самое для вашего следующего выбора(0,2)
или(1,0)
. До сих пор, у вас есть следующий список:1, 2, 4
. Ваш следующий шаг -(1,0)
значение там меньше, чем(0,3)
. Тем не менее, теперь у вас есть три варианта для вашего следующего хода: либо(0,3)
, либо(1,1)
, либо(2,0)
.Вам не нужна матрица, чтобы получить список, но вам нужно отслеживать все ваши выборы (т.е. когда вы достигнете 125+, у вас будет 4 варианта).
источник
j
проверка для каждого 1 выходаj ~ n^0.5
для n-го значения в последовательности, посколькуn
значения заполняют область наi x j
плоскости. Так что этот алгоритм -O(n^1.5)
время, сO(n^0.5)
пространством. Но существует линейный алгоритм времени с той же пространственной сложностьюn^0.5
, и алгоритм мини-кучи из ответа ниже -O(n*log(n))
время с тем жеn^0.5
пространством.Используйте Мин-кучу.
Ставь 1.
экстракт-Мин. Скажем, вы получили х.
Нажмите 2x и 5x в кучу.
Повторение.
Вместо сохранения x = 2 ^ i * 5 ^ j вы можете сохранить (i, j) и использовать пользовательскую функцию сравнения.
источник
Решение на основе FIFO требует меньшего объема памяти. Код Python
вывод:
источник
Это очень легко сделать
O(n)
на функциональных языках. Списокl
из2^i*5^j
номеров может быть просто определен как1
и то2*l
и5*l
объединен. Вот как это выглядит в Haskell:merge
Функция дает новое значение в постоянная время. Так и делает,map
а значит, и делаетl
.источник
union
, поскольку она удаляет дубликаты.merge
как частьmergesort
, должен сохранить дубликаты, поступающие из обеих его входных последовательностей. СмотритеData.List.Ordered
пакет для связанных вещей.Data.List.Ordered.union
. Это делает его одной строкой:xs = 1 : union (map (2*) xs) (map (5*) xs)
[1, 2, 4, 5,...]
поэтому он включает5*4
.Data.List.Ordered.union
функция. Не путать сData.List.union
.Вы должны отслеживать их отдельные показатели, и каковы их суммы
Итак, начните с того, что
f(0,0) --> 1
вам нужно увеличить одно из них:поэтому мы знаем, что следующим является 2 - мы также знаем, что можем увеличивать показатель i до тех пор, пока сумма не превысит 5.
Вы продолжаете идти вперед и назад, пока не достигнете нужного количества раундов.
источник
f(*,2)
только потому, что нашли этоf(a1,b+1)>f(a2,b)
. Инкрементальный подход в конечном итоге будет генерировать неограниченное количество пар, соседствующих с областью, которую вы уже вывели.Используя динамическое программирование, вы можете сделать это в O (n). Основная истина заключается в том, что никакие значения i и j не могут дать нам 0, и чтобы получить 1, оба значения должны быть 0;
Всякий раз, когда вы вызываете эту функцию, проверьте, установлены ли i и j, если они не равны NULL, затем заполните
TwoCount
иFiveCount
C ++ ответ. Извините за плохой стиль кодирования, но я тороплюсь :(
Очевидно, что вы можете использовать структуры данных, отличные от массива, для динамического увеличения хранилища и т. Д. Это всего лишь эскиз, чтобы доказать, что он работает.
источник
O(exp(sqrt(n)))
получитьn
числа последовательности. Линейный алгоритм существует, например, как указано ThomasAhle.O(n)
подразумеваетсяn
последнее значение, а не количество напечатанных элементов, что не правильно. Я не знаю, как работают функциональные языки или как работает слияние в постоянное время, но его ответ получил мое одобрениеПочему бы не попробовать посмотреть на это с другой стороны. Используйте счетчик, чтобы проверить возможные ответы по оригинальной формуле. Извините за псевдокод.
источник
O(4^sqrt(n))
потому, чтоnth
номер последовательности примерно такого же размера.Это соответствующая запись в OEIS.
Кажется возможным получить упорядоченную последовательность, генерируя первые несколько членов, скажем,
а затем, начиная со второго слагаемого, умножая на 4 и 5, чтобы получить следующие два
и так далее...
Интуитивно, это кажется правильным, но, конечно, доказательства отсутствуют.
источник
Вы знаете, что log_2 (5) = 2,32. Из этого отметим, что 2 ^ 2 <5 и 2 ^ 3> 5.
Теперь посмотрите матрицу возможных ответов:
Теперь, для этого примера, выберите номера по порядку. Там порядок будет:
Обратите внимание, что каждая строка начинается на 2 столбца позади строки, начинающей ее. Например, i = 0 j = 1 наступает сразу после i = 2 j = 0.
Следовательно, алгоритм, который мы можем вывести из этого шаблона, (предположим, j> i):
ПРИМЕЧАНИЕ: код здесь ограничивает значения показателей степени i и j, чтобы быть меньше 10. Вы можете легко расширить этот алгоритм, чтобы вписаться в любые другие произвольные границы.
ПРИМЕЧАНИЕ. Время выполнения этого алгоритма составляет O (n) для первых n ответов.
ПРИМЕЧАНИЕ. Пространственная сложность этого алгоритма равна O (1).
источник
Моя реализация основана на следующих идеях:
Пример:
Код на Java:
источник
рассчитать результаты и поместить их в отсортированный список вместе со значениями
i
иj
источник
2^n*5^n
но не2^(n+1)*5^(n-1)
меньше.i
«s иj
» s, не так ли? В противном случае вы никогда не доберетесь до состояния сортировки и, следовательно, никогда не вернете ни одного значения. Но для любого ограничения, котороеn
вы выберете, ваш список будет ошибочным.i
иj
.2^i*5^j
значения, а затем сортируете их. Если у вас нет ограниченного числа «результатов», как вы попадете на этап сортировки?Алгоритм, реализованный пользователем 515430 Эдсгером Дейкстрой (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF), вероятно, работает настолько быстро, насколько вы можете этого добиться. Я звоню на каждый номер, который является формой
2^i * 5^j
«специального номера». Теперь ответ vlads будет,O(i*j)
но с двойным алгоритмом, один для генерации специальных чиселO(i*j)
и один для их сортировки (согласно связанной статье такжеO(i*j)
.Но давайте проверим алгоритм Дейкстры (см. Ниже). В этом случае
n
количество специальных чисел, которые мы генерируем, равноi*j
. Мы делаем цикл один раз,1 -> n
и в каждом цикле мы выполняем постоянное действие. Так что этот алгоритм тожеO(i*j)
. И с довольно яркой быстрой константой тоже.Моя реализация в C ++ с GMP (оболочка C ++) и зависимость от
boost::lexical_cast
, хотя ее легко удалить (я ленив, а кто не использует Boost?). Составлено сg++ -O3 test.cpp -lgmpxx -o test
. На Q6600 Ubuntu 10.10time ./test 1000000
выдает1145ms
.источник
Если вы нарисуете матрицу с i в качестве строки и j в качестве столбца, вы сможете увидеть шаблон. Начните с i = 0, а затем просто пройдитесь по матрице, пройдя вверх на 2 строки и правый 1 столбец, пока не достигнете вершины матрицы (j> = 0). Тогда иди я + 1 и т.д ...
Так что для i = 7 вы путешествуете так:
И для я = 8:
Здесь это происходит в Java до i = 9. Он печатает положение матрицы (i, j) и значение.
источник
Моя интуиция :
Если я беру начальное значение как 1, где i = 0, j = 0, то я могу создать следующие числа как (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) * (5 ^ 1), ... т.е. 2,4,5 ..
Допустим, в любой момент мой номер х. тогда я могу создать следующие числа следующими способами:
Пояснение :
Тестовый забег
Давайте начнем с х = 1.
Следующие три числа: 1 * 2, 1 * 4, 1 * 5 [2,4,5]; ARR [1,2,4,5]
Теперь х = 2
Следующие три числа: [4,8,10] {Так как 4 уже произошло, мы его проигнорируем} [8,10]; ARR [1,2,4,5,8,10]
Теперь х = 4
Следующие три числа [8,16,20] {8 уже произошло, игнорируйте его} [16,20] Arr [1,2,4,5,8,10,16,20]
х = 5
Следующие три числа [10,20,25] {10,20} уже так [25] добавляется Arr [1,2,4,5,8,10,16,20,25]
Условие прекращения
Анализ
источник
Просто было интересно, чего ожидать на следующей неделе и нашли этот вопрос.
Я думаю, идея в том, что 2 ^ i увеличивается не такими большими шагами, как 5 ^ j. Так что увеличивайте i, пока следующий j-шаг не будет больше.
Пример на C ++ (Qt не обязателен):
Выход:
источник
Вот мое решение
Результат:
источник
Я знаю, что, скорее всего, ошибаюсь, но здесь есть очень простая эвристика, поскольку она не включает много чисел, таких как 2,3,5. Мы знаем, что для любого i, j 2 ^ i * 5 ^ j следующая последовательность будет 2 ^ (i-2) * 5 ^ (j + 1). Будучи Google q, у него должно быть простое решение.
Это производит вывод как:
источник
Если вы идете по тому, что действительно происходит, когда мы увеличиваем I или J в выражении
2^i * 5^j
, вы либо умножаете на еще 2 или еще 5. Если мы переформулируем задачу как - учитывая конкретное значение i и j, как вы найдете следующее Чем больше значение, тем становится очевидным решение.Вот правила, которые мы можем интуитивно перечислить:
i > 1
в выражении есть пара 2s ( ), мы должны заменить их на 5, чтобы получить следующее наибольшее число. Таким образом,i -= 2
иj += 1
.j > 0
), нам нужно заменить его на три 2. Такj -= 1
иi += 3
.i += 1
,Вот программа на Ruby:
источник
Если нам разрешено использовать java Collection, мы можем получить эти числа в O (n ^ 2)
Здесь powerLimit должен быть инициализирован очень осторожно! В зависимости от того, сколько номеров вы хотите.
источник
Вот моя попытка со Scala:
Вывод:
источник