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

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

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

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

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

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

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

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

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

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

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 242.

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

Ответ: 11

Дано: N — натуральное число. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 242.

Приписать справа 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.

Обоснование конечного перебора.
Ниже проверяются все натуральные N от 1 до 11 включительно. Для минимального N достаточно найти первый подходящий вход: ни одно большее N уже не может улучшить ответ.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход 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.

Первый вход, для которого R не меньше 242: N = 11, R = 307. Все меньшие N есть в таблице и не удовлетворяют требованию.

Проверка выбранного входа: N = 11 = 102₃.
Преобразованная запись: 102101₃.
R = 243 + 54 + 9 + 1 = 307.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 11.

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

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

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

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

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

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

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

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