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

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

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

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

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

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

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

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

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ это число 10011₂ = 19₁₀.

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

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

Ответ: 26

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

Рассматриваем остаток N при делении на 3. Если он равен 1, дописывается запись числа 3, то есть 11; если равен 2, дописывается запись числа 6, то есть 110. Для кратного 3 числа с хотя бы тремя двоичными цифрами значение последних трёх цифр равно остатку N при делении на 8.
Общие формулы: R = 4N + 3 при остатке 1; R = 8N + 6 при остатке 2; R = 8N + (N mod 8) при кратном 3 числе N ≥ 6. Здесь mod означает остаток от деления.
Во всех ветвях R ≥ 4N. Для малого N = 3 запись 11 содержит лишь две цифры: копирование имеющихся цифр даёт 1111₂ = 15, дополнение копии до 011 даёт 11011₂ = 27. Оба значения ниже рассматриваемой границы и не меняют искомый экстремум. В таблице для N = 3 указано 15; остальные строки не зависят от этой особенности формулировки.

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

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 7; N = 2, R = 22; N = 3, R = 15; N = 4, R = 19.
N = 5, R = 46; N = 6, R = 54; N = 7, R = 31; N = 8, R = 70.
N = 9, R = 73; N = 10, R = 43; N = 11, R = 94; N = 12, R = 100.
N = 13, R = 55; N = 14, R = 118; N = 15, R = 127; N = 16, R = 67.
N = 17, R = 142; N = 18, R = 146; N = 19, R = 79; N = 20, R = 166.
N = 21, R = 173; N = 22, R = 91; N = 23, R = 190; N = 24, R = 192.
N = 25, R = 103; N = 26, R = 214.

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

Проверка выбранного входа: N = 26 = 11010₂.
Преобразованная запись: 11010110₂.
R = 128 + 64 + 16 + 4 + 2 = 214.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 26.

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

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

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

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

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

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

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

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