как определить основу числа?
Учитывая целое число и его reresentation в некоторой системе произвольного числа. Цель состоит в том, чтобы найти основу системы счисления. Например, число равняется 10, и представление равняется 000010, затем основа должна быть 10. Другой пример: представление номер 21 0010101 затем, основа равняется 2. Еще один пример: число равняется 6, и представление os 10100 затем базируются, sqrt (2). У кого-либо есть какая-либо идея, как решить такую проблему?
8 ответов
Алгоритм, подобный этому, должен найти основание, если это целое число, и по крайней мере сузить выбор для нецелого основания:
- Пусть
N- ваше целое число, аR- его представление в загаданном основании. - Найдите наибольшую цифру в
Rи назовите ееr.- Вы знаете, что ваше основание не меньше
r + 1.
- Вы знаете, что ваше основание не меньше
- Для
base == (r+1, r+2, ...), пустьIпредставляет собойR, интерпретированный в базуbase- Если
IравноN, тоbase- ваша тайная база. - Если
IменьшеN, попробуйте следующую базу. - Если
IбольшеN, то ваша база находится где-то междубазой - 1ибазой.
- Если
Это метод грубой силы, но он должен сработать. Вы также можете немного ускорить его, увеличивая 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]) должно быть равномерно кратно основанию (поскольку все ваши значения a[] - целые числа). Если вы вычислите (x - a[0]) % base и получите ненулевой результат, то base не может быть правильным основанием.
___
\
number = /__ ( digit[i] * base ^ i )
Вы знаете номер , вы знаете все цифру [i] , вам просто нужно узнать базу .
Вопрос о том, является ли решение этого уравнения простым или сложным, остается в качестве упражнения.
В нескольких других сообщениях предполагается, что решение может быть найдено путем нахождения корней многочлена, который представляет собой число. Они, конечно, обычно работают, хотя имеют тенденцию давать отрицательные и сложные основания, а также положительные целые числа.
Другой подход состоял бы в том, чтобы представить это как задачу целочисленного программирования и решить, используя ветвление и границу.
Но я подозреваю, что предложение предположить и проверить будет быстрее, чем любое из более умных предложений.
Я не уверен, что это эффективно решаемо. Я бы просто попытался выбрать случайную базу, посмотреть, если с учетом базы результат будет меньше, больше или равен числу. В случае, если он меньше, выберите большую базу, в случае, если он больше, выберите меньшую базу, в противном случае у вас есть правильная база.
Я не думаю, что можно дать ответ для каждого случая. И у меня действительно есть основания так думать! =)
Дано число 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.
Это невозможно сделать в общем случае, как показано Абелем и Руффини . Возможно, вам повезет с более короткими числами, но если используется более четырех цифр, формулы становятся все более уродливыми.
Однако существует довольно много хороших алгоритмов аппроксимации. См. здесь .
Это должно дать вам отправную точку:
Создайте уравнение из числа и представления, числа 42 и представления " 0010203 "превращается в:
1 * base ^ 4 + 2 * base ^ 2 + 3 = 42
Теперь вы решаете уравнение, чтобы получить значение base .
Думаю, вам нужно будет попробовать проверить разные базы. Чтобы быть эффективным, ваша начальная база может быть max (цифра) + 1, поскольку вы знаете, что она не будет меньше этой. Если это слишком мало, удвойте, пока вы не превысите, а затем используйте двоичный поиск, чтобы сузить его. Таким образом, ваш алгоритм должен работать за O (log n) для нормальных ситуаций.
Только для целых чисел это не так уж и сложно (мы можем перечислить).
Давайте посмотрим на 21 и его представление 10101 .
1 * base^4 <= 21 < (1+1) * base^4
Давайте сгенерируем числа для некоторых оснований:
base low high
2 16 32
3 81 162
В общем, у нас есть N , представленное как ∑ 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] ) ]
В случае целочисленного основания или если у вас есть список известных возможных оснований, I сомневаюсь, что у них будет много возможностей, поэтому мы можем просто попробовать их.
Обратите внимание, что может быть быстрее взять Ithroot из N / (a [I] + 1) и выполнить итерацию отсюда вместо вычисления второго (что должно быть достаточно близко) ... но мне нужен математический обзор этого интуитивного ощущения.
Если вы действительно понятия не имеете (пытаетесь найти плавающую базу) ... ну, я думаю, это немного сложнее, но вы всегда можете уточнить неравенство (включая еще один или два члена), следуя тому же имущество.