Математика позади преобразования из любой базы в любую базу без прохождения базы 10?

36

Я искал математику за преобразование из любой базы в любую базу. Это больше о подтверждении моих результатов, чем о чем-либо. Я нашел то, что кажется моим ответом на mathforum.org, но я все еще не уверен, правильно ли я это понял. У меня есть преобразование из большей базы в меньшую базу, хорошо, потому что это просто взять первую цифру умножить на базу, вы хотите добавить следующую цифру повтора. Моя проблема возникает при преобразовании из меньшей базы в большую базу. При этом они говорят о том, как вам нужно преобразовать большую базу, которую вы хотите, в меньшую базу, которая у вас есть. Примером может быть переход от базы 4 к базе 6, вам нужно преобразовать число 6 в базу 4, получая 12. Затем вы просто делаете то же самое, что и при преобразовании из большого в маленькое. Трудность, с которой я сталкиваюсь, заключается в том, что вам нужно знать, какое число находится в другой базе. Так что мне нужно было бы знать, что 6 находится в базе 4. Это создает большую проблему в моей голове, потому что тогда мне понадобится стол. Кто-нибудь знает способ сделать это лучше.

Я думал, что базовое преобразование поможет, но я не могу найти такую ​​работу. И с сайта, который я нашел, кажется, что он позволяет вам конвертировать из базы в базу, не проходя через базу 10, но сначала вам нужно знать, как конвертировать первое число из базы в базу. Это делает это бессмысленно.

Комментаторы говорят, что я должен быть в состоянии преобразовать письмо в число. Если так, то я это уже знаю. Это не моя проблема, однако. Моя проблема в том, чтобы преобразовать большую базу в маленькую, мне нужно сначала преобразовать имеющееся у меня базовое число в желаемое. При этом я побеждаю цель, потому что, если у меня есть возможность конвертировать эти базы в другие базы, я уже решил свою проблему.

Изменить: я выяснил, как преобразовать из баз меньше или равно 10 в другие базы меньше или равно 10. Я также могу перейти от базы больше 10 на любую базу, которая меньше или равна 10. Проблема начинается при преобразовании из базы больше 10 в другую базу больше 10. Или из базы меньше 10 в базу больше 10. Мне не нужен код, мне просто нужна базовая математика, которая может быть применяется к коду.

Грифон
источник
1
Это вопрос по теме для этого форума?
Андрей Бауэр
2
Процедура тривиальна, если вы можете делать сложение и умножение в целевой базе. Если ты не можешь, я не думаю, что это возможно.
Каролис Юоделе
9
Сначала Гриффину нужно сказать то, что нужно услышать многим студентам: числа существуют без представления в базе . Тогда ответ ясен: нам нужны алгоритмы, один для преобразования представления числа в данной базе в число (то есть что-то, что принимает stringи возвращает int), и алгоритм, который принимает число и возвращает его представление в данной базе.
Андрей Бауэр
1
@AndrejBauer Вопрос о CS: даже если он не сформулирован таким образом, это вопрос об алгоритме преобразования между представлениями чисел. [Несвязанное примечание: я удалил кучу запутанных комментариев. Гриффин: пожалуйста, отредактируйте свой вопрос, чтобы обновить его. Другие: пожалуйста, возьмите это, чтобы поболтать .]
Жиль "ТАК - перестань быть злым"
1
@ Гриффин, прошло много времени с твоего первоначального вопроса. Я надеюсь, что вы нашли свой ответ. Если это так, может быть, это будет отличная идея, чтобы обновить и принять ответ или опубликовать свой. Тем временем я нашел несколько очень хороших идей (о реализации в C ++) в Google Code Jam Archives. Некоторые решения этой проблемы очень креативны code.google.com/codejam/contest/32003/dashboard
IsaacCisneros

Ответы:

45

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

Следовательно, правильный вопрос, который нужно задать, - это не «как преобразовать из одной базы в другую», а «как узнать, какое число представлено данной строкой цифр» и «как найти цифровое представление данный номер ".

Итак, давайте создадим две функции в Python: одну для преобразования числового представления в число, а другую для обратного. Примечание: когда мы запускаем функцию, Python, конечно, выводит на экран число, которое он получил в базе 10. Но это не означает, что компьютер хранит цифры в базе 10 (это не так). Это не имеет значения , как компьютер представляет собой число.

def toDigits(n, b):
    """Convert a positive number n to its digit representation in base b."""
    digits = []
    while n > 0:
        digits.insert(0, n % b)
        n  = n // b
    return digits

def fromDigits(digits, b):
    """Compute the number given by digits in base b."""
    n = 0
    for d in digits:
        n = b * n + d
    return n

Давайте проверим это:

>>> toDigits(42, 2)
[1, 0, 1, 0, 1, 0]
>>> toDigits(42, 3)
[1, 1, 2, 0]
>>> fromDigits([1,1,2,0],3)
42

Вооружившись функциями преобразования, ваша проблема решается легко:

def convertBase(digits, b, c):
    """Convert the digits representation of a number from base b to base c."""
    return toDigits(fromDigits(digits, b), c)

Тест:

>>> convertBase([1,1,2,0], 3, 2) 
[1, 0, 1, 0, 1, 0]

Примечание: мы не прошли через представление базы 10! Мы преобразовали представление базы в число, а затем число в базу c . Номер был не в каком представлении. (На самом деле, компьютер должен был каким-то образом представлять его, и он представлял его с помощью электрических сигналов и прикольных вещей, которые происходят в микросхемах, но, конечно, это были не нули, а 1).бс

Андрей Бауэр
источник
4
Это не убеждает меня на 100%. Фактически, вы преобразовали число в некоторое представление (хотя вы можете утверждать, что не знаете, что это такое), потому что компьютеры не являются платоническими математиками, и ваш алгоритм не может преобразовать произвольную последовательность цифр в базе в базу b 2 ; он может конвертировать только последовательности, представленные конкретной машиной. Python очаровательно гибок; С не был бы таким прощающим. Это совершенно справедливо, чтобы спросить, как преобразовать произвольные строки из б 1б1б2б1 в ; однако это возможно только в линейном времени, за исключением определенных базовых комбинаций (например, 2 <-> 16)б2
rici
1
Правильно задать вопрос, но чтобы найти правильный ответ, лучше всего знать о том, что числа являются абстрактными сущностями.
Андрей Бауэр
2
это делает передать номер через основание 10 представления, как fromDigitsвозвращается число в базе 10
apnorton
8
@anorton: нет, определенно нет . Python выводит число на экран в базовом 10-значном представлении, но само число не сохраняется таким образом. Я пытаюсь объяснить, что неважно, как числа реализованы внутри Python. Не важно. Единственное, что имеет значение, это то, что они ведут себя как числа.
Андрей Бауэр
3
Наконец, общее решение для любой базы и не ограничивается конкретными случаями использования, базами менее 36 или случаями, когда вы можете придумать достаточно уникальных символов.
J.Money
21

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

Определение является числом в базе bИксб означает, что является строкой цифр < b .Икс<б

Примеры Строка цифр 10010011011 - это число в базе 2, строка 68416841531 - это число в базе 10, BADCAFE - это число в базе 16.

Теперь предположим, что я вырос на планете QUUX, где всех учат работать в всю свою жизнь, и я встречаю вас, который привык основывать b . Так ты показываешь мне номер, и что мне делать? Мне нужен способ интерпретировать это:Qб

Определение Я могу интерпретировать число в базе (Примечание: ббб - это число в базе ) по следующей формулеQ

[[ε]]знак равно0[[s¯d]]знак равно[[s¯]]×б+d

где обозначает пустую строку, а ˉ с d обозначает строку , оканчивающиеся на цифруεs¯d . Посмотритемое доказательство того, что дополнение добавляетвведение в эту запись.d

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

Ключ Ключ к этому - то, что у и + есть функции, которые работают с основанием числа q . Это простые алгоритмы, определенные рекурсивно на основе чисел q (строки цифр).×+QQ


Это может показаться немного абстрактным, поскольку я использовал переменные, а не фактические числа. Итак, давайте предположим, что вы - существо из базы 13 (используя символы ), а я привык к базе 7 (что гораздо более разумно), используя символы α β γ δ ρ0123456789ИксYZ .αβγδρζξ

Итак, я увидел ваш алфавит и составил таблицу следующим образом:

0α1β2γ3δ4ρ5ζ6ξ7βα8ββ9βγИксβδYβρZβζ

Итак, я знаю, что вы работаете в базе , и я знаю, какому числу 7 соответствует любая цифра, которую вы пишете.βξ

Теперь, если мы обсуждали физику, а вы говорили мне о фундаментальных константах (скажем) 60Z8 поэтому мне нужно интерпретировать это:

[[60Z8]]знак равноξ(βξ)3+α(βξ)2+βζ(βξ)+ββ

Итак, я начинаю с умножения но для меня этошкола, я вспоминаю:βζ×βξ

Таблица умножения Quux

×βγδρζξββγδρζξγγρξβββδβζδδξβγβζγβγρρρβββζγγγξδδζζβδγβγξδρργξξβζγρδδργζββαβαγαδαραζαξα

βζ×βξ

βζ×βξξγρβζδβγγ

так что у меня так далеко

[[60Z8]]знак равноξ(βξ)3+α(βξ)2+βζ(βξ)+ββзнак равноξ(βξ)3+α(βξ)2+δβγ+ββ

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

δβγββδγδ

так

[[60Z8]]знак равноξ(βξ)3+α(βξ)2+βζ(βξ)+ββзнак равноξ(βξ)3+α(βξ)2+δβγ+ββзнак равноξ(βξ)3+α(βξ)2+δγδ

[[60Z8]]знак равноζδξγρ,

QбQ

Дискретная ящерица
источник
1
Ну, это было много волнистых линий. Как мне заставить компьютер это делать?
Гриффин
1
@ Гриффин, я думаю, ты задаешь этот (странный) вопрос преждевременно. Вы выбираете язык программирования и вводите алгоритм сложения и умножения на числа q (представленные в виде списков цифр), затем определяете функцию для интерпретации цифр base b в числа q и для интерпретации чисел b в числа q. Я объяснил все это.
Дело в том, что я знаю концепцию, которую ты пытаешься изобразить. Моя проблема в том, что мой компьютер не может использовать твои волнистые линии.
Гриффин
Я знаю, что вы объяснили, но применить это на практике гораздо сложнее. Вы видите, определить эти цифры не так просто.
Гриффин
1
Кроме того, почему вы бросили буквенное число в наиболее значимой позиции? Поскольку 6 = & xi ;, не будет 7 = & alpha; & alpha ;?
Джованни Ботта
9

Это просто рефакторинг (Python 3) кода Андрея . В кодовых номерах Андрея они представлены в виде списка цифр (скаляров), а в следующих кодовых номерах представлены в виде списка символов, взятых из пользовательской строки :

def v2r(n, base): # value to representation
    """Convert a positive number to its digit representation in a custom base."""
    b = len(base)
    digits = ''
    while n > 0:
        digits = base[n % b] + digits
        n  = n // b
    return digits

def r2v(digits, base): # representation to value
    """Compute the number represented by string 'digits' in a custom base."""
    b = len(base)
    n = 0
    for d in digits:
        n = b * n + base[:b].index(d)
    return n

def b2b(digits, base1, base2):
    """Convert the digits representation of a number from base1 to base2."""
    return v2r(r2v(digits, base1), base2)

Чтобы выполнить преобразование из значения в представление в пользовательской базе:

>>> v2r(64,'01')
'1000000'
>>> v2r(64,'XY')
'YXXXXXX'
>>> v2r(12340,'ZABCDEFGHI') # decimal base with custom symbols
'ABCDZ'

Чтобы выполнить преобразование из представления (в пользовательской базе) в значение:

>>> r2v('100','01')
4
>>> r2v('100','0123456789') # standard decimal base
100
>>> r2v('100','01_whatevr') # decimal base with custom symbols
100
>>> r2v('100','0123456789ABCDEF') # standard hexadecimal base
256
>>> r2v('100','01_whatevr-jklmn') # hexadecimal base with custom symbols
256

Для преобразования базы из одной базы в другую:

>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'
MMJ
источник
1
Добро пожаловать на сайт и спасибо за ваш вклад. Однако создание хорошо оптимизированного исходного кода - это не то, чем занимается этот сайт. Код Андрея проясняет концепции, а это то, что нужно для его ответа, но улучшение кода помимо этого - вопрос программирования, а не компьютерных наук .
Дэвид Ричерби
1
@DavidRicherby Я частично согласен, но этот вклад был слишком длинным для комментария, и его лучшее место где-то рядом с ответом Андрея, поэтому я разместил его здесь. В любом случае, если вы считаете, что лучше, я мог бы преобразовать его в комментарий со ссылкой на код, но разве это не был бы избыток пуризма?
Мм
1

Фундаментальной операцией базового преобразования является toDigits()операция ответа @AndrejBauer. Однако, чтобы сделать это, нет необходимости создавать число во внутреннем представлении чисел, которое в основном представляет собой преобразование из представления в базу 2 и обратно. Вы можете сделать необходимые операции в исходном базовом представлении.

Таким образом, первым шагом является выполнение повторяющейся операции деления по модулю.

def convertBase(n,original_base,destination_base):
    digits = []    
    while not is_zero(n):
        digits.insert(0,modulo_div(n,original_base,destination_base))
    return digits

Поскольку внутренним представлением являются цифры, нужно сделать специальную функцию для проверки нуля

def is_zero(n):
    for d in n:
        if d != 0:
            return False
    return True

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

def modulo_div(n,original_base,destination_base):
    carry = 0
    for i in range(len(n)):
        d = n[i]
        d+=original_base*carry 
        carry = d%destination_base 
        d=(d//destination_base)
        n[i] = d
        #print(i,d,carry)
    return carry

просто проверка, чтобы убедиться, что код правильный:

print(convertBase([1,1,2,0], 3, 2))
#[1, 0, 1, 0, 1, 0]

print(convertBase([1, 0, 1, 0, 1, 0], 2, 3))
#[1, 1, 2, 0]
Ксавье Комбель
источник
Спасибо за публикацию, но учтите, что мы не являемся сайтом кодирования, поэтому большой блок кода не подходит в качестве ответа здесь. Особенно, когда вопрос прямо говорит: «Мне не нужен код, мне просто нужна базовая математика».
Дэвид Ричерби
@DavidRicherby Я пытался добавить текст.
Ксавье Комбель,
Спасибо. И я вижу, что на этой странице чертовски много кода, несмотря на то, что я сказал!
Дэвид Ричерби
0

Я знаю простой способ сделать базовое преобразование, которое не требует компьютерной программы. Это путем определения способа преобразования из любой базы в базу 2 и наоборот, а затем покрытия из одной базы в другую базу путем первого преобразования из первой базы в базу 2, а затем преобразования из базы 2 в другую базу. 2 так легко умножить или разделить на любую базу.

Чтобы преобразовать из любой базы в базу 2, все, что вам нужно сделать, это распознать, что для любого числа, если вы возьмете его запись из базы 2 и начнете с 0, а затем для каждой цифры в порядке слева направо, удвойте, если эта цифра равна нулю и вдвое больше, чем 1, если эта цифра равна 1, вы получите сам этот номер. Теперь, учитывая это число в любой базе, вы можете разделить на 2 в этой базе, чтобы получить частное и остаток. Если остаток равен 1, последняя двоичная цифра равна 1, а если остаток равен 0, последняя двоичная цифра равна 0. Разделите снова на 2. Если остаток равен 1, вторая последняя цифра равна 1, а если остаток равен 0, вторая последняя цифра равна 0 и т. Д., Пока вы не получите коэффициент 0.

Чтобы преобразовать из базы 2 в любую базу, все, что вам нужно сделать, это в этой базе, начать с 0, затем для каждой двоичной цифры, идущей слева направо, удвоить в этой базе, если эта цифра равна 0, и удвоить, затем добавить 1 в эту база, если эта цифра 1.

Тимоти
источник
2 is so easy to multiply or divide by in any base.Я не вижу этого для нечетных оснований, которые больше, чем один из любой степени двух (11 и 13, для начала).
седобородый
0

Вы можете конвертировать из базы n в базу 10 без какого-либо преобразования в некоторую промежуточную базу.

Например, для преобразования из базы n в базу 9 вы берете алгоритм преобразования в базу 10 и заменяете «10» на «9». То же самое для любой другой базы.

gnasher729
источник