Задание 20 ЕГЭ по информатике 2018

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

*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 20
 

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 = 510 = 1012, 
    то if x mod 2 <> 0 проверяет if 1 <> 0
    
  • Если в младшем разряде стоит единица (в двоичной системе число состоит только из 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.
  • В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:
  • если было, например, D = 510 = 1012, то стало D = 102
    
  • Таким образом, счетчик L подсчитывает количество единиц в двоичной записи числа. Так как в результате выводится L = 5, то в двоичной записи числа 5 единиц.
  • Так как цикл работает 7 раз и в каждую итерацию от числа в двоичной записи отсекается один разряд, то имеем 7 разрядов (цифр) в числе.
  • Итого, в двоичной записи 5 единиц и 2 нуля. Для получения наименьшего x (по заданию) расположим цифры следующим образом:
  • 10011112 = 64 + 8 + 4 + 2 + 1 = 7910
    

  
✎ Способ 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:
  • 18 задание егэ информатика демоверсия 2018 решение

  • Вниз уходят команды, дающие четные значения 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. Посчитаем максимальное количество итераций цикла:
  • 2n <= 200, т.е. n = 7  
    (максимальное значение D - 200 - делим целочисленно на 2, пока это возможно).
    2n >=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 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла):
  • 11100002 = 11210
    первая единица будет стоять всегда, она не участвует в итерациях цикла
    
    Проверка:
    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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. Посчитаем максимальное количество итераций цикла:
  • 2n <= 200, т.е. n = 7  
    (максимальное значение D - 200 - делим целочисленно на 2, пока это возможно). 
    2n >=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 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла):
  • 100000112 = 13110
    первая единица будет стоять всегда, она не участвует в итерациях цикла
    
    Проверим:
    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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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