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

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

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

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

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

а) если число N делится на 3, то слева к нему приписывается «1», а справа «02»;

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

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

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

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

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

СВОЙСТВА ЗАДАНИЯ

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

Номер: E1DBA9

Статус задания: НЕ РЕШЕНО Ответить

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

Ответ: 8

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

Пусть k — длина троичной записи N. Для кратного 3 числа префикс 1 даёт добавку 3ᵏ, затем окончание 02 умножает полученное число на 9 и добавляет 2. В остальных случаях дописываются 5 = 12₃ или 10 = 101₃ соответственно остатку 1 или 2.
Общие формулы: R = 9 · 3ᵏ + 9N + 2 при кратном 3 числе; R = 9N + 5 при остатке 1; R = 27N + 10 при остатке 2.
Во всех ветвях R ≥ 9N.

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

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 14; N = 2, R = 64; N = 3, R = 110; N = 4, R = 41.
N = 5, R = 145; N = 6, R = 137; N = 7, R = 68; N = 8, R = 226.

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

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

Ответ: 8.

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

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

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

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

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

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

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