Модуль: Вопрос 05. Анализ простых алгоритмов


Меняем запись числа


Войдите на сайт, чтобы ответы сохранялись и баллы за тетрадь засчитывались.

Два разряда справа

Начнём с ближайшего R после границы. В цепочке цифр снимем добавленный хвост, восстановим N и проверим его вперёд.


Задача

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

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

2) Затем справа дописываются два разряда: символы 01, если число N чётное, и 10, если нечётное.

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


Разбор

Один из способов решения - пойти по алгоритму назад.
Если нужен минимальный R > 81 — возьмем числа 82, 83, 84 и посмотрим из какого N можно ихполучить…

Уберем с конца два бита (которые были добавлены в п2) → посмотрели N → анализируем N и смотрим, что у такому N приписываем → проверяем получим ли такое R. Ответ должен совпасть с кандидатом.
 


Выполни алгоритм для N = 6. Найди R.


Решение с конца: работаем с разрядами
Ищем минимальное R > 81, которое действительно может получиться по алгоритму. Идём от границы вверх и проверяем возможные результаты по порядку.
Проверяем по возрастанию:
Проверяем результат Берём ближайший кандидат
Шаг 1 из 5
 

 

Решение текстом

Нужно найти минимальное значение R > 81. Удобно идти не от исходного числа N, а от возможных результатов: 82, 83, 84, 85, 86, …

82 = 1010010₂. Убираем последние два разряда 10 и получаем 10100₂ = 20. Но 20 — чётное, поэтому алгоритм должен дописать 01. Получилось бы 81, а не 82. Значит, 82 невозможно.

У числа 83 = 1010011₂ хвост 11, а у 84 = 1010100₂ хвост 00. Алгоритм таких хвостов не создаёт: возможны только 01 и 10.

Для 85 = 1010101₂ после удаления хвоста 01 получаем 10101₂ = 21. Но 21 нечётное, поэтому к нему должен быть дописан хвост 10. Значит, из 21 получится 86, а не 85.

Наконец, 86 = 1010110₂. Удаляем хвост 10 и получаем N = 21. Число 21 нечётное, поэтому алгоритм действительно дописывает 10.

10101 → 1010110₂ = 86

Числа 82, 83, 84 и 85 получить нельзя, а 86 получить можно. Следовательно, минимальное значение R равно 86.


Как ускорить — необязательно

Если формулы не пугают: два дописанных бита сдвигают N на два разряда. Поэтому для чётного N получаем R = 4N + 1, для нечётного — R = 4N + 2. Это быстро приводит к кандидатам 89 и 86; выбираем 86.


Программное решение

Программа перебирает возможные значения N и выбирает наименьший R > 81. Проверяем N до 99: уже при N ≥ 100 приписывание двух битов даёт R ≥ 400, что больше найденного 86. 
Если не уверены в верхней границе N, то перебирайте до 1000, 2000  и т.д. Увидите, что ответ не меняется при изменнении верхней границы, значит ответ нашли.



Вывод программы
86

Совпало с разбором.


Алгоритм выдал R = 158. Восстанови N.


Не потеряй балл
  • Не забудь проверить чётность N после удаления хвоста.
  • Не включай 81: требуется строго больше.

     

Обсуждения (0)
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Решения (0)

Решения:

Нет доступных решений