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

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

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

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

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

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

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

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

Например, для исходного числа 4₁₀ = 100₂ результатом является число 20₁₀ = 10100₂, а для исходного числа 5₁₀ = 101₂это число 53₁₀ = 110101₂.

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

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

КЭС:

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

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

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

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

Тип ответа:

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

Номер: 9E31EF

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

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

Ответ: 109

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

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

Обоснование конечного перебора.
По условию 1 ≤ N ≤ 12. Проверяем весь этот отрезок и сравниваем результаты R; максимум R не обязан достигаться при самом большом N.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 13; N = 2, R = 10; N = 3, R = 29; N = 4, R = 20.
N = 5, R = 53; N = 6, R = 22; N = 7, R = 61; N = 8, R = 40.
N = 9, R = 101; N = 10, R = 42; N = 11, R = 109; N = 12, R = 44.

Максимальный результат среди всех разрешённых входов: R = 109, он достигается при N = 11.

Проверка выбранного входа: N = 11 = 1011₂.
Преобразованная запись: 1101101₂.
R = 64 + 32 + 8 + 4 + 1 = 109.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 109.

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

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

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

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