2025/26, 9-профиль, C++: Системы счисления

Общая информация по задачам

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

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

При этом числа удобней хранить в виде vector<int> при этом в элементе массива с индексом 0 хранится младший разряд, а в последнем элементе — старший разряд, то есть запись числа нужно развернуть.

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

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

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

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

hex2int('9')

9

hex2int('F')

15

Дано значение типа int от 0 до 15. Запишите его виде 16-ричной цифры.

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

int2hex(9)

'9'

int2hex(15)

'F'

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

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

Решение должно использовать схему Горнера (в частности, в решении не должны вычисляться степени числа 2). Все символы строки должны обрабатываться внутри общего цикла, от старшего разряда к младшему.

bin2int("10110011"s)

179

Переведите значение из 16-ричной системы счисления в тип int. Решение оформите в виде функции int hex2int(string s). Сдайте на проверку только тело функции.

hex2int("B3"s)

179

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

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

int2bin(179)

"10110011"s

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

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

int2hex(179)

"B3"s

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

На вход программа получает три величины: \(n\), \(a\), \(k\), где \(n\) и \(k\) — натуральные числа от 2 до 36, основания систем счисления, \(a\) — число, записанное в в системе счисления с основанием \(n\), \(0\le a\le 2^{31}\).

Необходимо вывести значение \(a\) в системе счисления с основанием \(k\).

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

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

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

hex2bin("2F"s)

"101111"s

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

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

bin2hex("101111"s)

"2F"s

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

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

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

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

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

ter2int("$01"s)

-8

Рассмотрим последовательность Фибоначчи: \(\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\) нет двух единиц подряд.

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

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

Дана запись числа в фибоначчиевой системе счисления. Переведите его в тип int. Гарантируется, что результат принимает значения от 0 до \(2\times 10^9\).

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

fib2int("10101"s)

12

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

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

int2ter(-8)

"$01"s

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

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

int2fib(12)

"10101"s

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

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

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

string n = "19A"s;
inc(n, 11);
cout << n << endl;

1A0

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

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

string n = "1A0"s;
dec(n, 11);
cout << n << endl;

19A

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

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

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

string n = "$01"s;
inc_ter(n);
cout << n << endl;

$1$

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

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

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

string n = "$1$"s;
dec_ter(n);
cout << n << endl;

$01

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

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

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

string n = "100101"s;
inc_fib(n);
cout << n << endl;

101000

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

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

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

string n = "101000"s;
dec_fib(n);
cout << n << endl;

100101

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

Решение оформите в виде функции string sum_hex(string n1, string n2). На проверку сдайте только тело функции.

sum_hex("F1"s, "F"s)

"100"s

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

Решение оформите в виде функции string sum_ter(string n1, string n2). На проверку сдайте только тело функции.

sum_ter("1$$$"s, "$0$"s)

"11"s

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

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

Решение оформите в виде функции string sum_fib(string n1, string n2). На проверку сдайте только тело функции.

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

sum_fib("10010"s, "10101"s)

"1000001"s

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

Решение оформите в виде функции string dif_hex(string n1, string n2). На проверку сдайте только тело функции.

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

dif_hex("100"s, "F"s)

"F1"s

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

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

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

dif_fib("1000001"s, "10101"s)

"10010"s

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

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

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

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

mul_hex("A38"s, "D"s)

"84D8"s

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

Решение оформите в виде функции string mul_hex(string n1, string n2). На проверку сдайте только тело функции.

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

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

• Переход к большему основанию системы счисления (например, к основанию 256 или 65536).

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

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

mul_hex("A1"s, "7F"s)

"4FDF"s

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

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

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

int2fib(13)

"10110"s

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

Решение оформите в виде функции string mul_hex(string n1, string n2). На проверку сдайте только тело функции.

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

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

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

mul_hex("A1"s, "7F"s)

"4FDF"s