как определить базу числа? - PullRequest
12 голосов
/ 08 апреля 2010

Дано целое число и его представление в произвольной системе счисления. Цель состоит в том, чтобы найти базу системы счисления. Например, число равно 10, а представление равно 000010, тогда основание должно быть 10. Другой пример: представление числа 21 - 0010101, затем основание - 2. Еще один пример: число - 6, а представление - 10100, тогда основание - sqrt (2). , У кого-нибудь есть идеи, как решить такую ​​проблему?

Ответы [ 8 ]

11 голосов
/ 08 апреля 2010
         ___
         \
number = /__ ( digit[i] * base ^ i )

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

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

8 голосов
/ 08 апреля 2010

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

Учитывая число х, с представлением 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.

Это не может быть сделано вообще, как показано Абелем и Руффини . Возможно, вам повезет больше с более короткими числами, но если в нем участвуют более четырех цифр, формулы становятся все более уродливыми

Хотя есть много хороших алгоритмов приближения. Смотри здесь .

5 голосов
/ 08 апреля 2010

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

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

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

Давайте сгенерируем числа для некоторых баз:

base   low   high
2      16    32
3      81    162

В более общем смысле, N представляется как 101 a i * base i . Учитывая I максимальную мощность, для которой 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) и выполнить итерацию отсюда вместо вычисления второго (которое должно быть достаточно близко) ... но мне понадобится математический обзор этой интуиции чувство.

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

3 голосов
/ 08 апреля 2010

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

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

1 голос
/ 08 апреля 2010

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

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

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

1 голос
/ 08 апреля 2010

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

1 голос
/ 08 апреля 2010

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

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

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

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

1 голос
/ 08 апреля 2010

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...