Выполнение и анализ простых алгоритмов
 Скачать 190.3 Kb.
|
Ещё пример задания:Р-08. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 137. В ответе это число запишите в десятичной системе. Решение: фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль если в конце двоичной записи числа стоит 0, значит, оно чётное; поэтому мы в результате работы алгоритма должно обязательно получиться чётное число по условию, мы должны получить чётное число, большее 137; числа-кандидаты – 138, 140, 142, 144, … проверяем число 138: после выполнения шага 2б оно увеличилось вдвое (приписали 0), поэтому до выполнения этого шага у нас было число 138 : 2 = 69 = 10001012; в этом двоичном коде нечётное число единиц (3), поэтому оно не подходит по условию (после шага 2а количество единиц должно стать чётным, так как мы добавили бит чётности) проверяем следующее число-кандидат: 140 : 2 = 70 = 10001102, тут тоже 3 единицы, оно тоже не подходит следующее чётное число, 142, при делении на 2 даёт число 71 = 10001112, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма; на этом шаге к нему был добавлен бит чётности, выделенный жёлтым фоном убираем последний бит числа 71 (бит чётности), получаем 35 = 1000112 Ответ: 35. Ещё пример задания:Р-07. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе. Решение: фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль если в конце двоичной записи числа стоит 0, значит, оно чётное минимальное чётное число, которое превышает 43, это 44, но число, полученное из 44 отбрасыванием последнего нуля в двоичной записи (то есть, делением на 2!), 22 = 101102, содержит нечётное число единиц, что не допускается по условию – после шага «а» число единиц двоичной записи должно быть чётным следующее чётное число, 46, при делении на 2 даёт число 23 = 101112, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма. Ответ: 46. Решение (Р.Р. Нугуманов, г. Альметьевск): Минимальное чётное число, которое превышает 43, это 44, в двоичной системе счисления оно выглядит как 1011002. В результате работы автомата такое число не может быть получено, потому что содержит нечётное число единиц. Два последних разряда добавляются в результате работы алгоритма. Значит число N, которое было на входе – это 1011002 без двух последних нулей, то есть 10112. Применяем алгоритм к двоичному числу 10112: а) 10112 – остаток от деления количества единиц на 2 равен 1, дописываем единицу – 101112; б) 101112 – остаток от деления количества единиц на 2 равен 0, дописываем ноль – 1011102. Переводим в десятичную систему счисления двоичное число 1011102, полученное в результате работы автомата: 1011102 = 46. Ответ: 46. |