Решение задания 20. Демо ЕГЭ по информатике 2020.


Решение ГИА в форме ЕГЭ по информатике 20 задание из демоверсии 2020 года.

Задание на анализ алгоритма, содержащего цикл и ветвление.

ЕГЭ по информатике 2020 задание 20 1
ЕГЭ по информатике 2020 задание 20 1
ЕГЭ по информатике 2020 задание 20 2
ЕГЭ по информатике 2020 задание 20 2
var
  x, L, M: integer;
begin
  readln(x);
  L := 0;
  M := 0;
  while x > 0 do
  begin
    M := M + 1;
    if x mod 2 = 0 then
      L := L + 1;
    x := x div 2;
  end;
  writeln(L);
  writeln(M);
end.

Рассмотрим алгоритм:

В цикле:

Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.

В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов цикла (в конце выводится M — по условию задания — число 7).

Условие if x mod 2 = 0 проверяет на четность младший разряд числа в двоичной системе:

например, если было x = 510 = 1012, 
то if x mod 2 = 0 проверяет if 1 = 0

Если в младшем разряде стоит ноль (в двоичной системе число состоит только из чисел 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.

В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, x = 510 = 1012, то стало x = 102

Таким образом, счетчик L подсчитывает количество нулей в двоичной записи числа. Так как в результате выводится L = 6, то в двоичной записи числа 6 нулей.

Так как цикл работает 7 раз и в каждую итерацию от числа в двоичной записи отсекается один разряд, то имеем 6 разрядов (цифр) в числе.

Итого, в двоичной записи 6 нулей и 1 единица. Для получения наименьшего x (по заданию) расположим цифры следующим образом:

10000002 = 64 + 0 + 0 + 0 + 0 + 0 + 0 = 6410

Ответ: 64