Задание 6. Тип заданий 6: алгоритмы.
  • Задание:

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

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

       2. К этой записи дописываются справа ещё два разряда по следующему правилу:

          а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

          б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

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

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

  • Решение:

    Обратите внимание, нужно найти наименьшее число N, то есть исходное число, для которого R будет больше 31.

    Переведем 31 в двоичную систему счисления:

    3110 = 111112

    111112 — максимально возможное пятизначное двоичное число, нам нужно, чтобы результат был больше него, значит результат должен быть как минимум шестизначным числом. Наименьшее двоичное шестизначное число — 1000002.

    Алгоритм добавляет к исходному числу два разряда, значит число R на два разряда больше числа N. Отсечём от числа 1000002 два последних разряда:

    1000

    В принципе, уже понятно, что 10002 — подходящее число N, но давайте проверим на нем работу алгоритма.

     

    Алгоритм складывает разряды исходного числа, и остаток от деления на 2 этой суммы дописывает в конец. Сумма разрядов числа 1000 — 1, остаток от деления на 2 равен 1, значит к 1000 справа добавится единица:

    10001

    Теперь алгоритм снова складывает разряды, и остаток от деления на 2 дописывает справа. Сумма разрядов равна 2, остаток от деления на 2 равен 0, справа добавляется ноль:

    100010

    То есть исходное число 10002 алгоритм преобразует в число 1000102, и 1000102 — наименьший возможный результат работы алгоритма, который больше числа 31.

    Но по заданию мы должны определить N, исходное число. Результат мы получили из числа 10002, то есть 810

    Ответ: 8

Поделиться:
 
Комментарии (0)

Нет комментариев. Ваш будет первым!

Перевести число из в Результат: 510 = 1012