Как определить базу номера?

Ответ 1

Подобный алгоритм должен найти базу, если она является целым числом, и должна, по крайней мере, сузить выбор для нецелого основания:

• Пусть 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 более чем на 1, если 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 не может быть правильной базой.

Ответ 2

         ___
         \
number = /__ ( digit[i] * base ^ i )

Знаете number, вы знаете все digit[i], вам просто нужно узнать base.

Решено ли это уравнение простым или сложным, остается как упражнение.

Ответ 3

Я не думаю, что ответ может быть дан для каждого случая. И у меня на самом деле есть причина думать так! =)

Учитывая число x с представлением a_6 a_5 a_4 a_3 a_2 a_1 в базе b, поиск базового средства решения

a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x.

Это невозможно сделать вообще, как показано Abel and Ruffini. Вам может быть повезло с более короткими номерами, но если задействовано более четырех цифр, формулы становятся все более уродливыми.

Однако существует довольно много хороших алгоритмов аппроксимации. См. здесь.

Ответ 4

Только для целых чисел это не так сложно (мы можем перечислить).

Посмотрим на 21 и его представление 10101.

1 * base^4 <= 21 < (1+1) * base^4

Пусть порождают числа для некоторых баз:

base   low   high
2      16    32
3      81    162

В более общем смысле мы имеем N, представленный как Σ a _i * base ⁱ. Учитывая I максимальную мощность, для которой a _I не является нулевым, мы имеем:

a[I] * base^I <= N < (a[I] + 1) * base^I  # does not matter if not representable

# Isolate base term
N / (a[I] + 1) < base^I <= N / a[I]

# Ith root
Ithroot( N / (a[I] + 1) ) < base <= Ithroot( N / a[I] )

# Or as a range
base in ] Ithroot(N / (a[I] + 1)), Ithroot( N / a[I] ) ]

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

Обратите внимание, что может быть быстрее фактически взять Ithroot из N / (a[I] + 1) и итерации отсюда вместо вычисления второго (что должно быть достаточно близко)... но мне нужен математический обзор на этом кишке чувство.

Если вы действительно не знаете (пытаетесь найти плавучую базу)... ну, это немного сложнее, я думаю, но вы всегда можете усовершенствовать неравенство (в том числе одно или два слова), следуя тем же свойство.

Ответ 5

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

Ответ 6

Это должно дать вам отправную точку:

Создайте уравнение из числа и представления, номер 42 и объявление "0010203" станет:

1 * base ^ 4 + 2 * base ^ 2 + 3 = 42

Теперь вы решаете уравнение, чтобы получить значение base.

Ответ 7

Я думаю, вам нужно попробовать и проверить разные базы. Чтобы быть эффективной, ваша стартовая база может быть максимальной (цифрой) + 1, как вы знаете, это будет не меньше. Если этот слишком маленький двойной, пока вы не превысите, а затем используйте бинарный поиск, чтобы сузить его. Таким образом, ваш алгоритм должен работать в O (log n) для нормальных ситуаций.

Ответ 8

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

Другим подходом было бы бросить это как задачу целочисленного программирования и решить с помощью ветки и границы.

Но я подозреваю, что предложение об угадывании и тестировании будет быстрее любого из более разумных предложений.