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

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

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

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

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

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

б) если число N нечётное, то в конец двоичной записи (справа) дописываются два нуля, а в начало (слева) дописывается единица.

Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

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

Например, для исходного числа 13₁₀ = 1101₂ результатом является число 1110100₂ = 116₁₀, а для исходного числа 6₁₀ = 110₂ это число 1111011₂ = 123₁₀.

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

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

КЭС:

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

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

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

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

Тип ответа:

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

Номер: F2E53C

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

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

Ответ: 52

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

Пусть k — длина двоичной записи N; тогда 2ᵏ больше N. Дописывание двух разрядов справа умножает число на 4; префикс 11 слева даёт добавку 3 · 2ᵏ⁺², префикс 1 — добавку 2ᵏ⁺².
Общие формулы: R = 3 · 2ᵏ⁺² + 4N + 3 при чётном N; R = 2ᵏ⁺² + 4N при нечётном N.
В первой ветви R больше 16N, во второй — больше 8N. Поэтому для обеих ветвей верна оценка R ≥ 8N.

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 6. При N ≥ 7 нижняя оценка даёт R ≥ 8 · 7 = 56, что больше 55.
Такие N нарушают верхнюю границу из условия.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 12; N = 2, R = 59; N = 3, R = 28; N = 4, R = 115.
N = 5, R = 52; N = 6, R = 123.

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

Проверка выбранного входа: N = 5 = 101₂.
Преобразованная запись: 110100₂.
R = 32 + 16 + 4 = 52.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 52.

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

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

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

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