Задание 5: Анализ и построение алгоритмов для исполнителей

Типичная формулировка: «Алгоритм получает на вход натуральное число $N$ и строит по нему новое число $R$: 1) переводит $N$ в систему с основанием $n$; 2) выполняет посимвольное преобразование цифр (замена, дополнение, дописывание); 3) переводит результат обратно в десятичную систему; 4) иногда добавляется финальный шаг — разность, сумма или сравнение с исходным числом». Дальше задаётся вопрос: найдите наибольшее/наименьшее $N$ или $R$, удовлетворяющее условию (например, не превышающее данное число, или дающее конкретный результат).

…

• Позиционная запись числа в системе с основанием $n$: $N = \sum_{i=0}^{k-1} a_i n^i$, где $a_i \in \{0,1,\dots,n-1\}$, $a_{k-1}\neq 0$.
• Число цифр $k$ представления $N$ в основании $n$ определяется условием $n^{k-1} \le N \le n^k-1$.
• Перевод из десятичной системы в систему с основанием $n$ — последовательное деление на $n$ с выписыванием остатков от последнего к первому.
• Дополнение цифры в системе с основанием $n$: замена $a_i$ на $(n-1)-a_i$. Для троичной системы это замена $0\leftrightarrow 2$, единица остаётся на месте.
• Если у числа с $k$ цифрами в основании $n$ заменить каждую цифру $a_i$ на $(n-1)-a_i$, то новое число (посчитанное с той же длиной $k$, даже если появляются ведущие нули) равно $M = (n^{k}-1) - N$. Удаление ведущих нулей не меняет численного значения $M$, меняется только запись.
• Дописывание к записи числа $N$ (длина $k$ цифр) блока из $m$ цифр со значением $v$ равносильно операции $R = N\cdot n^{m} + v$.
• Для двоичного случая ($n=2$) дополнение цифры — это инверсия бита: $a_i \to 1-a_i$, а формула дополнения принимает вид $M = (2^k - 1) - N$, что совпадает с побитовым «НЕ» числа $N$ в пределах $k$ разрядов.
• Для задач, где преобразование идёт по десятичным цифрам «окнами» (например, тройки соседних цифр), нужно помнить: для числа из $d$ цифр при окне длины $m$ получается $d-m+1$ окон.

1. Определить основание системы $n$, в которой строится запись числа (двоичная, троичная, десятичная «по цифрам»).
2. Расписать шаг преобразования как операцию над отдельной цифрой или как операцию над группой цифр (окно, дописывание, дополнение).
3. Найти длину $k$ представления $N$ в этой системе как функцию от диапазона значений $N$ (через неравенство $n^{k-1}\le N\le n^k-1$).
4. Вывести формулу $R(N,k)$, отражающую весь алгоритм целиком (включая финальные операции — разность, сумму, сравнение).
5. Если требуется найти $N$ по известному $R$ — составить уравнение $R=f(N,k)$, решить относительно $N$ при разных $k$, начиная с наименьших, и на каждом шаге проверять, что найденное $N$ действительно попадает в диапазон, соответствующий выбранному $k$. …