Question

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом:

1. Строится троичная запись числа $N$.
2. Если $N$ не кратно 3, то остаток от деления на 3 умножается на 5, переводится в троичную запись и дописывается в конец числа.
3. Результат $R$ переводится в десятичную систему счисления и выводится на экран.

Укажите минимальное число $N$, после обработки которого автомат получает число, большее 146.

Accepted Answer

8

Answer

Идея решения: перебрать натуральные числа, для каждого выполнить описанное преобразование и найти первое число, дающее результат больше 146.

Алгоритм:
1. Для каждого числа $N$ от 1 до некоторого предела переводим его в троичную систему.
2. Если $N$ не делится на 3 нацело, вычисляем остаток, умножаем на 5, переводим в троичную систему и приписываем к строке.
3. Полученную троичную строку интерпретируем как число в системе счисления 3 и переводим в десятичную.
4. Если результат превышает 146, выводим $N$ и завершаем поиск.

```python
for i in range(1, 100):
    n = i
    s = ""
    
    # Перевод N в троичную систему
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    
    # Если N не кратно 3, добавляем остаток * 5 в троичной форме
    if i % 3 != 0:
        m = (i % 3) * 5
        t = ""
        while m > 0:
            t = str(m % 3) + t
            m //= 3
        s += t
    
    # Переводим результат из троичной в десятичную
    r = int(s, 3)
    
    if r > 146:
        print(i)
        break
```

Проверим для $N = 8$:
- Троичная запись 8: $8 = 2 \cdot 3 + 2$, $2 = 0 \cdot 3 + 2$, получаем $22_3$.
- $8 \mod 3 = 2$, умножаем на 5: $2 \cdot 5 = 10$.
- Троичная запись 10: $10 = 1 \cdot 3 + 1$, $3 = 1 \cdot 3 + 0$, получаем $101_3$.
- Объединяем: $22101_3$.
- Переводим в десятичную: $2 \cdot 81 + 2 \cdot 27 + 1 \cdot 9 + 0 \cdot 3 + 1 = 162 + 54 + 9 + 1 = 226 > 146$. ✓

Задание №5Системы счисления и арифметикаЕГЭ по информатике