2026/27, 10В, Python: Системы счисления (часть 3.1)

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

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