В системе счисления с основанием больше 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, ...
Дана шестнадцатеричная цифра, которую необходимо считать
в величину типа str
. Выведите ее десятичное значение.
Решение оформите в виде функции hex2int(c: str) -> int.
На проверку сдайте только тело функции.
В решении нельзя использовать списки, словари, строки типа "ABCDEF" и т.д.
Вызов функции | Возвращаемое значение |
---|---|
hex2int('9') |
9 |
hex2int('F') |
15 |
Решите задачу, обратную предыдущей.
Решение оформите в виде функции int2hex(n: int) -> str.
Вызов функции | Возвращаемое значение |
---|---|
int2hex(9) |
'9' |
int2hex(15) |
'F' |
Дано число, записанное в двоичной системе счисления. Переведите его в тип int.
Решение оформите в виде функции bin2int(s: str) -> int
.
Решение должно использовать схему Горнера.
Вызов функции | Возвращаемое значение |
---|---|
bin2int('10110011') |
179 |
Решите предыдущую задачу в случае, когда входное число задано в шестнадцатеричном виде. Соответствующая функция должна называться hex2int(s: str) -> int.
Вызов функции | Возвращаемое значение |
---|---|
hex2int('B3') |
179 |
Переведите число из int в двоичную систему числения.
Решение оформите в виде функции int2bin(n: int) -> str.
Вызов функции | Возвращаемое значение |
---|---|
int2bin(179) |
'10110011' |
Переведите число из десятичной системы в шестнадцатеричную.
Решение оформите в виде функции int2hex(n: int) -> str.
Вызов функции | Возвращаемое значение |
---|---|
int2hex(179) |
'B3' |
Напишите программу, переводящую запись числа между двумя произвольными системами счисления.
На вход программа получает три величины: n, A, k, где n и k – натуральные числа от 2 до 36: основания системы счисления, A – число, записанное в в системе счисления с основанием n, A<231.
Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.
Решение должно содержать две функции перевода — из числа в произвольной системе счисления, записанного в переменной типа str в переменную типа int и обратно.
Ввод | Вывод |
---|---|
2 |
2F |
10 |
Z |
Переведите число из шестнадцатеричной системы счисления в двоичную. Исходное число может быть очень большим (до \(2\times10^5\) символов). Необходимо вывести результат без лидирующих нулей.
Решение оформите в виде функции hex2bin(s: str) -> str
Вызов функции | Возвращаемое значение |
---|---|
hex2bin('2F') |
'101111' |
Переведите число из двоичной системы счисления в шестнадцатеричную. Исходное число может быть очень большим (до \(1{,}2\times10^6\) символов).
Решение оформите в виде функции bin2hex(s: str) -> str
Вызов функции | Возвращаемое значение |
---|---|
bin2hex('101111') |
'2F' |
В уравновешенной троичной системе счисления используется основание 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 |
Рассмотрим последовательность Фибоначчи: 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 |
Дано целое число oт -2·109 до 2·109. Выведите его представление в уравновешенной троичной системе счисления без лидирующих нулей.
Решение оформите в виде функции int2ter(n: int) -> str
Вызов функции | Возвращаемое значение |
---|---|
int2ter(-8) |
'$01' |
Дано целое число oт 0 до 2·109. Выведите его представление в фибоначчиевой системе счисления без лидирующих нулей.
Решение оформите в виде функции int2fib(n: int) -> str
Вызов функции | Возвращаемое значение |
---|---|
int2fib(12) |
'10101' |
Дана запись числа в некоторой системе счисления. Увеличьте число на 1 и верните его представление в этой же системе счисления.
Решение оформите в виде функции inc(n: str, base: int) -> str
.
Первый параметр — запись числа в некоторой системе счисления, запись содержит символы '0', ..., '9', 'A', ..., 'Z', второй параметр — основание системы счилсения. Длина числа не превосходит 100000 символов.
Вызов функции | Возвращаемое значение |
---|---|
inc('19A', 11) |
'1A0' |
Решите аналогичную задачу для уменьшения числа на 1.
Решение оформите в виде функции dec(n: str, base: int) -> str
.
Ввод | Вывод |
---|---|
dec('1A0', 11) |
'19A' |
Реализуйте инкремент числа в уравновешенной троичной системе счисления.
Решение оформите в виде функции inc_ter(n: str) -> str
.
Входная строка может иметь длину до 100000 символов.
Вызов функции | Возвращаемое значение |
---|---|
inc_ter('$01') |
'$1$' |
Реализуйте декремент числа в уравновешенной троичной системе счисления.
Решение оформите в виде функции dec_ter(n: str) -> str
.
Входная строка может иметь длину до 100000 символов.
Вызов функции | Возвращаемое значение |
---|---|
dec_ter('$1$') |
'$01' |
Реализуйте инкремент числа в фибоначчиевой системе счисления.
Решение оформите в виде функции inc_fib(n: str) -> str
.
Входная строка может иметь длину до 100000 символов.
Вызов функции | Возвращаемое значение |
---|---|
inc_fib('100101') |
'101000' |
Реализуйте декремент числа в фибоначчиевой системе счисления.
Решение оформите в виде функции dec_fib(n: str) -> str
.
Входная строка может иметь длину до 100000 символов.
Вызов функции | Возвращаемое значение |
---|---|
dec_fib('101000') |
'100101' |
Дано два шестнадцатеричных числа, длиной до 100000 символов каждый. Вычислите их сумму.
Решение оформите в виде функции sum_hex(n1: str, n2: str) -> str
.
Вызов функции | Возвращаемое значение |
---|---|
sum_hex('F1', 'F') |
'100' |
Реализуйте сложение в уравновешенной троичной системе счисления.
Решение оформите в виде функции sum_ter(n1: str, n2: str) -> str
.
Вызов функции | Возвращаемое значение |
---|---|
sum_ter('1$$$', '$0$') |
'11' |
Пример соответствует выражению 14+(-10)=4.
Реализуйте сложение в фибоначчиевой системе счисления.
Решение оформите в виде функции sum_fib(n1: str, n2: str) -> str
.
Вызов функции | Возвращаемое значение |
---|---|
sum_fib('10010', '10101') |
'1000001' |