Главная страница

фигня. Выполнение и анализ простых алгоритмов


Скачать 0.66 Mb.
НазваниеВыполнение и анализ простых алгоритмов
Анкорфигня
Дата21.02.2022
Размер0.66 Mb.
Формат файлаdoc
Имя файлаege5.doc
ТипДокументы
#369032
страница4 из 12
1   2   3   4   5   6   7   8   9   ...   12

Ещё пример задания:


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

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

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

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

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

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

Решение:

  1. фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль

  2. если в конце двоичной записи числа стоит 0, значит, оно чётное; поэтому мы в результате работы алгоритма должно обязательно получиться чётное число

  3. по условию, мы должны получить чётное число, большее 137; числа-кандидаты – 138, 140, 142, 144, …

  4. проверяем число 138: после выполнения шага 2б оно увеличилось вдвое (приписали 0), поэтому до выполнения этого шага у нас было число 138 : 2 = 69 = 10001012; в этом двоичном коде нечётное число единиц (3), поэтому оно не подходит по условию (после шага 2а количество единиц должно стать чётным, так как мы добавили бит чётности)

  5. проверяем следующее число-кандидат: 140 : 2 = 70 = 10001102, тут тоже 3 единицы, оно тоже не подходит

  6. следующее чётное число, 142, при делении на 2 даёт число 71 = 10001112, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма; на этом шаге к нему был добавлен бит чётности, выделенный жёлтым фоном

  7. убираем последний бит числа 71 (бит чётности), получаем 35 = 1000112

  8. Ответ: 35.

Ещё пример задания:


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

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

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

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

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

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

Решение:

  1. фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль

  2. если в конце двоичной записи числа стоит 0, значит, оно чётное

  3. минимальное чётное число, которое превышает 43, это 44, но число, полученное из 44 отбрасыванием последнего нуля в двоичной записи (то есть, делением на 2!), 22 = 101102, содержит нечётное число единиц, что не допускается по условию – после шага «а» число единиц двоичной записи должно быть чётным

  4. следующее чётное число, 46, при делении на 2 даёт число 23 = 101112, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма.

  5. Ответ: 46.

Решение (Р.Р. Нугуманов, г. Альметьевск):

  1. Минимальное чётное число, которое превышает 43, это 44, в двоичной системе счисления оно выглядит как 1011002. В результате работы автомата такое число не может быть получено, потому что содержит нечётное число единиц.

  2. Два последних разряда добавляются в результате работы алгоритма. Значит число N, которое было на входе – это 1011002 без двух последних нулей, то есть 10112.

  3. Применяем алгоритм к двоичному числу 10112:

а) 10112 – остаток от деления количества единиц на 2 равен 1, дописываем единицу – 101112;

б) 101112 – остаток от деления количества единиц на 2 равен 0, дописываем ноль – 1011102.

  1. Переводим в десятичную систему счисления двоичное число 1011102, полученное в результате работы автомата: 1011102 = 46.

  2. Ответ: 46.
1   2   3   4   5   6   7   8   9   ...   12


написать администратору сайта