Collatz Conjecture интервью - PullRequest
Новая
       7

Collatz Conjecture интервью

9 голосов
/ 25 марта 2011

Это был вопрос интервью, который, похоже, связан с проектом Эйлера Задача 14

Гипотеза Коллатца гласит, что если вы выполните следующее 

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

В конечном итоге вы закончитес 1.

Например, 5 -> 16 -> 8 -> 4 -> 2 -> 1

Если предположить, что гипотеза верна, каждое число имеет длину цепи: количество шагов, необходимых для достижения 1. (Длина цепи1 - это 0).

Теперь задача состоит в том, что задаются натуральные числа n, m и натуральное число k, и дается алгоритм поиска всех чисел от 1 до n, так что длина цепочки этих чисел равна <= к.Существует также ограничение, заключающееся в том, что в цепочку любого из этих чисел должны входить только числа от 1 до m (т. Е. Вы не можете переходить через m). </p>

Простой способ состоит в том, чтобы перебрать его и объединить,с напоминанием.

Интервьюер сказал, что был алгоритм времени O (S), где S - это число чисел, которое нам нужно вывести.

Кто-нибудь знает, что это может быть?

1 Ответ

10 голосов
/ 25 марта 2011

Я думаю, что вы можете решить это в O (S), запустив процесс в обратном направлении.Если вы знаете, что такое k, то вы можете построить все числа, которые останавливаются не более чем на k шагов, используя следующую логику:

  • 1 имеет цепочку длины 0.
  • Если число z имеет цепочку длины n, то 2z имеет цепочку длины n + 1.
  • Если число z имеет цепочку длины n, z - 1 кратно трем (другиечем 0 или 3), и (z - 1) / 3 является нечетным, то (z - 1) / 3 имеет цепочку длиной n + 1.

С этого момента вы можете начать строитьдо числа в последовательности, начинающейся с 1: 

                  1
                  |
                  2
                  |
                  4
                  |
                  8
                  |
                  16
                  | \
                  32 \
                  |   5
                  64  |
                 /|   10
                / 128 | \
               21     20 3

Мы могли бы сделать этот алгоритм, используя рабочую очередь, хранящую числа, которые нам нужно посетить, и длины их цепочек.Мы заполняем очередь парой (1, 0), затем непрерывно вытесняем элемент (z, n) из очереди и ставим в очередь (2z, n + 1) и (возможно) ((z - 1) / 3, n +1) в очередь.По сути, это поиск в ширину в графе Коллатца, начиная с единицы.Когда мы находим первый элемент на глубине k, мы прекращаем поиск.

Предполагая, что гипотеза Коллатца верна, мы никогда не получим дубликатов таким образом.Более того, мы нашли все числа, достижимые не более чем за k шагов (вы можете быстро проверить это с помощью быстрого индуктивного доказательства).И, наконец, это занимает O (S) время.Чтобы увидеть это, обратите внимание, что работа, выполненная для сгенерированного числа, является константой (выведите очередь из очереди и вставьте до двух новых чисел в очередь).

Надеюсь, это поможет!

...