09DBE5 — Преобразование записи числа: ответ и решение

Впишите правильный ответ.

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

1. Строится троичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;

б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.

Полученная таким образом запись является троичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 11₁₀ = 102₃ результатом является число 102101₃ = 307₁₀, а для исходного числа 12₁₀ = 110₃ это число 11010₃ = 111₁₀.

Укажите минимальное число R, большее 133, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Решение задания EGEINF09DBE5

Ответ: 141

Дано: N — натуральное число. Укажите минимальное число R, большее 133, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Приписать справа d троичных цифр со значением t означает получить R = 3ᵈ · N + t. При остатке 1 от деления N на 3 дописывается 5 = 12₃; при остатке 2 — число 10 = 101₃. У кратного 3 натурального числа есть как минимум две троичные цифры; их значение равно N mod 9.
Общие формулы: R = 9N + (N mod 9) при кратном 3 числе; R = 9N + 5 при остатке 1; R = 27N + 10 при остатке 2. Здесь mod означает остаток от деления.
Каждая ветвь даёт R ≥ 9N.

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 16. При N ≥ 17 нижняя оценка даёт R ≥ 9 · 17 = 153, что больше 141.
В таблице уже есть допустимый результат R = 141; все пропущенные большие N дают ещё больший R и улучшить минимум не могут.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 14; N = 2, R = 64; N = 3, R = 30; N = 4, R = 41.
N = 5, R = 145; N = 6, R = 60; N = 7, R = 68; N = 8, R = 226.
N = 9, R = 81; N = 10, R = 95; N = 11, R = 307; N = 12, R = 111.
N = 13, R = 122; N = 14, R = 388; N = 15, R = 141; N = 16, R = 149.

Среди результатов, которые больше 133, наименьший равен 141. Он достигается при N = 15.

Проверка выбранного входа: N = 15 = 120₃.
Преобразованная запись: 12020₃.
R = 81 + 54 + 6 = 141.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 141.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF09DBE5.

Сообщение увидит только команда сайта: на странице оно не публикуется.

КЭС:	3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
Тип ответа:	Краткий ответ

Задание EGEINF09DBE5: Преобразование записи числа

Решение задания EGEINF09DBE5

Помочь улучшить сайт

Комментарии к решению