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

Упражнения

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

Числа в различных системах счисления будут храниться в строках, при этом при вводе-выводе в элементе с индексом строки будет храниться старший разряд числа, а в последнем элементе — младший разряд. Но при обработке чисел удобней, если в элементе с индексом 0 хранится младший разряд, а в последнем элементе — старший разряд, то есть запись числа нужно развернуть.

Для разворота контейнера (вектора, строки) или её части можно использовать функцию reverse из файла algorithm. Она используется так же, как и sort:

reverse(s.begin(), s.end());

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

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

Решение оформите в виде функции int hex2int(char c). Сдайте на проверку только тело функции.

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

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

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

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

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

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

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

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

Решение оформите в виде функции int bin2int(string s). Сдайте на проверку только тело функции.

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

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

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

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

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

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

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

Решение оформите в виде функции string int2bin(int n). Сдайте на проверку только тело функции.

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

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

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

Решение оформите в виде функции string int2hex(int n). Сдайте на проверку только тело функции.

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

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

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

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

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

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

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

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

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

Решение оформите в виде функции string hex2bin(string s). Сдайте на проверку только тело функции.

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

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

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

Решение оформите в виде функции string bin2hex(string s) Сдайте на проверку только тело функции.

Вызов функции	Возвращаемое значение
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.

Решение оформите в виде функции int ter2int(string s). Сдайте на проверку только тело функции.

Вызов функции	Возвращаемое значение
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. Гарантируется, что результат принимает значения от 0 до $2\times 10^9$.

Решение оформите в виде функции int fib2int(string s). Сдайте на проверку только тело функции.

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

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

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

Решение оформите в виде функции string int2ter(int n). Сдайте на проверку только тело функции.

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

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

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

Решение оформите в виде функции string int2fib(int n). Сдайте на проверку только тело функции.

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

N: Инкремент

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

Решение оформите в виде функции void inc(string & n, int base). Сдайте на проверку только тело функции.

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

Вызов функции	Вывод
string n = "19A"; inc(n, 11); cout << n << endl;	1A0

O: Декремент

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

Решение оформите в виде функции void dec(string & n, int base). Сдайте на проверку только тело функции.

Вызов функции	Вывод
string n = "1A0"; dec(n, 11); cout << n << endl;	19A

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

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

Решение оформите в виде функции void inc_ter(string & n). Сдайте на проверку только тело функции.

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

Вызов функции	Вывод
string n = "$01"; inc_ter(n); cout << n << endl;	$1$

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

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

Решение оформите в виде функции void dec_ter(string & n). Сдайте на проверку только тело функции.

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

Вызов функции	Вывод
string n = "$1$"; dec_ter(n); cout << n << endl;	$01

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

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

Решение оформите в виде функции void inc_fib(string & n). На проверку сдайте только тело функции.

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

Вызов функции	Вывод
string n = "100101"; inc_fib(n); cout << n << endl;	101000

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

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

Решение оформите в виде функции void dec_fib(string & n).

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

Вызов функции	Вывод
string n = "101000"; dec_fib(n); cout << n << endl;	100101

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Переведите строку в массив цифр (значений типа int), все вычисления проводите только с числами, а не со строками. Перевод обратно в строку выполняйте в самом конце.
“Разверите“ число: под индексом $i$ в списке должна храниться цифра, соответствующая $16^i$. Тогда при перемножении двух цифр $a_i$ и $b_j$ результат попадает в разряд $i+j$.
Можно не обращать внимания на переполнения разрядов и не следить за тем, что все полученные цифры будут меньше 16. Считайте, что вы храните произвольные коэффициенты, соответствующие степеням основания, а нормализацию представления выполните в самом конце.

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

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

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

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

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

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

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

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

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

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

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

Метод Карацубы — рекурсивный алгоритм, вы сводите задачу умножения длинных чисел к задаче умножение чисел меньшей длины. При этом при маленькой длине чисел метод Карацубы не даёт выгоды, используйте умножение “в столбик”. Скорее всего при длинах чисел меньше 100 выгоднее использовать умножение “в столбик”, а не метод Карацубы. Возможно, вам придется подбирать эту границу экспериментально.
Перемножать нужно не строки, а массивы чисел, чтобы не заниматься постоянным преобразованием символов 16-ричной системы счисления в int и обратно. В начале перевести строки в массивы int, в конце выполнить обратное преобразование.
Можно не обращать внимания на переполнение разрядов и даже можно считать, что при умножении в некоторых разрядах могут получаться отрицательные значения (там же есть вычитание). Да и вычитание можно реализовать без заёма значений из старших разрядов, просто считайте, что цифры могут быть и отрицательными. Нормализацию представления результата выполняйте в самом конце.

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