Системы счисления

Упражнения

В системе счисления с основанием больше 10, цифры записываются так: 0, 1, 2, ..., 9, A, B, C, ...

В тексте программ на языке Python можно использовать целочисленные константы, записанные в двоичной (префикс 0b), восьмеричной (префикс 0o) и шестнадцатеричной (префикс 0x) системах счисления. После указанного префикса идут цифры, которые в двоичной системе счисления могут быть только 0 или 1, в восьмеричной — от 0 до 7, в шестнадцатеричной — от 0 до 9, а также буквы латинского алфавита от A до F (могут быть как строчными, так и заглавными). Например, десятичной число 179 можно задать несколькими способами.

A = 179
A = 0b10110011
A = 0o263
A = 0xB3

Если вы знаете стандартные функции языка Python для перевода представления чисел между различными системами счисления, то этими функциями пользоваться нельзя. Также нельзя использовать функции типа eval, exec и т.д.

Если программа выводит результат в системе счисления с основанием больше 10, то цифры записываются так: 0, 1, 2, ..., 9, A, B, C, ...

A: Шестнадцатеричную цифру в int

Дана шестнадцатеричная цифра, записанная в строке из одного символа. Определите её числовое значение.

Решение оформите в виде функции hex2int(c: str) -> int.

На проверку сдайте только тело функции.

В решении нельзя использовать списки, словари, строки типа "ABCDEF" и т.д.

Вызов функции Возвращаемое значение
hex2int('9')
9
hex2int('F')
15

B: int в шестнадцатеричную цифру

Решите задачу, обратную предыдущей.

Решение оформите в виде функции int2hex(n: int) -> str.

Вызов функции Возвращаемое значение
int2hex(9)
'9'
int2hex(15)
'F'

C: Из двоичной в int

Дано число, записанное в двоичной системе счисления. Переведите его в тип int.

Решение оформите в виде функции bin2int(s: str) -> int.

Решение должно использовать схему Горнера.

Вызов функции Возвращаемое значение
bin2int('10110011')
179

D: Из шестнадцатеричной в int

Решите предыдущую задачу в случае, когда входное число задано в шестнадцатеричном виде. Соответствующая функция должна называться hex2int(s: str) -> int.

Вызов функции Возвращаемое значение
hex2int('B3')
179

E: Из int в двоичную

Переведите число из int в двоичную систему числения.

Решение оформите в виде функции int2bin(n: int) -> str.

Вызов функции Возвращаемое значение
int2bin(179)
'10110011'

F: Из int в шестнадцатеричную

Переведите число из десятичной системы в шестнадцатеричную.

Решение оформите в виде функции int2hex(n: int) -> str.

Вызов функции Возвращаемое значение
int2hex(179)
'B3'

G: Из любой в любую

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

На вход программа получает три величины: n, A, k, где n и k – натуральные числа от 2 до 36: основания системы счисления, A – число, записанное в в системе счисления с основанием n, A<231.

Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.

Решение должно содержать две функции перевода — из числа в произвольной системе счисления, записанного в переменной типа str в переменную типа int и обратно.

Ввод Вывод
2
101111
16
2F
10
35
36
Z

H: Из шестнадцатеричной в двоичную

Переведите число из шестнадцатеричной системы счисления в двоичную. Исходное число может быть очень большим (до \(2\times10^5\) символов). Необходимо вывести результат без лидирующих нулей.

Решение оформите в виде функции hex2bin(s: str) -> str

Вызов функции Возвращаемое значение
hex2bin('2F')
'101111'

I: Из двоичной в шестнадцатеричную

Переведите число из двоичной системы счисления в шестнадцатеричную. Исходное число может быть очень большим (до \(1{,}2\times10^6\) символов).

Решение оформите в виде функции bin2hex(s: str) -> str

Вызов функции Возвращаемое значение
bin2hex('101111')
'2F'

J: Из уравновешенной троичной в int

В уравновешенной троичной системе счисления используется основание 3 и три цифры: 0, 1 и -1. Цифру -1 будем обозначать знаком $. Достоинство уравновешенной троичной системы счисления: простота хранения отрицательных чисел и удобство нахождения числа, противоположному данному.

Вот как записываются небольшие числа в уравновешенной троичной системе счисления:

Десятичная -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
Уравнов. троичная $00 $01 $1$ $10 $11 $$ $0 $1 $ 0 1 1$ 10 11 1$$ 1$0 1$1 10$ 100

Подробней о уравновешенной троичной системе счисления можно прочитать в Википедии (статья Троичная система счисления, там используется термин "троичная симметричная система счисления").

Дана запись числа в уравновешенной троичной системе счисления. Переведите её в значение типа int.

Решение оформите в виде функции ter2int(s: str) -> int

Вызов функции Возвращаемое значение
ter2int('$01')
-8

K: Из фибоначчиевой в int

Рассмотрим последовательность Фибоначчи: \(\varphi_1=1\), \(\varphi_2=2\), \(\varphi_n=\varphi_{n-1}+\varphi_{n-2}\) при \(n\gt 2\). В частности, \(\varphi_3=3\), \(\varphi_4=5\), \(\varphi_5=8\) и т.д.

Любое натуральное число можно представить в виде суммы нескольких членов последовательности Фибоначчи. Такое представление будет неоднозначным, но если наложить дополнительное условие, что в представлении нет двух соседних членов последовательности Фибоначчи, то представление становится единственным.

Будем говорить, что число \(A\) представимо в фибоначчиевой системе счисления в виде \(a_ka_{k-1}...a_1\), где \(a_i\in\{0;1\}\), если \(A=a_k\varphi_k+...+a_1\varphi_1\) и в записи \(a_ka_{k-1}...a_1\) нет двух единиц подряд.

Вот как записываются небольшие числа в фибоначчиевой системе счисления:

Десятичная 1 2 3 4 5 6 7 8 9 10 11 12 13
Фибоначчиева 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000

Подробней о фибоначчиевой системе счисления можно прочитать в Википедии (статья Фибоначчиева система счисления).

Дана запись числа в фибоначчиевой системе счисления. Переведите его в тип int.

Решение оформите в виде функции fib2int(s: str) -> int

Вызов функции Возвращаемое значение
fib2int('10101')
12

L: Из int в уравновешенную троичную

Дано целое число oт \(-2\times 10^9\) до \(2\times 10^9\). Найдите его представление в уравновешенной троичной системе счисления без лидирующих нулей (за исключением числа 0, запись которого имеет вид 0).

Решение оформите в виде функции int2ter(n: int) -> str

Вызов функции Возвращаемое значение
int2ter(-8)
'$01'

M: Из int в фибоначчиеву

Дано целое число oт 1 до \(2\times 10^9\). Выведите его представление в фибоначчиевой системе счисления без лидирующих нулей.

Решение оформите в виде функции int2fib(n: int) -> str

Вызов функции Возвращаемое значение
int2fib(12)
'10101'

N: Инкремент

Дана запись числа в некоторой системе счисления. Увеличьте число на 1 и верните его представление в этой же системе счисления. Сдайте на проверку только тело функции.

Решение оформите в виде функции inc(n: str, base: int) -> str.

Первый параметр — запись числа в некоторой системе счисления, запись содержит символы '0', ..., '9', 'A', ..., 'Z', второй параметр — основание системы счисления, не превосходящее 36. Длина числа не превосходит 100000 символов.

Вызов функции Возвращаемое значение
inc('19A', 11)
'1A0'

O: Декремент

Решите аналогичную задачу для уменьшения числа на 1.

Решение оформите в виде функции dec(n: str, base: int) -> str.

Ввод Вывод
dec('1A0', 11)
'19A'

P: Инкремент в уравновешенной троичной системе счисления

Реализуйте инкремент числа в уравновешенной троичной системе счисления.

Решение оформите в виде функции inc_ter(n: str) -> str.

Входная строка может иметь длину до 100000 символов.

Вызов функции Возвращаемое значение
inc_ter('$01')
'$1$'

Q: Декремент в уравновешенной троичной системе счисления

Реализуйте декремент числа в уравновешенной троичной системе счисления.

Решение оформите в виде функции dec_ter(n: str) -> str.

Входная строка может иметь длину до 100000 символов.

Вызов функции Возвращаемое значение
dec_ter('$1$')
'$01'

R: Фибоначчиев инкремент

Реализуйте инкремент числа в фибоначчиевой системе счисления.

Решение оформите в виде функции inc_fib(n: str) -> str.

Входная строка может иметь длину до 100000 символов.

Вызов функции Возвращаемое значение
inc_fib('100101')
'101000'

S: Фибоначчиев декремент

Реализуйте декремент числа в фибоначчиевой системе счисления.

Решение оформите в виде функции dec_fib(n: str) -> str.

Входная строка может иметь длину до 100000 символов.

Вызов функции Возвращаемое значение
dec_fib('101000')
'100101'

T: Шестнадцатеричное сложение

Дано два шестнадцатеричных числа, длиной до 100000 символов каждый. Вычислите их сумму.

Решение оформите в виде функции sum_hex(n1: str, n2: str) -> str.

Вызов функции Возвращаемое значение
sum_hex('F1', 'F')
'100'

U: Уравновешенное троичное сложение

Реализуйте сложение в уравновешенной троичной системе счисления.

Решение оформите в виде функции sum_ter(n1: str, n2: str) -> str.

Вызов функции Возвращаемое значение
sum_ter('1$$$', '$0$')
'11'

Пример соответствует выражению 14+(-10)=4.

V: Фибоначчиево сложение

Реализуйте сложение в фибоначчиевой системе счисления.

Решение оформите в виде функции sum_fib(n1: str, n2: str) -> str.

Сложность решения: квадрат от длины входных чисел (длина входных чисел до 1000 знаков, ограничение по времени — 1 секунда).

Вызов функции Возвращаемое значение
sum_fib('10010', '10101')
'1000001'

W: Шестнадцатеричное вычитание

Реализуйте алгоритм вычитания двух чисел, записанных в шестнадцатеричной системе счисления.

Решение оформите в виде функции dif_hex(n1: str, n2: str) -> str.

Сложность решения: линейная от длины входных чисел (длина чисел до 100000 знаков, ограничение по времени — 1 секунда).

Вызов функции Возвращаемое значение
dif_hex('100', 'F')
'F1'

X: Фибоначчиево вычитание

Реализуйте вычитание в фибоначчиевой системе счисления.

Решение оформите в виде функции dif_fib(n1: str, n2: str) -> str. Гарантируется, что первое данное число не меньше второго.

Сложность решения: квадрат от длины входных чисел (длина чисел до 1000 знаков, ограничение по времени — 1 секунда).

Вызов функции Возвращаемое значение
dif_fib('1000001', '10101')
'10010'

Y: Умножение длинного числа на короткое

Реализуйте алгоритм умножения длинного числа, записанного в шестнадцатеричной системе счисления, на короткое число (из одной шестнадцатеричной цифры).

Решение оформите в виде функции mul_hex(n1: str, n2: str) -> str. Гарантируется, что второй параметр состоит ровно из одной цифры.

Сложность решения: линейная от длины первого числа (длина числа до 100000 знаков, ограничение по времени — 1 секунда).

Не забудьте, что в ответе может получиться 0, который записывается строкой "0".

Вызов функции Возвращаемое значение
mul_hex('A38', 'D')
'84D8'

Z: Шестнадцатеричное умножение

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

Решение оформите в виде функции mul_hex(n1: str, n2: str) -> str.

Сложность решения: квадрат от длины входных чисел (длина чисел до 1000 знаков).

Запрещённые в решении приёмы:

Советы по реализации:

Вызов функции Возвращаемое значение
mul_hex('A1', '7F')
'4FDF'

ZA: Развёрнутая фибоначчиева форма

В развёрнутой фибоначчиевой форме запись числа в фибоначчиевой системе счисления не содержит двух подряд идущих нулей. Для каждого числа существует единственное представление в развёрнутой фибоначчиевой форме.

Дано целое число oт 1 до 2·109. Найдите его представление в развёрнутой фибоначчиевой форме.

Решение оформите в виде функции int2fib(n: int) -> str

Вызов функции Возвращаемое значение
int2fib(13)
'10110'

ZZ: Умножение Карацубы

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

Решение оформите в виде функции mul_hex(n1: str, n2: str) -> str.

Требования к решению: вычисления должны проводиться в 16-ричной системе счисления (нельзя переходить к большему основанию, например, 256 или 65536). Длина входных чисел — до 10000 знаков, ограничение по времени — 10 секунд.

Советы по реализации

Вызов функции Возвращаемое значение
mul_hex('A1', '7F')
'4FDF'