Алгоритм, подобный этому, должен находить базу, если она является целым числом, и, по крайней мере, должен сузить выбор для нецелочисленной базы:
- Пусть
N
будет вашим целым числом, а R
будет его представлением в базе мистерий.
- Найдите самую большую цифру в
R
и назовите ее r
.
- Вы знаете, что ваша база по крайней мере
r + 1
.
- Для
base == (r+1, r+2, ...)
, пусть I
представляет R
, интерпретируемый в базе base
- Если
I
равно N
, тогда base
является вашей загадочной базой.
- Если
I
меньше N
, попробуйте следующую базу.
- Если
I
больше N
, то ваша база находится где-то между base - 1
и base
.
Это метод грубой силы, но он должен работать. Вы также можете ускорить его, увеличив base
более чем на единицу, если I
значительно меньше N
.
Что-то еще, что может помочь ускорить процесс, особенно в случае нецелочисленной базы: Помните, что, как упоминали несколько человек, число в произвольной базе может быть расширено как многочлен, как
x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0]
При оценке потенциальных баз вам не нужно конвертировать все число. Начните с преобразования только наибольшего термина, a[n]*base^n
. Если это больше, чем x
, то вы уже знаете, что ваша база слишком велика. В противном случае добавляйте по одному термину за раз (переходя от наиболее значимого к наименее значимому). Таким образом, вы не тратите время на вычисления терминов, когда узнаете, что ваша база неверна.
Кроме того, есть еще один быстрый способ устранить потенциальную базу. Обратите внимание, что вы можете переупорядочить приведенное выше полиномиальное выражение и получить
(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base
или
(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base
Вам известны значения x
и a[0]
(цифра "единицы", вы можете интерпретировать ее независимо от базы). Что это дает вам дополнительное условие, что (x - a[0])
должно быть равномерно делиться на base
(так как все ваши значения a[]
являются целыми числами). Если вы вычислили (x - a[0]) % base
и получили ненулевой результат, то base
не может быть правильной базой.