Верхняя граница 4-значных последовательностей в пи

Если это не правильный сайт SE для этого вопроса, пожалуйста, дайте мне знать.

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

Задается значение от pi до n цифр в виде строки.

Как я могу найти все повторяющиеся последовательности из 4 цифр в этой строке?

Эта часть кажется довольно прямолинейной. Добавьте 4 последовательности символов в хэш-таблицу, увеличивая по одному символу за раз. Перед вставкой в ​​хеш-таблицу проверьте, существует ли текущая последовательность из 4 символов. Если да, то вы нашли дубликат. Сохраните это где-нибудь и повторите процесс. Мне сказали, что это более-менее правильно.

У меня проблема по второму вопросу:

Какова верхняя граница?

n = 10,000,000 был примером.

Мой фон алгоритма, по общему признанию, очень ржавый. Сначала я подумал, что верхняя граница должна быть как-то связана с n, но мне сказали, что это не так.

Как мне это рассчитать?

ИЗМЕНИТЬ:

Я также был бы открыт для решения, которое игнорирует ограничение, заключающееся в том, что верхняя граница не связана с n. Любой приемлем.


algorithm pi upperbound
person Josh    schedule 02.01.2015    source источник
comment
«Какова верхняя граница?» Верхняя граница чего?   -  person Pascal Cuoq    schedule 03.01.2015
comment
@PascalCuoq Примерно сколько итераций потребуется, чтобы найти все дубликаты.   -  person Josh    schedule 03.01.2015
comment
и для хеш-таблицы, и для user3386109 решения, очевидно, O(n) (амортизируются в случае хеш-таблицы, строго для предварительно выделенного массива), и не может быть более простого решения, потому что каждую цифру в массиве нужно искать в.   -  person kkm    schedule 03.01.2015

Ответы (2)


arrow_upward
2
arrow_downward

Существует только 10 000 возможных последовательностей из четырех цифр (от 0000 до 9999), поэтому в какой-то момент вы обнаружите, что каждая последовательность дублируется, и нет необходимости обрабатывать дальнейшие цифры.

Если вы предполагаете, что pi является совершенно однородным генератором случайных чисел, то каждая новая цифра, которая обрабатывается, приводит к новой последовательности, и примерно через 20 000 цифр вы найдете дубликаты для всех 10 000 последовательностей. Учитывая, что pi не идеально, вам может понадобиться значительно больше цифр, прежде чем вы продублируете все последовательности, но 100 000 будет разумным предположением для верхней границы.

Кроме того, поскольку существует всего 10 000 возможностей, вам не нужна хэш-таблица. Вы можете просто использовать массив из 10000 счетчиков (int count[10000]) и увеличивать счетчик для каждой найденной последовательности.

person user3386109    schedule 02.01.2015

arrow_upward
0
arrow_downward

Верхняя граница вашего решения — это размер хеш-таблицы, которую вы можете поместить в память.

Альтернативный метод заключается в создании всех последовательностей и их сортировке. Тогда дубликаты будут соседними и их будет легко обнаружить. Как правило, вы можете вписать больше в линейную структуру данных, чем в хеш-таблицу, и если вы все еще исчерпали память, вы можете сортировать на / с диска.

Изменить: если только «верхняя граница» не означает O (n) алгоритма, что должно быть легко понять.

person Mark Ransom    schedule 02.01.2015
comment
К вашему редактированию, да, я совершенно уверен, что это был желаемый ответ. Как я уже сказал, я очень ржавый. Как бы просто это ни было, как мне рассчитать O (n)? - person Josh; 03.01.2015
comment
@iThink, снова глядя на ваш вопрос, O (n) очевидно связано с n, но вы заявляете, что это не так. Это меня очень смущает. - person Mark Ransom; 03.01.2015
comment
Я согласен. Вот что меня действительно смутило. При этом я открыт для любой интерпретации этого вопроса. - person Josh; 03.01.2015