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

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

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

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

Например, для исходного числа 6₁₀ = 110₂ результатом является число 1000_{2 =}8₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 1101₂= 13₁₀.

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

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

КЭС:

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

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

3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»

3.5 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

Краткий ответ

Номер: 930BF4

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

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

Ответ: 11

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

Пусть k — длина исходной двоичной записи, s — количество единиц, p — остаток s при делении на 2. Сначала дописываем p справа, и только затем заменяем два левых разряда на 10 при p = 0 или на 11 при p = 1.
При k ≥ 2 обозначим через t значение исходной записи без двух первых цифр: t = N mod 2ᵏ⁻². Тогда общая формула R = (2 + p) · 2ᵏ⁻¹ + 2t + p. Здесь mod означает остаток от деления. Для N = 1 отдельно получаем 1 → 11 → 11, то есть R = 3.
Новая запись имеет k + 1 разрядов и начинается с единицы, поэтому R ≥ 2ᵏ, а N меньше 2ᵏ. Следовательно, R ≥ N. Чётность N здесь не заменяет чётность количества единиц.

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

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 3; N = 2, R = 7; N = 3, R = 4; N = 4, R = 13.
N = 5, R = 10; N = 6, R = 8; N = 7, R = 15; N = 8, R = 25.
N = 9, R = 18; N = 10, R = 20; N = 11, R = 31.

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

Проверка выбранного входа: N = 11 = 1011₂.
Количество единиц равно 3; после добавления бита получаем 10111, после замены первых двух цифр — 11111.
Преобразованная запись: 11111₂.
R = 16 + 8 + 4 + 2 + 1 = 31.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 11.

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

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

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

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