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

Упражнения

В системе счисления с основанием больше 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

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

Решение оформите в виде функции 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

Рассмотрим последовательность Фибоначчи: F1=1, F2=2, Fn=Fn-1+Fn-2 при n>2. В частности, F3=2, F4=3, F5=5, F6=8 и т.д.

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

Будем говорить, что число A представимо в фибоначчиевой системе счисления в виде akak-1...a2, где ai∈{0;1}, если A=akFk+...+a2F2 и в записи akak-1...a2 нет двух единиц подряд.

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

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

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

Дана запись числа в фибоначчиевой системе счисления. Переведите его в тип int. Гарантируется, что результат может пр0 до 2·109.

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

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

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

Дано целое число oт -2·109 до 2·109. Выведите его представление в уравновешенной троичной системе счисления без лидирующих нулей.

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

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

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

Дано целое число oт 0 до 2·109. Выведите его представление в фибоначчиевой системе счисления без лидирующих нулей.

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

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

N: Инкремент

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

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

Первый параметр — запись числа в некоторой системе счисления, запись содержит символы '0', ..., '9', 'A', ..., 'Z', второй параметр — основание системы счилсения. Длина числа не превосходит 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.

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