5 НОМЕР - Решение задач (3/3)

Условие задачи

На вход алгоритма подаётся натуральное число 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 — шестнадцатеричная). Поэтому пишем свою функцию перевода через деление с остатком:

1
2
3
4
5
6

3. Обработка: Проверяем, делится ли N на 3. Если делится — дописываем две последние цифры троичной записи. Если не делится — считаем остаток, умножаем на 5, переводим в троичную и дописываем.

Для получения двух последних цифр строки используем срез s[-2:] — он берёт символы с предпоследнего до конца строки. Соответственно проверка будет выглядеть следующим образом:

1
2

Если N не делится на 3, то остаток от деления N % 3 равен 1 или 2. Умножаем его на 5 и переводим результат в троичную запись той же функцией:

1
2
3

Например, если остаток = 2, то 2 × 5 = 10, а 10 в троичной — это '101'. Эта строка дописывается в конец.

4. Обратный перевод: Переводим итоговую троичную строку обратно в десятичную систему: R = int(s, 3).

5. Условие и вывод: Проверяем условие if R > 150 и добавляем подходящие R в список. В конце выводим min(results), так как ищем минимальное R.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Ответ: 162