Задание 5
(до 2021 года задание 6)
(до 2021 года задание 6)
В этом задании первая ваша задача - понять что же от вас требуется. Если углубляться, то необходимо понять какие R могли получится, а какие нет.
Пример задания
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ешё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конеu числа ( справа). Например, запись 11001 преобразуется в запись 110011;
6) над этой записью производятся те же действия: справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите максимальное число R, которое не превышает числа 57 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.
Итак, план действий:
Как я уже говорила, в начале надо понять, как работает алгоритм. Для этого берем любое двузначное число и прогоняем по алгоритму:
1) Например, N=35 и двоичное N=10011
2) добавляем два разряда 10011
а)сумма равна 3, добавляем 1 - 100111,
б) теперь у нас число 10111 сумма равна 4, остаток - 0, получаем 1001110
Ваша задача понять, какие варианты образования двух последних разрядов.
У нас только 2 варианта - 00 (если у N сумма была четной) и 10. Это мы будем учитывать при проверке R
Анализируем наше задание. Переводим число R (результат работы алгоритма) в двоичную. Так как К не превышает 57 берем сразу 56 и переводим в двоичную:
111000
находим исходное число N для нашего R (это К без учета двух последних разрядов)
N =1110
Идем по алгоритму: проверяем, могло ли такое число получится в результате работы алгоритма. Если не могло, то к N прибавляем или убавляем 1 (если в задании фраза "не превышает числа", то убавляем на 1, если "превышает число...", то прибавляем 1) и строим R уже для нового N. Иначе, оставляем ответ.
Итак, проверяем:
Для N=1110 будет R=111010
Значит 56 получиться не могло.
Кроме того, наше R =111010 превышает R из задания 111000.
Понижаем N 1110-1=1101
И для этого N ищем R
110110
Это и есть наш ответ, надо только перевести в десятичную - 54
Ответ 54.