Разбор 20 задания егэ по информатике 2018

Задание 20. Программирование: циклы и ветвления: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018

*** КАНАЛ ЮТЬЮБ ***

ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 20

20 задание демоверсия ЕГЭ 2018 информатика:

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M.

Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7.

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.

📹 Видеоразбор 1
📹 Видеоразбор 2

✍ Показать решение:

✎ Способ 1:

В цикле:

Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.
В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов.
Условие if x mod 2 <> 0 проверяет на нечетность младший разряд числа в двоичной системе:

например, если было D = 5₁₀ = 101₂, 
то if x mod 2 <> 0 проверяет if 1 <> 0

Если в младшем разряде стоит единица (в двоичной системе число состоит только из 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.
В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, D = 5₁₀ = 101₂, то стало D = 10₂

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

1001111₂ = 64 + 8 + 4 + 2 + 1 = 79₁₀

✎ Способ 2 (длительный, аналитический):

Для начала рассмотрим алгоритм программы:

В начале программы вводится x, и обнуляются две переменные — L и M.
Далее следует цикл, который зависит от переменной x: пока x > 0 выполняется тело цикла.
В теле цикла каждый его шаг происходит увеличение переменной M на единицу. Т.е. переменная M — это счетчик, соответственно, его значение по завершению работы цикла будет соответствовать количеству шагов (итераций) цикла.
В конце программы печатается сначала L, потом M. Т.е. L должно быть равно 5, а M = 7. Раз M будет равно 7, то из предыдущего пункта видим, что цикл имеет 7 шагов, т.е. 7 итераций.
L — это тоже счетчик, но из условия if x mod 2 <> 0 видим, что счетчик L подсчитывает количество нечетных промежуточных x. Т.е. x в цикле постоянно меняется, а L проверяет x и в случае нечетного значения увеличивается на единицу. В программе L должно стать 5.
В цикле x делится целочисленно на 2: x := x div 2
Поскольку цикл завершит работу, когда x = 0, то последним шагом будет x = 1 div 2 = 0. Т.е. в предпоследнем шаге x = 1.
Решим данную задачу с конца, проследив все итерации цикла. Получается, что из предыдущего шага в следующий шаг x изменяется по двум правилам, назовем их командами:

1. x*2 -> если предыдущий x - четный, 
например 4 div 2 - обратное действие 2*2 = 4

2. x*2+1 -> если предыдущий x - нечетный, 
например 5 div 2 - обратное действие 2*2+1 = 5

Так как L в результате равно 5, значит, в программе 5 команд № 2 и 2 команды №1 (7-5 = 2)
Нарисуем дерево команд и получающиеся значения, начиная с последней итерации цикла до начальной итерации. Т.е. начнем с завершения цикла, когда x стал = 0:

Вниз уходят команды, дающие четные значения x, а вверх — нечетные. Поскольку нам необходимо найти наименьший x, то «выгоднее» проследить нижние ветви дерева, т.к. они в результате дают меньшие значения.
Из дерева видим, что первая команда — это команда 2. В итоге осталось 4 команды № 2 и 2 команды № 1.
Нам выгодно с самого начала «двигаться» по дереву, используя команды №1 (чтобы x был наименьшим). Поэтому вторая и третья ветвь будут соответствовать команде №1. Поскольку первых команд должно быть только две, остальные команды будут №2.
Итого получаем следующий путь по дереву, в результате которого x становится равным 79.

Результат: 79

Решение 20 задания ЕГЭ по информатике, вариант 1 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», 10 вариантов, С.С. Крылов, Т.Е. Чуркина):

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число: S. Известно, что 100 <= x <=200.

Укажите наибольшее допустимое число x, при вводе которого алгоритм печатает 42.

var
  x, A, B, D, S: integer;
begin
  readln(x);
  B := x;
  A := 10;
  D := x;
  S := 0;
  while (D div 2) > 0 do
  begin
    if (D mod 2) = 1 then
      s := s + 1
    else
      s := s + A;
    D := D div 2;
  end;
  writeln(s);
end.

📹 Видеоразбор

✍ Показать решение:

В начале программы вводится x, две переменные — B и D присваивают значение введенного x. Переменной A присваивается значение 10, а переменная S обнуляется.
Далее следует цикл, который зависит от переменной D (равной x): пока x div 2 > 0 выполняется тело цикла. Т.е. пока x, деленный целочисленно на 2, больше нуля.
В теле цикла происходит увеличение переменной S либо на 10 (А:=10), либо на 1 в зависимости от четности значения D. Т.е. переменная S увеличивается на 10 в случае, если очередное значение D — нечетное и увеличивается на 1, если очередное значение D — четное.
В конце цикла D целочисленно делится на 2 (D := D div 2).
По условию программы S должно быть равно 42. Посчитаем максимальное количество итераций цикла:

2ⁿ <= 200, т.е. n = 7  
(максимальное значение D - 200 - делим целочисленно на 2, пока это возможно).
2ⁿ >=100, т.е. n = 6 
минимальное количество итераций - 6

За 7 или 6 итераций цикла необходимо получить S = 42, каждую итерацию цикла, увеличивая S либо на 1, либо на 10. Рассмотрим варианты:

42 = 10 + 10 + 10 + 12*1 (получаем 15 итераций, что не соответствует действительности)
42 = 10 + 10 + 10 + 10 + 2*1 получаем 6 итераций - подходит!

Из 6 итераций имеем: 2 итерации с D — нечетным (когда s = s + 1) и 4 итерации с D — четным (когда s = s + 10)
Четность чисел в двоичной системе счисления зависит от младшего бита: если младший бит = 0, то число четное, если 1, то число нечетное. Поскольку нам необходимо найти наибольшее x, то необходимо в двух старших битах числа, выраженного в двоичной системе счисления, поместить 1, а в остальных четырех битах разместить 0. При этом необходимо не забыть про еще один старший бит равный 1 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла):

1110000₂ = 112₁₀
первая единица будет стоять всегда, она не участвует в итерациях цикла

Проверка:
112| 0  - соответствует s + 10
 56| 0  - соответствует s + 10
 28| 0  - соответствует s + 10
 14| 0  - соответствует s + 10
  7| 1  - соответствует s + 1
  3| 1  - соответствует s + 1
  1|

Результат: 112

Разбор 20 задания ЕГЭ по информатике, вариант 2 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», 10 вариантов, С.С. Крылов, Т.Е. Чуркина):

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число S. Известно, что 100 <= x <=200.

Укажите наименьшее допустимое число x, при вводе которого алгоритм печатает 57.

var
  x, A, B, D, S: integer;
begin
  readln(x);
  B := x;
  A := 11;
  D := x;
  S := 0;
  while (D div 2) > 0 do
  begin
    if (D mod 2) = 1 then
      s := s + 1
    else
      s := s + A;
    D := D div 2;
  end;
  writeln(s);
end.

✍ Показать решение:

В начале программы вводится x, две переменные — B и D присваивают значение введенного x. Переменной A присваивается значение 11, а переменная S обнуляется.
Далее следует цикл, который зависит от переменной D (равной x): пока x div 2 > 0 выполняется тело цикла.
В теле цикла происходит увеличение переменной S либо на 11 (т.к. А:=11), либо на 1 в зависимости от четности значения D. Т.е. переменная S увеличивается на 11 в случае, если очередное значение D — нечетное и увеличивается на 1, если очередное значение D — четное.
В конце цикла D целочисленно делится на 2 (D := D div 2).
По условию программы S должно быть равно 57. Посчитаем максимальное количество итераций цикла:

2ⁿ <= 200, т.е. n = 7  
(максимальное значение D - 200 - делим целочисленно на 2, пока это возможно). 
2ⁿ >=100, т.е. n = 6
минимальное количество итераций -> 6

За 7 или 6 итераций цикла необходимо получить S = 57, каждую итерацию цикла, увеличивая S либо на 1, либо на 10. Рассмотрим варианты:

57 = 11 + 11 + 11 + 11 + 11 + 1 + 1 (получаем 7 итераций)

Из 7 итераций имеем:

2 итерации с D - нечетным (когда s = s + 1) 
5 итераций с D - четным (когда s = s + 11)

Четность чисел в двоичной системе счисления зависит от младшего бита: если младший бит = 0, то число четное, если 1, то число нечетное. Поскольку нам необходимо найти наименьшее x, то необходимо в пяти старших битах данного числа, выраженного в двоичной системе счисления, поместить 0, а в остальных двух битах разместить 1. При этом необходимо не забыть про еще один старший бит равный 1 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла):

10000011₂ = 131₁₀
первая единица будет стоять всегда, она не участвует в итерациях цикла

Проверим:
131| 1  - соответствует s + 1
 65| 1  - соответствует s + 1
 32| 0  - соответствует s + 11
 16| 0  - соответствует s + 11
  8| 0  - соответствует s + 11
  4| 0  - соответствует s + 11
  2| 0  - соответствует s + 11
  1|

Результат: 131

Решение 20 задания ЕГЭ по информатике (контрольный вариант №1 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков «Тренадер ЕГЭ информатика»):

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M.

Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 4, а потом 8.

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 
  begin	
    L:= L + 1;
  End;
  x := x div 2;
end;
writeln(L);
writeln(M);
end.

📹 Видеоразбор

✍ Показать решение:

Результат: 135

ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 20