Обычно мы имеем дело с десятичной системой счисления, в которой используется ровно 10 цифр: 0..9, и мы все к этому сильно привыкли. Но для обозначения чисел возможно использование других систем, отличных от десятичной. Особенностью таких систем является, отличное от 10 количество используемых цифр. Например, в двоичной системе используется только две цифры - 0 и 1; и любое число может быть представлено в такой системе. Если система имеет порядок, больший чем 10, то в качестве следующих цифр используются латинские буквы; например, в шестнадцатеричной системе присутствуют следующие цифры: 0..9,A,B,C,D,E и F.
Для того, чтобы представить какое либо число в десятичной системе счисления, следует вычислить сумму всех цифр данного числа, умноженных на порядок системы счисления, возведенной в степень, равную номеру разряда данной цифры. Следующие примеры демонстрируют суть данного метода:
Для перевода из десятичной системы счисления в систему с основанием k необходимо производить деление исходного числа на k, запоминая остатки от деления и продолжая данную операцию с целочисленным значением деления до тех пор, пока результатом деления не будет ноль. Искомым представлением числа будет запись, составленная из полученных остатков от деления, записанных в обратном порядке. Ниже представлены примеры перевода:
При решении олимпиадных задач обычно рассматривают системы счисления с основаниями от 2 до 36. Это связано с тем, что в латинском алфавите 26 букв (10 цифр + 26 букв = 36 символов). Для хранения цифр числа можно использовать как целочисленный массив, так и строку. Для хранения десятичного числа и основания системы счисления будем использовать целочисленные переменные x и k соответственно, а для хранения числа в системе счисления с основанием k используем строковую переменную s:
Пусть s - число, записанное в k-ой системе счисления (k ≤ 10) в переменной типа string. Мы желаем осуществить перевод в десятичную систему счисления, а результат сохранить в переменной x типа int. Тогда реализация данного алгоритма на языке C++ может быть представлена следующим образом:
Алгоритм перевода из десятичной системы числа x в систему с основанием k (k ≤ 10) и записи его в s может быть представлен так:
В описанных выше фрагментах кода присутствует число 48, так как ASCII-коды символов, обозначающих цифры, превышают на 48 значения самих цифр (int('0')=48, int('1')=49, ..., int('9')=57). В случае, если необходимо работать с системами счисления с основанием, превышающим 10 (k > 10), то для преобразования буквенных значений следует добавлять или вычитать 55 (int('A')=65, int('B')=66, ..., int('Z')=90).
Для того, чтобы перевести из k-ой системы счисления в систему с основанием m, можно воспользоваться "принципом чайника" и перевести сначала из k-ой системы в 10-ую, а затем из 10-ой в m-ую. Однако, иногда этой двойной операции можно избежать. Речь идет о случае, когда мы имеем дело с кратными системами счисления. Например, несложно переводить из 2-ой в 4-ую, 8-ую, 16-ную и обратно; аналогично можно сказать о 3-ой и 27-ой системах или о 5-ой и 25-ой. В подобных случаях каждая цифра числа в системе с большим основанием представляется в виде нескольких цифр системы с меньшим основанием. Так, в 4-ой системе каждая цифра представляется 2-мя цифрами 2-ой системы, в 8-ой - 3мя цифрами 2-ой, а в 16-ой каждая цифра есть ничто иное как 4 цифры 2-ой системы. Например, для перевода двоичного числа 101100101010011011 в 16-ую систему достаточно разбить число на 4ки: 0010 1100 1010 1001 1011 и записать каждую из них в 16-ом формате: 2CA9B, т.к. 0010 = 2, 1100 = B, 1010 = A, 1001 = 9 и 1011 = B. Несложно догадаться, что обратное преобразование из 16-ой в 2-ую систему происходит аналогичным образом.
