Условие задачи
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится троичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.
Пример: для числа 11 = 102₃ результат — 102101₃ = 307; для числа 12 = 110₃ результат — 11010₃ = 111.
Укажите минимальное число R, большее 150, которое может быть получено с помощью описанного алгоритма.
Алгоритм решения
1. Перебор чисел: Создать цикл for N in range(1, 10000): (диапазон обычно небольшой, можно увеличить при необходимости).
2. Перевод в систему счисления (СС): В нашем случае нужна троичная система счисления. Для неё нет встроенной функции в Python (bin — двоичная, oct — восьмеричная, hex — шестнадцатеричная). Поэтому пишем свою функцию перевода через деление с остатком:
123456
3. Обработка: Проверяем, делится ли N на 3. Если делится — дописываем две последние цифры троичной записи. Если не делится — считаем остаток, умножаем на 5, переводим в троичную и дописываем.
Для получения двух последних цифр строки используем срез s[-2:] — он берёт символы с предпоследнего до конца строки. Соответственно проверка будет выглядеть следующим образом:
12
Если N не делится на 3, то остаток от деления N % 3 равен 1 или 2. Умножаем его на 5 и переводим результат в троичную запись той же функцией:
123
Например, если остаток = 2, то 2 × 5 = 10, а 10 в троичной — это '101'. Эта строка дописывается в конец.
4. Обратный перевод: Переводим итоговую троичную строку обратно в десятичную систему: R = int(s, 3).
5. Условие и вывод: Проверяем условие if R > 150 и добавляем подходящие R в список. В конце выводим min(results), так как ищем минимальное R.
Решение
12345678910111213141516171819
Ответ: 162
