Информатика ЕГЭ 27 задание разбор

Разбор 27 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеет значения.

Максимальная оценка за правильную программу — 2 балла.

  
Задание Б (более сложное, чем А)
Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться на более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Например:
2  6
4  1
7  3
2  9
7  4
sum=231

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

Задание Б (алгоритм):

  • поскольку в задании указано, что «имеется набор данных, состоящих из пар…», то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:
  • n:longint; {количество пар чисел};
  • объявим сами числа типа integer, переменную цикла — i — типа integer и дополнительные переменные, смысл которых будет объяснен ниже. Объявление сделаем в отдельных строках (так делать не обязательно), чтобы можно было ввести удобно комментарии:
  •  x,y: integer; {пара чисел}
     max: integer; {максимальное из пары}
     min: integer; {минимальное из пары}
     sum:longint; {сумма квадратов отобранных чисел}
     min_kvadr:longint; {мин. нечетная разница квадратов max и min}
     i:integer;
  • так как в задании не оговаривается, что пары чисел считывается из файла, значит их необходимо считать со стандартного входного потока оператором readln(); т.е. организуем цикл:
  • for i:=1 to n do begin
      readln(x,y);
      ...

    Допустим имеем пары:

    2 6
    4 1
    7 3
    2 9
    7 4
    
  • Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:
  • 2 6
    4 1
    7 3
    2 9
    7 4
    
  • но сначала определим максимальное и минимальное число из каждой пары:
  • if x>y then 
    begin 
       max:=x; min:=y 
    end
    else 
    begin 
        max:=y;min:=x 
    end;
  • далее суммируем квадраты максимальных чисел:
  • sum:=sum+sqr(max);
  • поскольку, согласно заданию, сумма должна быть нечетной, то в случае, если сумма будет четной, нам необходимо выбрать пару, в которой разница между квадратами чисел минимальна и при этом нечетна и взять из этой пары не максимальный, а минимальный элемент. Или лучше просто вычислить разницу между квадратами максимума и минимума и затем вычесть ее из получившейся четной суммы. Выделим пару, разница между квадратами чисел которой минимальна и при этом нечетна:
  • 2 6 - разница 4
    4 1 - разница 3
    7 3 - разница 4
    2 9 - разница 7
    7 4 - разница 3
    
  • поиск минимальной и нечетной разницы между квадратами чисел в паре:
  • if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
        min_kvadr:=sqr(max) - sqr(min)
  • для переменной, обозначающей разницу, до цикла необходимо назначить максимально возможное значение:
  • min_kvadr:=1073676289;  {32 767 * 32 767 (самое большое в типе integer) }
  • таким образом, в цикле у нас происходит:
  • 1. поиск максимального и минимального числа из пары;
  • 2. вычисляется сумма максимальных чисел из каждой пары;
  • 3. находится минимальная разница квадратов максимального и минимального числа в парах.
  • после цикла необходимо проверить сумму на нечетность. Если сумма четная (чего НЕ должно быть по условию), то отнимем от суммы вычисленную минимальную разницу. Но при этом учтем, что если не нашлось нечетной минимальной разницы, то выводим 0 (по условию):
  • if sum mod 2 = 0 then begin
      if min_kvadr > 10000 then sum := 0
      else sum:=sum - min_kvadr
    end;

  
Эффективная программа (решение):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var
 n:longint; {количество пар чисел}
 x,y: integer; {пара чисел}
 max: integer; {максимальное из пары}
 min: integer; {минимальное из пары}
 sum:longint; {сумма квадратов отобранных чисел}
 min_kvadr:longint; {мин. нечетная разница квадратов max и min}
 i:integer;
begin
sum:=0;
readln(n);
min_kvadr:=1073676289;  {32 767 * 32 767, самое большое integer}
for i:=1 to n do begin
  readln(x,y);
  if x>y then begin max:=x; min:=y end
  else begin max:=y;min:=x end;
  sum:=sum+sqr(max);
  if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
    min_kvadr:=sqr(max) - sqr(min)
end;
if sum mod 2 = 0 then begin
  if min_kvadr > 10000 then sum := 0
  else sum:=sum - min_kvadr
end;
writeln('sum=',sum)
end.

Пример работы программы:

3
1 4
2 4
3 4
sum=41

📹 Видео


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

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

  
А. Имеется набор данных, состоящий из 5 тройке положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу — 2 балла.

Б. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Постарайтесь сделать программу эффективной по времени и по используемой памяти.

Программа считается эффективной по времени, если время работы программы пропорционально количеству чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Напоминаем! не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию.

Входные данные
Для варианта А на вход программе подается 5 строк, каждая из которых содержит три натуральных числа, не превышающих 10000.
 
Пример входных данных для варианта А:

1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

Для варианта Б на вход программе в первой строке подается количество троек чисел N (1<=N<=100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.   Пример входных данных для варианта Б:

5
1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

Пример выходных данных для приведенных выше примеров входных данных:
6

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

Задание Б

Чтобы получить минимально возможную сумму, будем брать из каждой тройки наименьшее число. Если полученная при этом сумма будет кратна 5, ее придется увеличить. Для этого достаточно в одной из троек, где хотя бы два числа имеют разные остатки при делении на 5, заменить ранее выбранное число на число с другим остатком от деления на 5 из той же тройки. При этом модуль разности между прежним и новым, выбранным из тройки, должен быть минимально возможным.

 
Пример правильной и эффективной программы для задания Б на языке Паскаль:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const
  aMax = 10000;{наибольшее возможное исходное число}
 
var
  N: longint; {количество троек}
  a, b, c, tmp: longint;{тройка чисел}
  s: longint;{сумма выбранных чисел}
  D_min: longint;{мин. разница в тройке не кратная 5}
  i: longint;{}
 
begin
  s := 0;
  D_min := aMax + 1;
  readln(N);
  for i := 1 to N do 
  begin
    readln(a, b, c);
    if (a > b) then begin tmp := a;a := b;b := tmp end;
    if(b > c) then begin
      tmp := b;b := c;c := tmp;
      if (a > b) then begin tmp := a;a := b;b := tmp end
    end; {a,b,c отсортированы по возрастанию}
    s := s + a;
    if((b - a) mod 5 > 0 ) and ((b - a) < D_min) then D_min := b - a;
    if((c - a) mod 5 > 0 ) and ((c - a) < D_min) then D_min := c - a
  end;
  if s mod 5 = 0 then begin
    if D_min > aMax then s := 0
    else s := s + D_min
  end;
  writeln(s)
end.

Задание А

В цикле перебираются все возможные суммы, и среди них ищется удовлетворяющая условию.

Информатика ЕГЭ 26 задание разбор

Разбор 26 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 7 камней, за один ход можно получить кучу из 14 или 8 камней. У каждого игрока, чтобы сделать ход, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27.

Задание 1
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24? Опишите выигрышные стратегии для этих случаев.

Задание 2
У кого из игроков есть выигрышная стратегия при S = 13, 12? Опишите соответствующие выигрышные стратегии.

Задание 3
У кого из игроков есть выигрышная стратегия при S = 11? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.

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

  1. а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S = 27: тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22): тогда необходимо удвоить кучу.

    S=27
    Паша: 27 + 1 = 28 - Выигрыш!
    
    27 - выигрышная позиция
    

    б) При S = 26 выигрышная стратегия есть у Вали. Паша делает ход первым, у него есть возможность либо удвоить количество камней в куче, и тогда количество превысит 44, — выигрывает Валя; либо увеличить количество на один камень, станет 27 камней: следующая Валя, — она может положить один камень и выиграть.

    S=26
    Паша: 26 * 2 = 52   Валя выигрывает! или:
    Паша: 26 + 1 = 27
    Валя: 27 + 1 = 28 - Выигрыш! 
    
    26 - проигрышная позиция
    

    При S = 25 выигрышная стратегия есть у Паши. Удваивать количество камней нет смысла, т.к. количество превысит 44, значит, Паша добавит один камень, их станет 26, следующая Валя, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.

    S=25
    Паша: 25 + 1 = 26
    Валя: 26 ...  проигрышная позиция (см. выше) Паша выигрывает!
    
    25 - выигрышная позиция
    

    При S = 24 выигрышная стратегия есть у Вали. Паша делает ход первым: удваивать кучу нет смысла, т.к. в ней станет более 44, значит, Паша добавит один камень, их станет 25; следующая — Валя: она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной позиции, см. пункт при S = 26).

    S=24
    Паша: 24 + 1 = 25 
    Валя: 25 ...  выигрышная позиция (см. выше) Валя выигрывает!
     
    24 - проигрышная позиция
    
  2. При S = 13 или S = 12 выигрышная стратегия есть у Паши. Паша удваивает количество и в куче остается 26 или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
  3. При S = 11 выигрышная стратегия есть у Вали. Паша делает первый ход: в куче остается либо 22, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S = 12 последовательность игры описана в пункте 2, а при S = 22 — в пункте .

      
    Дерево возможных партий:
    задание 26 егэ дерево игры

    * Для Вали отображены только ходы по стратегии
    ** красный круг означает выигрыш
    *** фиолетовый круг — конец игры (проигрыш)

📹 Видео


Разбор 26 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

Петя и Ваня играют в игру: есть набор слов, необходимо последовательно называть буквы этих слов. Побеждает тот игрок, который называет последнюю букву любого слова из набора. Петя ходит первым.

Например, есть набор слов {Волк, Информатика, Страшно}; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя — В, Ваня — О, Петя — Л, Ваня — К).

  
Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ, НМЛКИНМЛКИ}. Определить выигрышную стратегию.

Б) Даны 2 слова {ТРИТРИТРИ…ТРИ, РИТАРИТАРИТАРИТА…РИТА}. В первом слове 99 букв, во втором 164. Определить выигрышную стратегию.

Задание 2
Необходимо поменять две буквы местами из набора пункта в слове с наименьшей длинной так, чтобы выигрышная стратегия была у другого игрока. Объяснить выигрышную стратегию.

Задание 3
Дан набор слов {Ворона, Волк, Волна, Производная, Прохор, Просо}. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий.

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

  1. А) Для выигрыша Пете достаточно выбрать первую букву слова с нечетным количеством букв, тогда последний ход делает Петя. При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что своим первым ходом он должен выбрать букву И (слово ИКЛМНИКЛМНХ из 11 букв). Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.

    Б) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, чтобы выбрать слово с нечетным количеством букв, т.к. при такой стратегии последнюю букву в любом случае записывает Петя. Т.о., Петя должен выбрать букву Т, т.к. в первом слове 99 букв.

  2. Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:
    {ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
    

    Для данного набора выигрышная стратегия есть у Вани. Петя в любом случае должен будет выбрать букву И, а Ваня следующим ходом может перевести игру в проигрышную позицию для Пети, т.е. перейти на второе слово, назвав букву М. Такая стратегия приведет Ваню к выигрышу, так как последнюю букву слова — И — запишет именно он.

  3. Выигрышная стратегия есть у Вани, так как при любом выборе Пети, Ваня может перевести игру в проигрышную позицию для Пети, т.е. «перейти» на слово с четным количеством букв. Такая стратегия позволит Ване написать последнюю букву и тем самым выиграть игру.
  4. Дерево возможных партий:
    дерево партий

* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш

📹 Видео


Решение 26. Демоверсия ЕГЭ 2018 информатика:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

Задание 1
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.

Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции

Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

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

    Задание 1.

  • а) Петя может выиграть, если S = 15, … 28
  • 15, ..., 28 - выигрышные позиции с первого хода
    
  • б) Ваня может выиграть первым ходом (как бы ни играл Петя), если в куче будет S = 14 камней. Тогда после первого хода Пети в куче будет 15 или 28 камней. В обоих случаях Ваня удваивает кучу и выигрывает в один ход.
  • S = 14
    Петя: 14 + 1 = 15  выигрышная позиция (см. п. а). Выигрывает Ваня
    Петя: 14 * 2 = 28   выигрышная позиция (см. п. а). Выигрывает Ваня
    
    14 - проигрышная позиция
    

    Задание 2.

  • Возможные значения S: 7, 13. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 14 камней: в первом случае удвоением, во втором — добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
  • S = 7
    Петя: 7 * 2 = 14  проигрышная позиция (см. п. 1 б). Выигрывает Петя
    S = 13
    Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя
    
    7, 13 - выигрышные позиции со второго хода
    

    Задание 3.

  • Возможные значения S: 12. После первого хода Пети в куче будет 13 или 24 камня. Если в куче их станет 24, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 13 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
  • S = 12
    Петя: 12 + 1 = 13  
    Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!
    

    В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчеркнуты. На рисунке это же дерево изображено в графическом виде.
    таблица выигрышных стратегий
    Дерево всех партий, возможных при стратегии Вани:
    дерево выигрышных стратегий
    * красный круг означает выигрыш


Досрочный егэ по информатике 2018, вариант 1. Задание 26:

Два игрока, Паша и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в пять раз. Игра завершается в тот момент, когда количество камней в куче становится не менее 69.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 69 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 68.

Задание 1.
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
  
б)Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Вася может выиграть своим первым ходом. Опишите выигрышную стратегию Васи.
  
Задание 2. Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.
 
Задание 3. Укажите хотя бы одно значение S, при котором у Васи есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, и у Васи нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Васи. Постройте дерево всех партий, возможных при этой выигрышной стратегии Васи (в виде рисунка или таблицы).

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

    1.
    а) S ≥ 14. При количестве камней в куче от 14 и выше Паше необходимо увеличить их количество в пять раз, тем самым получив 70 или более камней.

    S ≥ 14 выигрышные позиции
    

     
    б) S = 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.

    S = 13 
    Паша 1 ход: 13 + 1 = 14
    Паша 1 ход: 13 + 4 = 17
    Паша 1 ход: 13 * 5 = 65
    
    Ваня 1 ход: [14, 17, 65] * 5 = S ≥ 14  Ваня выигрывает
    
    13 - проигрышная позиция
    

    2. S = 9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
    После чего игра сводится к стратегии, описанной в пункте .

    S = 13 
    Паша 1 ход: 9 + 4 = 13  Паша выигрывает
    Паша 1 ход: 12 + 1 = 13 Паша выигрывает
    
    9, 12 - выигрышные позиции со второго хода
    

    3. S = 8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
    Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.

    S = 8 
    Паша 1 ход: 8 + 1 = 9   Ваня Выигрывает (см. п.2)
    Паша 1 ход: 8 + 4 = 12  Ваня Выигрывает (см. п.2)
    Паша 1 ход: 8 * 5 = 40  
    

    дерево решение 26 задание егэ

📹 Видео


Тренажер егэ по информатике 2018, контрольный вариант 1. Задание 26 (Крылов С., Ушаков Д.):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
 
Задание 1.
Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
  
Задание 2.
Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.
  
Задание 3.
Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

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

  • Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани.
  • Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
  • Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани.
  • дерево выигрышной стратегии

📹 Видео


Информатика ЕГЭ 25 задание разбор

Разбор 25 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество элементов массива НЕ кратных 3.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.

1
2
3
4
5
6
7
8
const N = 20;
var i,j,k:integer;
a:array [1..N] of integer; 
begin
for i:=1 to N do 
  readln(a[i]);end.

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

Рассмотрим заданный фрагмент решения:

  • в цикле со счетчиком i запрашиваются значения элементов массива, т.е. формируется массив;
  • из постановки задания видим, что необходимо найти количество чего-то, это значит, что нужно использовать переменную счетчик;
  • объявлены три целочисленных переменных: i, j, k; переменная i использована в первом цикле, значит для счетчика можно взять переменную k;
  • счетчик всегда нужно обнулять, поэтому следующим оператором будет:
  • k:=0;
  • определим, количество чего нам необходимо считать: количество элементов массива не кратных 3. Кратность можно определить через остаток от деления: если значение элемента массива при делении на 3 в остатке не возвращает 0, значит элемент не кратен трем;
  • остаток при делении в паскале — оператор mod. Поскольку необходимо просмотреть каждый элемент массива, то это нужно делать в цикле for;
  • переменная i уже использована в первом цикле for, значит, для очередного цикла возьмем неиспользованную переменную j:
  • for j:=1 to N do
      if a[j] mod 3 <> 0 then
  • если условие истинно (т.е. нашелся элемент массива, не кратный трем), то увеличиваем счетчик:
  •      inc(k);
  • после цикла остается вывести значение счетчика, т.е. вывести количество элементов массива не кратных 3:
  • writeln(k);

Результат:

k:=0;
for j:=1 to N do
  if a[j] mod 3 <> 0 then
    inc(k);
writeln(k);

📹 Видео


Разбор 25 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество троек элементов массива, состоящих из равных между собой чисел. В данной задаче под тройкой подразумевается три подряд идущих элемента массива.

Например, для массива из семи элементов: 2; 2; 2; 4; 4; 4; 4 — ответ: 3.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

1
2
3
4
5
6
7
8
9
10
const
  N=40;
var
  a: array[1..N] of integer;
  i, j, k:integer;
begin
  for i:=1 to N do
    readln(a[i]);
  ...
end.

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

  • из постановки задания видим, что необходимо искать количество чего-то, это значит, что нужно использовать переменную счетчик; возьмем для нее объявленную переменную k;
  • счетчик всегда нужно сначала обнулять, поэтому следующим оператором будет:
  • k:=0;
  • определим, количество чего нам необходимо считать: количество троек элементов массива, состоящих из равных между собой чисел. Т.е. необходимо сравнивать между собой каждые три подряд идущих элемента массива, например так:
  • if (a[i]=a[i+1]) and (a[i]=a[i+2]) then
        inc(k);
  • inc(k) — оператор, увеличивающий счетчик k на единицу;
  • условие необходимо выполнять в цикле, так как нужно проверить все элементы массива; цикл со счетчиком необходимо организовать от 1 до N-2, в противном случае индексы элементов a[i+2] выйдут за границы диапазона массива (например, при i = 40, получим … a[40+2], а 42-го элемента массива не существует, поэтому цикл надо делать до i = 38, т.е. N-2).

Результат:

for i:=1 to N-2 do
    if (a[i]=a[i+1]) and (a[i]=a[i+2]) then
      inc(k);
writeln(k);

📹 Видео


Решение 25 задания ЕГЭ по информатике Демоверсия 2018:

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на одном из языков программирования алгоритм, который находит количество элементов массива, больших 100 и при этом кратных 5, а затем заменяет каждый такой элемент на число, равное найденному количеству. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести измененный массив, каждый элемент массива выводится с новой строчки.

Например, для массива из шести элементов: 4 115 7 195 25 106
программа должна вывести числа 4 2 7 2 25 106

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

1
2
3
4
5
6
7
8
9
10
const
N = 30;
var
a: array [1..N] of longint;
i, j, k: longint;
begin
	for i := 1 to N do
		readln(a[i]);
	...
end.

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.

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

  • Решение на языке Паскаль:
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    
    k := 0;
    for i := 1 to N do
    	if (a[i] > 100) and (a[i] mod 5 = 0) then
    		k:=k+1;
    for i := 1 to N do begin
    	if (a[i] > 100) and (a[i] mod 5 = 0) then
    		a[i] := k;
    writeln(a[i])
    end

Информатика ЕГЭ 24 задание разбор

Разбор 24 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

Ученик написал программу, которая находит максимальную цифру заданного числа, кратную 6 (примечание: 0 кратен любому числу). Если таких чисел нет, то программа должна напечатать NO. Но его программа оказалась неверной.

1
2
3
4
5
6
7
8
9
10
11
12
13
var N,digit,maxDigit:integer;
begin 
readln(N);
maxDigit := N mod 10;
while N>0 do begin 
    digit:= N mod 10;
    if (digit > maxDigit) and (digit mod 6 = 0) then 
      maxDigit:=digit;
    N:=N div 10;
    end;
if maxDigit = 0 then writeln('NO')
else writeln(maxDigit);
end.

Последовательно выполните следующее:

  1. Напишите, что выведет эта программа при вводе числа 143.
  2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.
  3. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой сделана ошибка и укажите, как исправить ошибку, т.е. приведите правильный вариант строки.

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

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

  • Алгоритм предназначен для поиска максимальной цифры числа, кратной 6.
  • Переменная maxDigit предусмотрена для хранения максимальной цифры. Изначально ей в программе присвоена крайняя справа цифра (разряд единиц) — maxDigit := N mod 10;. Т.е. остаток при делении числа на 10 — это и есть крайняя справа цифра.
  • В цикле пока N > 0:
  • от N «отсекается» каждая цифра справа и сохраняется в переменную digit;
  • осуществляется проверка: если «отсеченная» цифра больше максимальной (digit > maxDigit) и кратна 6 (digit mod 6 = 0), то устанавливаем ее максимальной (maxDigit:=digit;);
  • сохраняем N без «отсеченной» цифры (N:=N div 10; , т.е. целочисленно делим на 10, таким образом отсекая цифру справа).
  • После цикла осуществляется проверка: если максимальным числом был 0, то выводим слово NO, иначе выводим максимальное число.

Решение заданий:

  1. При вводе 143 на экран выведется цифра 3.
  2. 🔔Дальнейшее объяснение НЕ нужно писать на экзамене:

    • В четвертой строке программы в maxDigit сохранится крайняя справа цифра числа, т.е. 3.
    • В цикле в условном операторе (строка 7) больше не найдется ни одной цифры, удовлетворяющей условию, т.е. ни 4, ни 1 не будут кратными 6.
    • В результате программа выведет значение maxDigit, т.е. цифру 3.
    • Рассмотрим подробно каждый шаг:

      maxDigit := 3;
      1 шаг:
      while 143>0 do begin 
          digit:= 3;
          if (3 > 3)and (3 mod 6 = 0) then условие ложно
            maxDigit:=digit; - не выполняется
          N:=14;
      end;
      
      2 шаг:
      while 14>0 do begin 
          digit:= 4;
          if (4 > 3)and (4 mod 6 = 0) then условие ложно
            maxDigit:=digit; - не выполняется
          N:=1;
      end;
      🔕
      3 шаг:
      while 1>0 do begin 
          digit:= 1;
          if (1 > 3)and (1 mod 6 = 0) then условие ложно
            maxDigit:=digit; - не выполняется
          N:=0;
      end;
      
      4 шаг:
      while 0>0 do begin  условие ложно
      ...
      end;
      if maxDigit = 0 then условие ложно
         writeln('NO') - не выполняется
      else writeln(maxDigit); - вывод числа 3
      

    🔕

  3. При вводе любого числа, крайней справа цифрой которого является цифра 6, а остальные цифры будут меньше либо равны ей, программа выдаст правильный результат. Например, ввод 126 вернет верный результат.
  4. 🔔Дальнейшее объяснение НЕ нужно писать на экзамене:

    в maxDigit сохранится цифра 6, которая максимальна в числе и кратна 6.
    🔕

  5. 1) неверная инициализация переменной maxDigit:
    ошибочная строка: maxDigit := N mod 10; (№ 4)
    исправление: maxDigit := -1;
    🔔Дальнейшее объяснение НЕ нужно писать на экзамене:
    Изначально максимальным необходимо назначить наименьшую возможную цифру, которая не кратна 6 (0 кратен любому числу, поэтому -1)
    🔕
    2) неверное условие:
    ошибочная строка: if maxDigit = 0 then (№ 11)
    исправление: if maxDigit = -1 then
    🔔Дальнейшее объяснение НЕ нужно писать на экзамене:
    Вытекает из предыдущего пункта
    🔕

📹 Видео


Разбор 24 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Дано натуральное число N, не превосходящее 1000. Необходимо определить, существует ли такое натуральное число M, что N можно представить в виде произведения (M-1)(M+1). Если это возможно, то следует напечатать число M, в противном случае вывести сообщение, что такого числа не существует.
Для решения этой задачи ученик написал программу, но, к сожалению, его программа оказалась неверной.

1
2
3
4
5
6
7
8
9
10
11
var n, m: integer; 
begin 
   read(n); 
   m:=2;
   while ((m-1)*(m+1) = n) and (m<n) do 
      m:=m+1;
   if m < n then
    writeln(n)
   else
    writeln('Не существует') 
end.

Последовательно выполните следующее:

  1. Напишите, что выведет эта программа при вводе числа 3.
  2. Приведите пример натурального числа, при вводе которого приведенная программа напечатает то, что требуется.
  3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

Достаточно указать ошибки и способ их исправления для одного языка программирования.

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

  1. Программа выведет ‘Не существует’
  2. 🔔Дальнейшее объяснение НЕ нужно писать на экзамене:

    n = 3;
    m = 2;
    
    1 шаг:
    while ((2-1)*(2+1) = 3) and (2<3) do условие истинно
      m:=2+1;
    
    2 шаг:
    while ((3-1)*(3+1) = 3) and (2<3) do условие ложно
      ...
    if 3 < 3 then  условие ложно
        writeln(n) не выполняется 
       else
        writeln('Не существует') выполняется
    end.
    

    🔕

  3. При вводе 2 (выведет на экран ‘Не существует‘)
  4. 1) ошибочное условие цикла:
    ошибочная строка: while ((m-1)*(m+1) = n)
    исправление: while ((m-1)*(m+1) <> n)
    2) ошибочный вывод:
    ошибочная строка: writeln(n)
    исправление: writeln(m)

📹 Видео


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

Дано натуральное число N, не превосходящее 10000. Требуется найти и напечатать минимальную четную цифру в десятичной записи числа N. Гарантируется, что в десятичной записи числа N есть хотя бы одна четная цифра.
Для решения этой задачи ученик написал программу, но, к сожалению, его программа оказалась неверной.

1
2
3
4
5
6
7
8
9
10
11
12
13
var
  n, mi, m: integer;
begin
  read(n);
  mi := n mod 10;
  while n > 0 do begin
    m := n mod 10;
    if (m < mi) and (m mod 2 = 0) 
    then mi := m;
    n = n div 10
  end;
  writeln(m)
end.

Последовательно выполните следующее:

  1. Напишите, что выведет эта программа при вводе числа 187.
  2. Приведите пример входного натурального числа, в десятичной записи которого есть хотя бы одна четная цифра, такого, что приведенная программа напечатает то, что требуется.
  3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Обратите внимание: Вам нужно исправить приведенную программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки.

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

  1. При вводе числа 187 программа выведет 1.
  2. Например, число 4.
  3. Программа содержит две ошибки:
  4. 1) неверная инициализация mi;
    2) неверная печать результата.
    Пример исправления для языка Паскаль:
      
    Первая ошибка:

    mi:=n mod 10;

    Исправленная строка:

    mi:=8;

    Комментарий для экспертов: В качестве начального значения подходит любое число, большее 8. Инициализация правой цифрой числа является неверной, поскольку она может быть нечетной. Так, например, даже при условии исправления ошибки вывода инициализация mi правой цифрой для числа 187 даст неверный результат (7 вместо 8).
     
    Вторая ошибка:

    writeln(m)

    Исправленная строка:

    writeln (mi)

Информатика ЕГЭ 23 задание разбор

Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x6, y1, y2, … y6, которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∨  y1)) ≡ (x2 ∨  y2)
(¬(x2 ∨  y2)) ≡ (x3 ∨  y3)

(¬(x5 ∨  y5)) ≡ (x6 ∨  y6)

Ответ: 54

Показать решение (с использованием метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:
  • ¬a ≡ b
    ¬b ≡ c
    ¬c ≡ d
    ¬d ≡ e
    ¬e ≡ f
    
  • Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:
  • a ≠ b
    b ≠ c
    c ≠ d
    d ≠ e
    e ≠ f
    
  • Вспомним, как выглядит таблица истинности для эквивалентности:
  • x1 x2 F
    0 0 1
    0 1 0
    1 0 0
    1 1 1
  • Рассмотрим, в каких случаях выражения будут возвращать ложь. Каждое из пяти выражений будет ложно, когда: либо оба операнда истинны, либо оба операнда ложны (операция равносильность = истине: при 00 или 11).
  • Составим битовую маску для наших уравнений. В цепочке значений от a до f не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна (к примеру, a ≠ b, если 0 ≠ 0 — это ложь). Таким образом, для данных уравнений существует всего две цепочки решений:
  •   цеп.1  цеп.2 
    a   0      1
    b   1      0
    c   0      1
    d   1      0
    e   0      1
    f   1      0
    
  • Теперь вспомним о заменах: каждая из переменных от a до f представляет собой скобку, внутри которой две переменные, связанные дизъюнкцией. Дизъюнкция двух переменных истинна в трех случаях (01, 10, 11), а ложна — в одном (00). Т.е., к примеру:
  • x1 ∨ y1 = 1 тогда, когда: либо 0 ∨ 1, либо 1 ∨ 0, либо 1 ∨ 1
     
    x1 ∨ y1 = 0 тогда и только тогда, когда 0 ∨ 0
    
  • Это говорит о том, что на каждую единицу в цепочке приходится три варианта значений, а на каждый нольодин. Т.о. получаем:
  • для первой цепочки: 33 * 13 = 27 наборов значений,
  • и для второй: 33 * 13 = 27 наборов значений
  • Итого наборов:
  • 27 * 2 = 54
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x9, y1, y2, … y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∧  y1)) ≡ (x2 ∧  y2)
(¬(x2 ∧  y2)) ≡ (x3 ∧  y3)

(¬(x8 ∧  y8)) ≡ (x9 ∧  y9)

В качестве ответа Вам нужно указать количество таких наборов.


Ответ: 324

Показать решение (использование метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:
  • ¬a ≡ b
    ¬b ≡ c
    ¬c ≡ d
    ¬d ≡ e
    ¬e ≡ f
    ¬f ≡ g
    ¬g ≡ h
    ¬h ≡ i
    
  • Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:
  • a ≠ b
    b ≠ c
    c ≠ d
    d ≠ e
    e ≠ f
    f ≠ g
    g ≠ h
    h ≠ i
    
  • Вспомним таблицу истинности для эквивалентности:
  • x1 x2 F
    0 0 1
    0 1 0
    1 0 0
    1 1 1
  • Теперь рассмотрим, в каких случаях полученные условия будут возвращать ложь. Каждое из условий будет ложно, если либо оба операнда истинны, либо оба операнда ложны:
    например 
    a ≠ b = 0, если: a=0 и b=0 или a=1 и b=1
    

    Это означает, что для одного условия не может быть такого случая, что a=0 и b=0 или a=1 и b=1.

  • Составим битовую маску для условий. В цепочке значений от a до i не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна. Таким образом, для данных условий существует всего две цепочки решений:
  •   цеп.1  цеп.2  цеп. цеп.
    a   0      1     0    1
    b   1      0     0    1   не может быть! 
    c   0      1    ...  ...
    d   1      0
    e   0      1
    f   1      0
    g   0      1
    h   1      0
    i   0      1
    
  • Теперь вспомним, что каждая из переменных от a до i представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех. Т.е., к примеру:
  • x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1, либо 1 ∧ 0, либо 0 ∧ 0
     
    x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1
    
  • Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1один. Т.о. получаем:
  • для первой цепочки: 35 * 14 = 243 набора значений,
  • и для второй: 34 * 15 = 81 набор значений
  • Итого наборов:
  • 243 + 81 = 324
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧  y1) ≡ (x3 ∧  y3)) → (x2 ∧  y2))
¬(((x2 ∧  y2) ≡ (x4 ∧  y4)) → ¬(x3 ∧  y3))
¬(((x3 ∧  y3) ≡ (x5 ∧  y5)) → (x4 ∧  y4))
¬(((x4 ∧  y4) ≡ (x6 ∧  y6)) → ¬(x5 ∧  y5))
¬(((x5 ∧  y5) ≡ (x7 ∧  y7)) → (x6 ∧  y6))
¬(((x6 ∧  y6) ≡ (x8 ∧  y8)) → ¬(x7 ∧  y7))

В качестве ответа Вам нужно указать количество таких наборов.

Ответ: 81

Показать решение (с использованием метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и скобки повторяются в разных уравнениях, то введем обозначения. Обозначим латинскими буквами в алфавитном порядке скобки с переменными согласно их номерам:
  • 1-a
    2-b
    3-c
    4-d
    5-e
    6-f
    7-g
    8-h
    
  • После замены получим следующие выражения:
  • ¬((a ≡ c) → b)
    ¬((b ≡ d) → ¬c)
    ¬((c ≡ e) → d)
    ¬((d ≡ f) → ¬e)
    ¬((e ≡ g) → f)
    ¬((f ≡ h) → ¬g)
    
  • Используя законы алгебры логики, преобразуем одно из условий (первое). Потом по аналогии выполним преобразования для остальных условий:
    1. Избавимся от импликации:
    2. было:  ¬((a ≡ c) → b)
      стало: ¬(¬(a ≡ c) ∨ b)
      
    3. По закону Де Моргана избавимся от отрицания над общей внешней скобкой:
    4. было:  ¬(¬(a ≡ c) ∨ b)
      стало: (a ≡ c) ∧ ¬b
      
  • По аналогии преобразуем остальные условия, учитывая, что двойное отрицание просто аннулирует отрицание:
  • (a ≡ c) ∧ ¬b
    (b ≡ d) ∧ c
    (c ≡ e) ∧ ¬d
    (d ≡ f) ∧ e
    (e ≡ g) ∧ ¬f
    (f ≡ h) ∧ g	
    
  • Рассмотрим, в каких случаях условия будут возвращать истину. Внешняя операция конъюнкция: каждое из условий будет истинно только в том случае, если оба операнда истинны:
    например: 
    (a ≡ c) ∧ ¬b  возвратит истину, если:
    (a ≡ c) = 1 и ¬b = 1

    Это означает, что все операнды, стоящие после знака конъюнкции, должны быть истинны.

  • Составим битовую маску для наших уравнений с учетом указанного требования:
  •   цеп.1  
    a   ?      
    b   0      
    c   1      
    d   0      
    e   1      
    f   0      
    g   1      
    h   ?      
    
  • Значение для переменной a найдем из условия (a ≡ c) ∧ b. В битовой маске с=1, значит, чтобы условие a ≡ c было истинным, а должно тоже равняться 1 (таблица истинности эквивалентности).
  • Значение для переменной h найдем из условия (f ≡ h) ∧ ¬g. В битовой маске f=0, значит, чтобы условие f ≡ h было истинным, h должно тоже равняться 0 (таблица истинности эквивалентности).
  • Получим итоговую битовую маску:
  •   цеп.1  
    a   1      
    b   0      
    c   1      
    d   0      
    e   1      
    f   0      
    g   1      
    h   0      
    
  • Теперь вспомним, что каждая из переменных от a до h представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех. Т.е., к примеру:
  • x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1, либо 1 ∧ 0, либо 0 ∧ 0
     
    x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1
    
  • Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1один. Т.о., получаем:
  • 	34 * 14 = 81 набор значений
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1

(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

В качестве ответа Вам нужно указать количество таких наборов.

Ответ: 22

Показать решение (используется метод отображения):

  • Внешняя операция в отдельно взятом уравнении — это импликация, результат которой должна быть истина. Импликация истинна если:
  • 0 -> 0 0 -> 1 1 -> 1
    т.е. ложна только, когда 1 -> 0
  • Если скобка (¬x1 ∨ y1) = 0, то для скобки (¬x2 ∧ y2) возможны варианты 0 или 1.
  • Если скобка (¬x1 ∨ y1) = 1, то для скобки (¬x2 ∧ y2) возможен один вариант — 1.
  • В скобках дизъюнкция (∨) истинна, когда: 0 ∨ 1, 1 ∨ 0, 1 ∨ 1; ложна, когда: 0 ∨ 0.
  • В скобках конъюнкция истинна, когда 1 ∧ 1 и ложна во всех остальных случаях.
  • Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Выделим в ней те строки, которые возвращают ложь: т.е. где первая скобка (¬x1 ∨ y1) возвратит 1, а вторая (¬x2 ∧ y2) 0:
  • решение 23 задания демоверсия 2018

  • Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения. Для первого уравнения x1 и y1 будут обозначаться xi и yi, а x2 и y2 будут обозначаться xi+1 и yi+1.
  • задание 23 егэ демоверсия 2018 решение

  • Теперь найдем общее количество решений, подставляя в отображении соответствующие x и y, и, учитывая предыдущие значения:
  • 23 задание егэ демо разбор

  • В итоге получаем:
  • 1 + 19 + 1 + 1 = 22

📹 Видео


Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):

Сколько различных решений имеет уравнение:

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1

где a, b, c, d, e — логические переменные?

В качестве ответа указать количество таких наборов.


Ответ: 30

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

  • Внешняя логическая операция — — дизъюнкция. Таблица истинности:
  • 0 ∨ 0 = 0
    0 ∨ 1 = 1
    1 ∨ 0 = 1
    1 ∨ 1 = 1
    
  • Поскольку дизъюнкция равна единице аж в трех случаях, то искать количество вариантов будет достаточно сложно. Значительно проще найти варианты, когда ∨ = 0 и вычесть их из общего количества вариантов.
  • Найдем общее количество строк в таблице истинности. Всего 5 переменных, поэтому:
  • количество строк в ТаблИстин = 25 = 32 
  • Посчитаем, сколько вариантов имеют решение при значении уравнения = 0. Чтобы потом вычесть это значение из общего количества. Для операции дизъюнкция (∨) каждая скобка должна быть равна нулю:
  •  (a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 0
       0          0               0
    
  • Теперь рассмотрим каждую скобку отдельно:
  • 1. (a → b) = 0, импликация ложна в одном случае (1 → 0) = 0
    т.е. имеем a = 1, b = 0
    
    2. (c → ¬d) = 0, импликация ложна в одном случае (1 → 0) = 0
    т.е. имеем c = 1, d = 1
    
    3. ¬(e ∨ a ∨ c) = 0 
    
  • т.к. перед скобкой стоит отрицание, то для большей понятности раскроем скобки по закону Де Моргана:
  • ¬e ∧ ¬a ∧ ¬c = 0   
    Конъюнкция равна 0, когда хоть один операнд = 0.
    
  • из п.1 и п.2 имеем a = 1 и c = 1. Тогда для e имеем два варианта: e = 0, e = 1, т.е.:
  • ¬0 ∧ ¬1 ∧ ¬1 = 0
    ¬1 ∧ ¬1 ∧ ¬1 = 0
    
  • То есть всего имеем 2 цепочки «исключаемых» решений:
  • 1.  a = 1, b = 0, c = 1, d = 1, e = 0
    2.  a = 1, b = 0, c = 1, d = 1, e = 1
    
  • Эти два варианта исключаем (вычитаем) из общего количества:
  • 32 - 2 = 30
    


Разбор 23 задания демоверсии егэ по информатике 2019:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1
(y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1
…
(y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1
y7 → x7 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x7, y1, y2, … y7, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.


Ответ: 36

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

  • Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
  • Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:
  • 1 -> 1
    т.е.:
    (y1 → (y2 ∧ x1))(x1 → x2) = 1
        1                1
    
  • Найдем случаи, когда равенство будет ложным (чтобы в дальнейшем исключить эти случаи):
  • (y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 0
    
  • Внутри первой «большой» скобки находится операция импликации. Которая ложна:
  • 1 -> 0 = 0
    т.е. случаи:
    y1=1 → (y2=0 ∧ x1=1)
    y1=1 → (y2=1 ∧ x1=0)
    y1=1 → (y2=0 ∧ x1=0)
    
  • Таким же образом проанализируем вторую скобку. В ней импликация вернет ложь:
  • (x1=1 → x2=0)
    
  • Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Поскольку переменных 4, то строк будет 24 = 16. Выделим те строки, которые возвращают ложь:
  • решение 23 задания демоверсии егэ 2019

  • Теперь переходим к методу отображения. Для первого уравнения x1 и y1 обозначим xi и yi, а x2 и y2 обозначим xi+1 и yi+1. Стрелками обозначим значения только тех строк таблицы истинности, которые возвращают 1.
  • метод отображения в решении 23 задания егэ

  • Найдем общее количество решений, подставляя в таблицу из отображения соответствующие значения x и y, и, учитывая предыдущие значения:
  • таблица отображений для решения 23 задания егэ

  • Теперь вернемся к последнему равенству. По условию оно должно быть истинным. Равенство вернет ложь только в одном случае:
  • y7=1 → x7=0 = 0
    
  • Найдем соответствующие переменные в нашей таблице:2
  • Рассчитаем сумму по последнему столбцу, не учитывая строку, возвращающую ложь:
  • 1 + 7 + 28 = 36

📹 Видео

Информатика ЕГЭ 22 задание разбор

Разбор 22 задания ЕГЭ по информатике 2017 года ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

Исполнитель Счетчик преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:

  1. Прибавь 5
  2. Умножь на 5

Первая команда увеличивает число на экране на 5, вторая умножает его на 5.
Программа для исполнителя Счетчик — это последовательность команд.

Сколько существует программ, для которых при исходном числе 5 результатом является число 250, и при этом траектория вычислений содержит число 35 и не содержит числа 105?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 9, 45, 50.

Ответ: 8

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

  • Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:
  • решение 22 задания егэ

    1. 5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
    2. 35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
    3. 35 -> 105 — «ненужная» часть траектории;
    4. 105 -> 250 — тоже «ненужная» часть.
  • Чтобы вычислить результат, т.е. количество программ, необходимо:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    
    полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
    
  • Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
  • Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
  • Расчет отрезка 1: 5 -> 35
    • Возьмем такое число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
    • 5 не подходит: применимы две команды в интервале до 35: 
      5 + 5 = 10 и 5 * 5 = 25
      10 подходит: применима только одна команда:
      10 + 5 = 15, а 10 * 5 = 50 - больше 35
      
    • Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
    • решение 22 задание на графах

    • Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
    • 1_1

    • Итого получили две программы.
    • Результат: 2

  • Расчет отрезка 2: 35 -> 250
  • Возьмем такое число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
  • 55 
    т.к. 55 * 5 = 275 - это больше числа 250
    
  • Затем будем последовательно брать подходящие меньшие числа
  • 1_11

    Пояснение: поскольку это задача динамического программирования, то полученные в начале результаты, используются для дальнейших вычислений:

  • для числа 45 мы взяли результат, полученный для числа 50 (2);
  • для числа 40 мы взяли результат, полученный для числа 45 (3);
  • для числа 35 мы взяли результат, полученный для числа 40 (4);
  • Результат: 5

  • Расчет отрезка 3: 35 -> 105
  • Возьмем такое число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
  • 35 
    т.к. 35 * 5 = 175 - больше числа 105
    

    2

    Результат: 1

  • Расчет траектории 4: 105 -> 250
  • 1
    Результат: 1

  • Посчитаем результат, согласно полученной формуле:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    2 * (5 - 1 * 1) = 8
    

Разбор 22 задания ЕГЭ по информатике 2017 года ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

У исполнителя Увеличитель две команды, которым присвоены номера:

  1. прибавь 1
  2. умножь на 4

Первая из них увеличивает число на экране на 1, вторая умножает его на 4.

Программа для Увеличителя – это последовательность команд.

Сколько есть программ, которые число 3 преобразуют в число 44?

Ответ: 10

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

Использование графов

  • Возьмем такое число, находящееся в интервале от 3 до 44, для которого применима только одна команда:
  • 12 
    к нему применима только команда - прибавь 1 
    12 * 4 = 48 - это больше, чем 44 
    
  • Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):
  • 1
    Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

  • Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.
  • разбор 33 задания егэ
    Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:

    • для 11 взят результат, полученный для 12 (1);
    • для 10 взят результат, полученный для числа 11 (2);
    • для 9 взят результат, полученный для 10 (3);
    • и т.д.
  • Для последнего числа 3 получено 10 команд.

📹 Видео


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

Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
 1. Прибавить 1
 2. Прибавить 2
 3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Ответ: 60

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

  • Изобразим траекторию в виде луча, на котором отложим отрезки:
  • поиск траектории

  • Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:
  • 1 * 2 * 3
    или
    (2 -> 8) * (8 -> 10) * (10 -> 12)
    
  • Найдем отдельно количество программ каждого из отрезков:
  • 2 -> 8 = 15
  • На интервале от 2 до 8 возьмем число, для которого исполнима только одна из команд:
  • 7
    7 + 1 = 8
    7 + 2 = 9 - нельзя, вне интервала
    
  • Рассмотрим все числа интервала, двигаясь от большего к меньшему:
  • траектория

  • 8 -> 10 = 2
  • очевидно, что это две программы:
  • 2

  • 10 -> 12 = 2
  • 1

  • Выполним произведение полученных результатов:
  • 15 * 2 * 2 = 60
    

📹 Видео


Информатика ЕГЭ 21 задание разбор

Разбор 21 задания ЕГЭ по информатике 2017 года ФИПИ вариант 7 (Крылов С.С., Чуркина Т.Е.):

Напишите в ответе наименьшее значение входной переменной k, при котором программа выдает тот же ответ, что и при входном значении k=20.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var k, i : longint;
function f(n: longint) : longint;
begin
  f := -(n+1) * (n+1) * (n+1);
end;
 
function g(n: longint) : longint;
begin
  g := -2*n + 2;
end;
 
begin
  readln(k);
  i := 1;
  while f(i) > g(k) do
    i:= i+1;
  writeln(i)
end.

Ответ: 15

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

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

  • функция f возвращает отрицательный куб увеличенного на единицу параметра этой функции (если i=1, то n=1, функция f(n) возвратит -23):
  • при n = 1  
    f(1) = -(1+1) * (1+1) * (1+1) = -2 * 2 * 2 = -23
    
  • значение функции g зависит только от введенного k, т.к. k является параметром функции; значение g(k) постоянно и не меняется в программе (т.к. k не меняется);
  • при k = 20 функция g возвращает -38:
  • при k = 20 (n = 20):
    g := -2*n + 2 = -2*20 + 2 = -38
    
  • после ввода k проверяется условие цикла, который постоянно увеличивает i на единицу, пока f(i) > g(k), или, другими словами, пока отрицательное значение куба числа i+1 больше -38:
  • пока f(i) > 38 
      i = i + 1
    или:
    пока  -(i+1)3 > -38
      i = i + 1
    
  • построим таблицу значений функции f(i) и самого i:
  • i f(i) Работает ли условие цикла при k=20
    1 -23=-8 -28 > -38 — да
    2 -33=-27 -27 > -38 — да
    3 -43=-64 -64 > -38 — нет
  • т.е. при i = 3 цикл завершится, а при i = 2 цикл еще работает;
  • из функции g видим, что чем больше ее аргумент, тем меньшее значение она выдает;
  • чтобы найти наименьшее значение k, надо взять наибольшее значение функции g(k) (при таком же значении i), для которого бы цикл еще продолжал работать, это число -28:
  • i = 2 
    чтобы получить наименьшее k возьмем ближайшее к -27 значение g(k), т.е -28:
    f(i) > g(k), т.е. -27 > -28
    
  • для того чтобы найти k, подставим значение в функцию g(k):
  • -28 = -2*n + 2
    n = (-28-2)/-2 = 15
    
  • поскольку n — это и есть k, то k = 15

📹 Видео


Разбор 21 задания ЕГЭ по информатике 2017 года ФИПИ вариант 13 (Крылов С.С., Чуркина Т.Е.):

Определите, какое число будет напечатано в результате выполнения следующего алгоритма.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var a,b,t,M,R : integer;
function F(x: integer) : integer;
begin
  F := 4 * (x+2)*(x-4);
end;
 
begin
  a:=-20; b:=20;
  M:=a; R:= F(a);
  for t:=a to b do
      begin
           if (F(t)<R) then begin
              M:=t;
              R:=F(t);
           end;
      end;
  write(M);
end.

Ответ: 1

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

  • В цикле происходит поиск наименьшего значения функции F(t) на отрезке от a до b (строка 12 программы).
  • В функции F — квадратное уравнение, которое на графике представляет собой параболу. t — это точка x параболы, а F(t)у параболы. То есть в цикле организован поиск наименьшего y на отрезке параболы от a до b.
  • Преобразуем квадратное уравнение:
  • F(x) = 4(x+2)(x-4) = 4x2 - 8x - 32
    
  • Так как программа выводит на экран M (М — это и есть х), то нам необходимо найти такой x, при котором функция F(x) возвращает наименьшее значение.
  • Из уравнения видим, что ветви параболы направлены вверх (старший коэффициент 4x2 — положительный). Парабола может выглядеть примерно так:
  • решение 21 задания егэ

  • Очевидно, что наименьшее значение функции будет в вершине (в нашем случае она совпадает с точкой минимума). Найдем x вершины по формуле:
  • xверш = -b/2a

    \[ X верш= \frac {-(-8)}{2 * 4} = \frac {8}{8} = 1 \]

  • Поскольку M = t = x, то 1 — это и есть значение, которое выдаст программа

📹 Видео


Разбор 21 задания ЕГЭ по информатике 2017 года ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

Определите, какое число будет напечатано в результате выполнения следующего алгоритма.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var a,b,t,M,R : integer;
function F(x: integer) : integer;
begin
  F := -3 * (x+2)*(x-6);
end;
 
begin
  a:=-20; b:=20;
  M:=a; R:= F(a);
  for t:=a to b do
      begin
           if (F(t)<R) then begin
              M:=t;
              R:=F(t);
           end;
      end;
  write(M);
end.

Ответ: -20

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

  • В цикле происходит поиск наименьшего значения функции F(t) на отрезке от a до b.
  • В самой функции F — квадратное уравнение, что означает на графике параболу. Тогда t — это точка x параболы, а F(t)у параболы. То есть в цикле организован поиск наименьшего y на отрезке параболы от a до b.
  • Преобразуем квадратное уравнение:
  • F(x) = -3(x+2)(x-6) = -3x2 + 12x + 36
  • Так как программа выводит на экран значение M, то необходимо найти такой x, при котором функция F(x) выдает наименьшее значение (М — это и есть х).
  • Из уравнения видим, что ветви параболы направлены вниз (старший коэффициент -3x2 — отрицательный)
  • Так как мы рассматриваем только интервал от -20 до 20, то наименьшее значение y на этом промежутке параболы будет либо в точке x=-20, либо в точке x=20.
    y минимален либо при ч=20, либо при х=-20

    y минимален либо при х=20, либо при х=-20

  • Подставим последовательно значения -20 и 20 в качестве аргументов функции, чтобы найти наименьшее из полученных значений y:
  • F(-20) = -3*(-20+2)*(-20-6) = -1404
    F(20) = -3*(20+2)*(20-6) = 924
    
  • Видим, что наименьший y получается при х=-20.
  • Поскольку M = t = x, то -20 — это и есть значение, которое выведет программа.

📹 Видео


Разбор 21 задания ЕГЭ по информатике 2017 года ФИПИ вариант 20 (Крылов С.С., Чуркина Т.Е.):

Определите, какое целое значение H нужно ввести, чтобы число, напечатанное в результате выполнения следующего алгоритма, было наибольшим. Если таких значений несколько, то в ответ запишите минимальное из них.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var a,b,t,M,R,H : integer;
function F(H, x: integer) : integer;
begin
  F := (x-10)*(x-H);
end;
 
begin
  readln(H);
  a:=-20; b:=40;
  M:=a; R:= F(H,a);
  for t:=a to b do
      begin
           if (F(H,t)<R) then begin
              M:=t;
              R:=F(H,t);
           end;
      end;
  write(M);
end.

Ответ: 70

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

  • В цикле происходит поиск наименьшего значения функции F(H,t) на отрезке от a до b.
  • Величина H в программе не изменяется, то есть выполняет роль константы; она передаётся в функцию и влияет на значение функции.
  • В самой функции F — квадратное уравнение, что означает, что график этой функции — парабола. Тогда t — это точка оси x параболы, а F(H,t)у параболы. То есть в цикле организован поиск наименьшего y на отрезке параболы от a до b.
  • Рассмотрим квадратное уравнение:
  • F(x) = (x-10)(x-H) = x2 - 10x - Hx + 10H
  • Так как в результате работы программы выводится M, то нам необходимо найти такой x, при котором функция F(H,x) выдает наименьшее значение (М — это и есть х).
  • Из уравнения видим, что ветви параболы направлены вверх (старший коэффициент 1*x2 — положительный). Парабола может иметь такой вид:
  • y наименьшее при х=-20 или 2=40

  • Так как мы рассматриваем только интервал от -20 до 40, и по условию необходимо получить наибольшее значение x, то выгоднее построить такую параболу, когда наименьшее значение функции (y параболы) будет соответствовать точке x=40, т.е. будет соответствовать наибольшему возможному x:
  • график параболы для решения 21 задания егэ

  • Существует формула для x вершины: -b/2a.
  • Из предыдущего пункта можно найти H, зная, что минимальное значение функции достигается при хверш=40:
  • \[ 40 = \frac {-(-10-H)}{2*1} \]

    40*2 = 10+H; 
    H = 80-10 = 70 
    
  • Таким образом, чтобы программа вывела наибольшее x, необходимо, чтобы вершина параболы совпала с наибольшем значением данного интервала [-20,40], т.е. с 40. Функция в этой точке возвращает минимальное значение, а значение H при этом равняется 70.

📹 Видео


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

Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма.

Паскаль:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var a, b, t, M, R :longint;
function F(x: longint): longint;
begin
  F:= 2*(x*x-1)*(x*x-1)+27;
end;
begin
a:=-20; b:=20;
M:=a; R:=F(a);
for t:= a to b do begin
  if (F(t) <= R) then begin
     M:=t;
     R:=F(t)
  end
end;
write(M+R)
end.

Ответ: 28

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

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

  • В цикле программы ищется минимальное значение, возвращаемое функцией F(t), вызываемой с параметрами от -20 до 20.
  • После завершения работы цикла минимальное значение функции помещается в переменную R, а параметр, при котором функция возвратила минимальное значение, помещается в переменную M.
  • В конце программы выводится результат M+R.
  • В теле функции:
  • 2 * (x*x-1) * (x*x-1) + 27
    Т.е. в скобках получаем: 
    (x2 - 1)2
    
  • X вершины для такого уравнения находится по формуле:
  • (x2 — a)2;
    x1,2 верш=±√a
  • Таким образом, функция имеет два минимума — в точках -1 и 1 (оси ox).
  • Так как в условии программы стоит F(t) <= R, то условие будет истинным и при F(1). Проверим:
  • F(-1) = 2 * 0 * 0 = 27
    F(1) = 2 * 0 * 0 = 27
    
  • Таким образом, минимальное значение функции: R = 27, а параметр при минимальном значении функции: M = 1.
  • Результат:
  • M + R = 28 

📹 Видео


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

Напишите в ответе наибольшее значение входной переменной k, при котором программа выдает тот же ответ, что и при входном значении k=9.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 var
  k, i: longint;
function f(n: longint): longint;
begin
  f := -n * (n + 1);
end;
function g(n: longint): longint;
begin
  g := -2 * n + 2;
end;
 
begin
  readln(k);
  i := 1;
  while f(i) > g(k) do
    i := i + 1;
  writeln(i)
end.

Ответ: 11

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

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

  • функция f возвращает произведение числа на последующее число со знаком минус (если i=2, то n=2, функция f(n) возвратит -2 * 3):
  • при n = 2  
    f(2) = -2 * (3) = -6
    
  • значение функции g зависит только от введенного k, т.к. k является параметром функции; значение g(k) постоянно и не меняется в программе (т.к. k не меняется);
  • при k = 9 функция g возвращает -16:
  • при k = 9 (n = 9):
    g := -2*n + 2 = -2*9 + 2 = -16
    
  • после ввода k проверяется условие цикла, который постоянно увеличивает i на единицу, пока f(i) > g(k), или, другими словами, пока -i * (i+1) больше -16:
  • пока f(i) > -16 
      i = i + 1
    или:
    пока  -i * (i+1) > -16
      i = i + 1
    
  • построим таблицу значений функции f(i) и самого i:
  • i f(i) Работает ли условие цикла при k=9
    1 -1*2 =-2 -2 > -16 — да
    2 -2*3 =-6 -6 > -16 — да
    3 -3*4=-12 -12 > -16 — да
    4 -4*5=-20 -20 > -16- нет
  • т.е. при i = 4 цикл завершится, а при i = 3 цикл еще работает;
  • построим систему уравнений:
  • g(k)< f(3)
    g(k)>=f(4)
    т.е.:
    f(4) <= g(k) < f(3)
    или
    -20 <= g(k) < 12
    или
    g(k) ∈ [-20;-12)
    
  • найдем k согласно значениям промежутка:
  • 1.
    g(k) >= -20 => -2*k + 2 >= -20
    -2k >= -22 | :(-2) меняем знак!
    k <=11  
    2.
    g(k) < -12 => -2*k + 2 < -12
    -2k < -14 | :(-2) меняем знак!
    k > 7
    
  • получаем k в промежутке:
  • 7 < k <= 11
    
  • Наибольшее k на этом промежутке: k = 11.

📹 Видео


Решение 21 задания демоверсии егэ по информатике 2019:

Определите число, которое будет напечатано в результате выполнения следующего алгоритма.

Примечание. Функция abs возвращает абсолютное значение своего входного параметра.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var a, b, t, M, R : longint;
function F(x: longint) : longint;
begin
  F := abs(abs(x - 6) + abs(x + 6) - 16) + 2;
end;
begin
  a := -20; b := 20;
  M := a; R := F(a);
  for t := a to b do begin
    if (F(t) <= R) then begin
      M := t;
      R := F(t)
    end
  end;
  write(M + R)
end.


Ответ: 10

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

  • В 9-й строке алгоритма программы находится цикл, счетчик которого (t) принимает целые значения в интервале от a (-20) до b (20):
  • for t:=a to b do begin
      ...
    end;
    
  • В начале программы переменной M присваивается значение a, а переменной R присваивается результат функции с параметром a (в точке a):
  • M:=a; R:=F(a);
    
  • В цикле с помощью условного оператора сравнивается значение функции F(t) со значением переменной R. В случае истинности условия в R присваивается меньшее значение функции, а в M присваивается параметр функции, которая возвратила меньшее значение.
  • if (F(t)<=R)then begin
      M:=t;
      R:=F(t);
    end;
    
  • Таким образом, в цикле происходит поиск минимума функции F(t) на интервале от a до b. В итоге в переменной M оказывается значение параметра t, при котором функция достигает минимума на интервале от a до b.
  • Перепишем функцию в более понятном виде:
  • f(x) = | | x – 6 | +  | x + 6 |  – 16 | + 2
    
  • Рассмотрев функцию, можно сказать, что на графике она имеет минимумы в тех точках, где выполняется равенство:
  • | x – 6 | +  | x + 6 |  – 16 = 0; 
    
  • Решим данное уравнение:
  • в скобках под знаком модуля необходимо получить нули и отметить данные точки на числовой оси:
  • для | x – 6 | ноль будет в точке 6
    для | x + 6 | ноль будет в точке -6
    
  • для интервала (–∞; –6) раскроем модули, установив их с обратным знаком:
  • – (x – 6) – (x + 6) – 16 = 0  =>  
    -2x - 16 = 0; -2x = 16;
    x = – 8
    
  • полученное значение -8 находится в интервале (–∞; –6), поэтому является решением уравнения;
  • раскроем модули для полуинтервала [–6; 6):
  • – (x – 6) + (x + 6) – 16 = 0  => 
    12 = 16
    решений нет
    
  • раскроем модули для полуинтервала [6; ∞):
  • (x – 6) + (x + 6) – 16 = 0  =>
    2x = 16
    x = 8
    
  • полученное значение принадлежит полуинтервалу [6; ∞), значит, является решением уравнения.
  • Таким образом, мы нашли точки минимума (x = – 8 и x = 8), которые принадлежат отрезку [–20; 20].
  • В обеих полученных точках значение функции равно 2, какую же точку необходимо считать за минимум? Поскольку в условии F(t) <= R у нас стоит нестрогое неравенство, то дойдя до второй точки, условие тоже будет истинным и произойдет присваивание M:=t; и R:=F(t);. Поэтому в результате R равной 2, а M станет равной 8 (второй минимум).
  • На экран при этом выводится M+R:
  • 8 + 2 = 10
    

📹 Видео

Информатика ЕГЭ 20 задание разбор

Разбор 20 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

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

1
2
3
4
5
6
7
8
9
10
11
12
13
var x, L, M, D: integer;
begin
  readln(x);
  D:=x;
  L:=23;
  M:=141;
  while L<=M do
  begin
    L:=L+D;
    M:=M-3*D;
  end;
  writeln(L);
end.

Ответ: 15

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

Разберем решение по одному из возможных вариантов выполнения данного задания.
Рассмотрим алгоритм:

  • Результатом программы является вывод L.
  • Цикл перестанет работать, когда L станет больше M (т.к. while L<=M).
  • D в программе - это и есть искомый x (D:=x;).
  • В цикле оператор L:=L+D работает, как сумматор: L накапливает в себе сумму всех D, тогда как D в нашей задаче не меняется и равна введенному x.
  • Сумматор (L) до цикла обычно обнуляется, сделаем это: т.е. в строке 5 вместо L:=23 представим, что L:=0. Тогда и условие задачи поменяется: т.е. вместо указанного в условии числа 53 программа выводит L равное 53-23 = 30:
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    ...
      L:=23;
      M:=141;
      while L<=M do
      begin
        L:=L+D;
        M:=M-3*D;
      end;
      writeln(L); // выводится L = 30
    end.
  • Так как по заданию необходимо найти наибольший x, то представим, что он равен как раз 30:
  • L = L + D => L = 0 + 30 => L = 30 
    
  • После первой итерации цикла (первого прохода) условие продолжает работать, т.е.:
    L <= M  -> истинно (30<51) 
    цикл продолжает выполняться
    
  • Значит, одного прохождения цикла недостаточно, и, кроме того, 30 - четное (по заданию x - нечетное).
  • Предположим, что цикл имеет две итерации. За два прохождения цикла L увеличится на 2*D, то есть нужно взять такое D, чтобы 2*D было равно 30:
  • 30 / 2 = 15 
    То есть D = x = 15
    
  • Проверим:
  • D=15     1 проход  2 проход  3 проход
    L:=L+D;     23        38        53
    M:=M-3*D;   141       96        51  условие перестало работать
    
  • Т.е. D=15 полностью подходит, и это наибольшее возможное число при данных условиях.

📹 Видео


Разбор 20 задания ЕГЭ по информатике 2017 года ФИПИ вариант 8 (Крылов С.С., Чуркина Т.Е.):

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает S. Известно, что 100 ≤ x ≤ 200.
  
Укажите наибольшее допустимое число x, при вводе которого алгоритм распечатает 30.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var x,A,B,D,S: integer;
begin
  readln(x);
  B:= x;
  A:= 9;
  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.

Ответ: 120

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

✎ 1 способ (аналитический):
 

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

  1. В начале программы вводится x, две переменные - B и D присваивают значение введенного x. Переменной A присваивается значение 9, а переменная S обнуляется.
  2. Далее следует цикл, который зависит от переменной D (равной x): пока x div 2 > 0 выполняется тело цикла. Т.е. пока x, деленный целочисленно на 2, больше нуля.
  3. В теле цикла происходит увеличение переменной S либо на 9 (А:=9), либо на 1 в зависимости от четности значения D. Т.е. переменная S увеличивается на 9 в случае, если очередное значение D - четное и увеличивается на 1, если очередное значение D - нечетное.
  4. В конце цикла D целочисленно делится на 2 (D := D div 2).
  5. По условию программы S должно быть равно 30. Посчитаем максимальное количество итераций цикла: 2n <= 200, т.е. n = 7 (максимальное значение D - 200 - делим целочисленно на 2, пока это возможно). При этом минимальное количество итераций - 6 (2n >=100, т.е. n = 6)
  6. За 7 или 6 итераций цикла необходимо получить S = 30, каждую итерацию цикла, увеличивая S либо на 1, либо на 9. Рассмотрим варианты:
  7. 30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций, что соответствует действительности)
    30 =  9 + 9 + 12 * 1 (если взять две девятки, то цикл должен работать 14 раз 
    (9 + 9 + [12 единиц]), а это невозможно)
    
  8. Из 6 итераций имеем: 3 итерации с D - нечетным (когда s = s + 1) и 3 итерации с D - четным (когда s = s + 9)
  9. Четность чисел в двоичной системе счисления зависит от младшего бита: если младший бит = 0, то число четное, если 1, то число нечетное. Поскольку нам необходимо найти наибольшее x, то необходимо в трех старших битах данного числа, выраженного в двоичной системе счисления, поместить 1, а в остальных трех битах разместить 0. При этом необходимо не забыть про еще один старший бит равный 1 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла: условие цикла ложно while (1 div 2) > 0 - ложь):
  10. 11110002 = 12010
    первая единица будет стоять всегда, она не участвует в итерациях цикла
    
    Проверка:
    120| 0  - соответствует s + 9
     60| 0  - соответствует s + 9
     30| 0  - соответствует s + 9
     15| 1  - соответствует s + 1
      7| 1  - соответствует s + 1
      3| 1  - соответствует s + 1
      1|
     

✎ 2 способ:

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

  • Значение искомого x присваивается сразу двум переменным B и D, но B более нигде не используется, поэтому забудем про нее. D - это x.
  • В цикле:

  • D mod 2 - это крайняя справа цифра числа в двоичной системе счисления (младший разряд); т.е.:
  • например, если D = 510 = 1012, то D mod 2 = 1 (101)
  • в цикле есть сумматор S, результат которого выводится в программе (результат 30), и который накапливает в себя значения по следующему принципу:
  • если указанная крайняя цифра = 1, то в S добавляется 1, если крайняя цифра = 0, то в S добавляется 9 (А = 9);
  • последнее действие цикла D:= D div 2 - это отсечение крайнего младшего разряда числа D в двоичной системе счисления, т.е.:
  • если было D = 510 = 1012, то стало D = 102
  • условие цикла: пока D при целочисленном делении на 2 больше 0 (while (D div 2)>0);
  • анализ алгоритма показывает, что вводимый x можно рассматривать в двоичной системе счисления. Поскольку сумматор S выводит в результате число 30, то можно понять, как накапливается это число в S:
  • 30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций цикла)
  • поскольку цифра 9 прибавлялась 3 раза и единица прибавлялась 3 раза, значит, в двоичной записи исходного числа D было 3 цифры 0 и три цифры 1. Чтобы получить наибольшее x, как указано в задании, расположим в старших битах единицы, а в младших 0:
  • 111000
  • важно не забыть крайнюю слева цифру 1, которая останется не учтенной в цикле, так как условие при последней единице не выполняется:
  • при оставшемся D = 1 условие while (1 div 2) > 0 не работает, 
    поэтому добавляем еще старший разряд "1"
    таким образом, получаем число в двоичной системе: 1111000 
    
  • переведем в десятичное представление:
  • 64 32 16  8  4  2  1
    1  1   1  1  0  0  0   = 64 + 32 + 16 + 8 = 12010

📹 Видео 1
📹 Видео 2


Разбор 20 задания ЕГЭ по информатике 2017 года ФИПИ вариант 13 (Крылов С.С., Чуркина Т.Е.):

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

1
2
3
4
5
6
7
8
9
10
11
12
13
var x,L,M: integer;
begin
  readln(x);
  L:=0; M:=0;
  while x>0 do
  begin
    L:=L + 1;
    if M < (x mod 10) then
      M:=x mod 10;
    x:=x div 10;
  end;
  writeln(L);writeln(M);
end.

Ответ: 88

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

Рассмотрим алгоритм работы с L:

  • В конце программы алгоритм выводит значение L, равное 2 (по условию). В цикле L - это счетчик, увеличивающийся каждую итерацию цикла (каждое прохождение цикла) на 1.
  • Таким образом, цикл работает два раза.
  • В цикле x постоянно уменьшается на 1 разряд, т.е. от него отсекается цифра справа (x:=x div 10):
  • например, x = 243
    после выполнения x:=x div 10 получаем
    х = 24
    
  • Так как цикл работает два раза, значит x - двухзначное число, т.е. после двух проходов (итераций) цикла условие цикла перестало работать (x стало <= 0).

Рассмотрим работу с M в цикле:

  • В первую итерацию цикла М всегда заменится на значение x mod 10, так как изначально М = 0.
  • Из предыдущего пункта имеем, что M - это остаток от числа x при делении на 10. Т.е. M - это сначала (в первую итерацию цикла) разряд единиц числа x, а затем - сотен:
  • например, x = 243
    после выполнения M := x mod 10; получаем
    М = 3
    
  • В результате работы программы на экран выводится М = 8.

Рассмотрим две цифры числа x путем подстановки:

  • Поскольку по условию нам нужно наибольшее x, то попробуем в единицы записать число 8:
  • ? 9
  • В таком случае во второй итерации цикла условие в цикле M < (x mod 10) не будет работать, и программа распечатает 9 (вместо 8). Т.е. 9 не походит:
  • if M  < (x mod 10) then
          M:=x mod 10;
    1 шаг: 
    if 0  < (9) then
          M:=9;
    2 шаг:
    if 9 < (любая цифра) then ... 
    Условие не работает, программа распечатает М = 9. Не подходит!
    
  • Поставим вместо разряда единиц число 8:
  • ? 8
  • После первой итерации цикла M = 8 (по условию нам подходит):
  • if M  < (x mod 10) then
          M:=x mod 10;
    1 шаг: 
    if 0  < (8) then
          M:=8;
    
  • Теперь рассмотрим первую цифру числа x:
  • 9 8
    если она равна 9 (то есть число 98), 
    то М станет = 9 (а нам необходимо, чтобы осталось 8):
    
    1 шаг: 
    if 0  < (8) then
          M:=8;
    2 шаг:
    if 8 < 9 then ... 
    Условие работает, программа распечатает М = 9. Не подходит!
    
  • Возьмем цифру 8 (88):
  • 8 8
    1 шаг: 
    if 0  < (8) then
          M:=8;
    2 шаг:
    if 8 < 8 then ... 
    Условие не работает, программа распечатает М = 8. Подходит!
    
  • Наибольшее х = 88.

📹 Видео


Разбор 20 задания ЕГЭ по информатике "Типовые экзаменационные варианты" вариант 3, 2018 года и вариант 11, 2017 года (Крылов С.С., Чуркина Т.Е.):

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число M.
  
Известно, что x>40. Укажите наименьшее такое (т.е. большее 40) число x, при вводе которого алгоритм печатает 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var x,L,M: integer;
begin
  readln(x);
  L:=x; 
  M:=5;
  if L mod 2 = 0 then
    M:=24;
  while L <> M do
    if L > M then
      L:=L-M
    else
      M:=M-L;
  writeln(M);
end.

Ответ: 45

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

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

  • В начале программы запрашивается x. Переменной L присваивается значение x, а переменной M - значение 5.
  • Затем в условии проверяется четность переменной L: если переменная четная, то M присваивается значение 24.
  • Далее следует цикл, зависящий от переменных L и M: цикл завершится, когда L сравняется с M, т.е. согласно условию, когда L = M = 5 (так как по завершению программы на экран выводится число 5):
  • По завершению программы:
    L = M = 5
    
  • Кроме того, по условию известно, что x > 40.
  • В цикле из переменной большего значения вычитается переменная меньшего значения (алгоритм Евклида поиска наибольшего общего делимого):
  • НОД (a, b) = если a > b, то НОД (a-b, b) = если b > a, то НОД (a, b-a)
    
  • Поскольку в результате работы программы распечатывается значение M, равное 5, то можно утверждать, что если условие if L mod 2 = 0 не будет истинным, то в цикле постоянно будет происходить действие L:=L-M). Т.е. постоянно вычитается 5.
  • Исходя из предыдущего пункта, исходное число x должно быть кратно 5, так как в результате печатается 5 (M). А при M=24 алгоритм не выдаст в результате значение 5.
  • Первое наименьшее число, кратное 5 и большее 40 (по условию) - это 45.
  • Проверим по алгоритму:
  • L  M
    
    45 5
    40 5
    35 5
    30 5
    25 5
    20 5
    15 5
    10 5
    5  5 
    
  • Если следовать алгоритму Евклида, то число 5 (результат) - это наибольший общий делитель числа 5 (исходное значение M) и числа x (введенного числа). Поскольку x больше 40, то наименьшим значением для которого общим делителем с числом 5 будет само число 5 - это число 45.

📹 Видео


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.

Ответ: 79

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

✎ Способ 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.

📹 Видео 1
📹 Видео 2


Досрочный егэ по информатике 2018, вариант 1. Задание 20:

Укажите наибольшее десятичное число, при вводе которого на экране сначала напечатается 3, а затем 6.

1
2
3
4
5
6
7
8
9
10
11
12
var x, L, M: integer;
begin
 readln(x);
 L:=0; M:=0;
 while x > 0 do begin
  L:=L + 1;
  if (x mod 2) <> 0 then
    M:= M + x mod 8;
  x:= x div 8;
 end;
 writeln(L); write(M);
end.

Ответ: 425

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

Результат: 425

📹 Видео


Информатика ЕГЭ 19 задание разбор

Задание 19 ЕГЭ по информатике 2017 ФИПИ вариант 13 (Крылов С.С., Чуркина Т.Е.):

В программе описан одномерный целочисленный массив А с индексами от 0 до 10.

Язык программирования Паскаль:
s:=0;
n:=10;
for i:=0 to n-1 do begin
  s:= s + A[i] + A[i+1]
end;

В начале выполнения этого фрагмента в массиве находились двухзначные четные натуральные числа.
  
Какое наибольшее значение может иметь переменная s после выполнения данной программы?

Ответ: 1960

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

Рассмотрим алгоритм фрагмента программы:

  • Цикл выполняется 10 раз: от 0 до 9 (т.к. n-1).
  • В цикле повторяется операция, суммирующая два подряд идущих элемента массива, — текущего и следующего:
  • A[i] + A[i+1]
  • Данная сумма накапливается в переменной s, значение которой требуется узнать в задаче.
  • Поскольку по заданию необходимо найти наибольшее значение переменной s, и по заданию элементы массива — двухзначные четные натуральные числа, то представим, что все элементы равны самому большому двухзначному четному числу — 98. Это будет оптимальным вариантом.
  • В первый проход цикла получим:
  • s = 0 + 98 + 98 = 196
  • Полученная сумма будет каждый проход цикла увеличиваться на то же самое число (196):
  • s = 196 + 98 + 98
  • Так как проходов (итераций) цикла 10, то получим:
  • 196 * 10 = 1960

📹 Видео


Задание 19 ЕГЭ по информатике 2017 ФИПИ вариант 19 (Крылов С.С., Чуркина Т.Е.):

В программе описан одномерный целочисленный массив А с индексами от 0 до 10.

Язык программирования Паскаль:
s:=1;
n:=10;
for i:=1 to 5 do begin
  s:= s * A[i] * A[n-i+1]
end;

В начале выполнения этого фрагмента в массиве находились однозначные четные натуральные числа.
  
Какое наименьшее значение может иметь переменная s после выполнения данной программы?

Ответ: 1024

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

Рассмотрим алгоритм фрагмента программы:

  • Цикл выполняется 5 раз: от 1 до 5.
  • В цикле повторяется операция произведения двух элементов массива:
  • A[i] * A[n-i+1]
  • Определим, какие элементы перемножаются, подставив для n и i конкретные значения:
  • 1 шаг: A[1]*A[10]
    2 шаг: A[2]*A[9]
    3 шаг: A[3]*A[8]
    4 шаг: A[4]*A[7]
    5 шаг: A[5]*A[6]
    
  • Результат каждой операции умножения накапливается в переменной s, значение которой и требуется найти.
  • Поскольку в s накапливается произведение элементов массива, а по заданию элементы — однозначные четные натуральные числа, то представим, что в массиве все элементы равны самому малому однозначному четному числу — 2. Это будет оптимальным вариантом, т.к. по заданию, необходимо определить наименьшее значение.
  • В первый проход цикла получим:
  • s = 1 * 2 * 2 = 4
  • Полученное произведение будет каждый проход цикла перемножаться на предыдущее значение (4 — в первом шаге, 16 — во втором шаге и т.п.):
  • s = 4 * 2 * 2 = 16
    ...
    
  • Так как проходов цикла 5, то получим:
  • 45 = 1024

📹 Видео


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

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 соответственно, т.е. A[0] = 3, A[1] = 0 и т.д.

Определите значение переменной c после выполнения следующего фрагмента этой программы:

1
2
3
4
5
6
7
8
9
c := 0;
for i := 1 to 9 do
 if A[i-1] > A[i] then
 begin
   c := c + 1;
   t := A[i];
   A[i] := A[i-1];
   A[i-1] := t;
 end;

Ответ: 5

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

Результат: 5

📹 Видео


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

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 1, 3, 4, 7, 2, 9, 1, 2, 3, 0 соответственно, т.е. A[0] = 1, A[1] = 3 и т.д.

Определите значение переменной c после выполнения следующего фрагмента этой программы:

1
2
3
4
5
6
7
8
9
c := 0;
for i := 1 to 9 do
 if A[i] > A[0] then
 begin
   c := c + 1;
   t := A[i];
   A[i] := A[0];
   A[0] := 2*t;
 end;

Ответ: 2

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

  • Рассмотрим изменение всех переменных и элементов массива для каждой итерации (прохода) цикла:
  • 1 2 3 4 5 6 7 8 9
    i 1 2 3 4 5 6 7 8 9
    if 3>4
    true
    4>6
    false
    7>6
    true
    2>14
    false
    9>14
    false
    1>14
    false
    2>14
    false
    3>14
    false
    0>14
    false
    c 1 2
    t 3 7
    A[i] 1 6
    A[0] 6 14

📹 Видео



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

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 0, 7, 1, 3, 2, 1, 8, 9, 6, 3 соответственно, т.е. A[0] = 0, A[1] = 7 и т.д.

Определите значение переменной j после выполнения следующего фрагмента этой программы:

1
2
3
4
5
6
7
8
j:=9;
while A[j] + A[j-1] > 4 do
 begin
  t:=A[j];
  A[j]:=A[j-1];
  A[j-1]:=t;
  j:=j-1;
 end;

Ответ: 6

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


Информатика ЕГЭ 18 задание разбор

Поразрядная конъюнкция:

Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.):

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4

  
Для какого наименьшего неотрицательного целого числа A формула

(X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0)

тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?

Ответ: 3

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

Стоит заметить, что для такого типа задач, нет универсального единственного решения. Поэтому на видео, расположенном ниже, представлено два варианта решения.

Рассмотрим один из вариантов решения:

  • Удалим из формулы X&, чтобы сократить ее запись:
  • (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
    
  • Обратим внимание, что внешней операцией является конъюнкция — логическое умножение:
  • (A = 0)  ¬(35 ≠ 0 → 52 ≠ 0)
    
  • Разделим общее выражение на две части относительно внешней операции. Первая часть — неизвестная, искомая, а вторая — известная, ее можно вычислить:
  • (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
       1               2
    
  • Выполним некоторые преобразования во второй части формулы:
  • Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):
  • правило импликации: a → b = ¬a ∨ b
    (A = 0) ∧ ¬(35 = 0 ∨ 52 ≠ 0)
    т.к. в результате получается отрицание того, что 35 ≠ 0, 
    то убираем знак "не равно": было 35 ≠ 0, стало 35 = 0
    
  • Избавимся от отрицания перед скобками по закону Де Моргана:
  • закон де Моргана: ¬ (A ∨ B) = ¬ A ∧ ¬ B
    A = 0 ∧ 35 ≠ 0 ∧ 52 = 0
  • По условию формула должна быть ложной. Вспомним таблицу истинности для конъюнкции (внешняя операция в нашей общей формуле):
  • 0 ∧ 0 = 0
    0 ∧ 1 = 0
    1 ∧ 0 = 0
    1 ∧ 1 = 1
    
  • Вторая часть формулы — вычислима, поэтому начнем с нее. В ней находится операция конъюнкция, которая имеет один единственный вариант решения, когда ¬ A ∧ ¬ B = 1. То есть примем вторую часть за истину (=1). В таком случае, для того чтобы общее выражение стало ложным (так требуется по заданию), необходимо, чтобы утверждение, что A = 0 было ложным (т.к. в обратном случае получим: 1 ∧ 1 = 1):
  • (A = 0) ∧ 35 ≠ 0 ∧ 52 = 0
       0            1    = 0 
    
  • Вторая часть будет истинной только в том случае, если оба утверждения будут истинными:
  • 35 ≠ 0 ∧ 52 = истинно (=1)  если:
    35 ≠ 0 = истинно (=1)
    и
    52 = 0 = истинно (=1)
    
    так как стоит логическое умножение  - 
    смотрим выше таблицу истинности для конъюнкции
    
  • Из двух последних пунктов получаем три утверждения:
  • 35 ≠ 0  = 1  (истина)
    и
    52 = 0  = 1  (истина)
    и
    A = 0   = 0  (ложь)
    
  • Переведем числа в двоичную систему счисления:
  • 35: 100011  (≠ 0)
    52: 110100 (= 0)
    
  • Найдем такой X, который при поразрядной конъюнкции даст истинное значение для обеих частей.
  • Для начала рассмотрим ситуацию с числом 52 — это проще, т.к. для получения в результате нуля (52 = 0 = истина), достаточно во всех разрядах «перекрыть» единицы нулями:
  • 52 1 1 0 1 0 0
    X 0 0 ? 0 ? ?
  • Мы «перекрыли» все единицы нулями, чтобы в результате получить 0.
  • Теперь рассмотрим 35 ≠ 0 = 1. Для искомого X учтем уже полученные значения:
  • 35 1 0 0 0 1 1
    X 0
    (получено выше)
    0
    (получено выше)
    ? 0
    (получено выше)
    1 1
  • Объединим обе маски в одну:
  • 0 0 ? 0 1 1
  • Так как выражение X & A = 0 должно быть ложным, то найдем такое наименьшее А, при котором X & A ≠ 0. Для этого в тех разрядах Х, в которых находится единица, необходимо сохранить эту единицу и в соответствующих разрядах А:
  • X 0 0 ? 0 1 1
    A 0 0 0 0 1 1
  • Переведем результат в десятичную систему счисления:
  • 0000112 = 310

📹 Видео


Поразрядная конъюнкция:

Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 12 (Крылов С.С., Чуркина Т.Е.):

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4

  
Для какого наибольшего неотрицательного целого числа A формула

X & A ≠ 0 → (X & 36 = 0 → X & 6 ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном значении переменной X)?

Ответ: 38

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

    ✎ Способ 1:

  • Произведем замену:
  • z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)
    
  • Перепишем выражение:
  • ¬A → (z36 → ¬ z6)
    
  • Избавимся от импликации (A → B = ¬ A ∨ B):
  • Сначала по правилу преобразования импликации:
  • ¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6 
    
  • По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):
  • A + ¬z36 + ¬z6 = A + ¬(z36 * z6)
    
  • Вернемся опять к импликации:
  • A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A
    
  • Суть предыдущих действий в том, что нам сначала нужно прийти к конъюнкции, а затем необходимо прийти к импликации, но, избавившись от отрицания.
  • По следующему правилу ZK * ZM = ZK or M (К. Поляков) заменим конъюнкцию:
  • z36 * z6 = z36 or 6
  • Выполним поразрядную дизъюнкцию двоичных чисел 36 и 6:
  • 1001002 -> 36
    1102 -> 6
    
    100100
    +
       110
    1001102 -> 36 or 6 = 3810
    
  • Получаем:
  • z38 → A
    
  • Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 38. То есть:
  • A = 1001102 = 3810

      
    ✎ Способ 2:

  • Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:
  • x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1
  • Введем обозначения:
  • A = (x&A = 0);
    P = (x&36 = 0);
    Q = (x&6 = 0);
    
  • Перепишем выражение согласно введенным обозначениям:
  • ¬A → (P → ¬Q) = 1
    
  • Избавимся от импликации:
  • A ∨ (¬P ∨ ¬Q) = 1
    
  • A — наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
  • Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы общее выражение было = 1):
  • A ∨ (¬P ∨ ¬Q) = 1; 
    или 
    1 ∨ (0) = 1
    
  • Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
  • Получаем:
  • ¬P ∨ ¬Q = 0
    Отсюда имеем: 
    ¬P = 0 и ¬Q = 0 
    
    (дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)
    
  • Или запишем другим образом:
  • Q = 1 и P = 1
  • Построим побитовые маски:
  • 100100  : 36
    000110  : 6
    0**0**  : маска P (x&36 = 0)
    ***00*  : маска Q (x&6 = 0)
    
  • Сопоставим обе маски и маску x&A = 0:
  • 0**0**  : маска P (x&36 = 0)
    ***00*  : маска Q (x&6 = 0)
    0**00*  : общая маска x
    *00**0  : маска для A (x&A = 0)
    т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
    мы поставили нули.
  • Так как нам необходимо получить наибольшее A (по заданию), то вместо всех «звездочек» ставим единицы:
  • 100110 = 3810
    

Результат: 38

📹 Видео 1

📹 Видео 2


Отрезки на числовой прямой:

Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

Укажите наибольшую возможную длину промежутка А, для которого формула

((x ϵ P) → (x ϵ Q)) ∧ (x ϵ A)

тождественно ложна, то есть принимает значение 0 при любом значении переменной x.

Ответ: 4

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

  • Упростим формулу, избавившись от «x ϵ«:
  • (P → Q) ∧ A
    
  • Теперь преобразуем импликацию в скобках:
  • правило импликации: a → b = ¬a ∨ b
    (¬P ∨ Q) ∧ A
    
  • Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.
  • решение 18 задания егэ по информатике

  • Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:
  • (¬P ∨ Q) ∧ A = 0
  • Внешняя операция выражения — конъюнкция — ложна в трех случаях и только в одном — истинна:
  • (¬P ∨ Q) ∧ A
        0      0 = 0
        0      1 = 0
        1      0 = 0
        1      1 = 1
    
  • Теперь рассмотрим это выражение относительно наших отрезков на числовой прямой: если известная часть выражения (¬P ∨ Q) на каком-либо отрезке прямой дает истину, то неизвестная часть (A) должна возвращать ложь (по условию формула должна быть тождественно ложна).
  • Рассмотрим все отрезки числовой прямой для известной части выражения:
  • 1. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
    2. (¬P ∨ Q) = 1 ∨ 1 = 1  - на данном отрезке А должно равняться 0
    3. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
    4. (¬P ∨ Q) = 0 ∨ 0 = 0  - на данном отрезке А может! равняться 1
    5. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
    
  • Получаем, что на всех отрезках кроме 4-го выражение ¬P ∨ Q истинно, т.е. на отрезках 1, 2, 3 и 5 неизвестная часть A должна быть ложной (чтобы формула вернула ложь). Отсюда следует, что А может быть истинно только на отрезке 4.
  • Длина отрезка 4 составляет:
  • 48 - 44 = 4

📹 Видео


Отрезки на числовой прямой:

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

На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].
  
Укажите наибольшую возможную длину отрезка A, для которого формула

((x ∈ P) → (x ∈ Q))  → ¬(x ∈ A)

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.


Ответ: 10

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

  • Упростим выражение, введя обозначения:
  • A: x ∈ A
    P: x ∈ P
    Q: x ∈ Q
    
  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
  • (P → Q) → ¬A = 1
    
  • Избавимся от импликации:
  • (P → Q) → ¬A = 1        =>
    ¬(P → Q) ∨ ¬A = 1       =>
    ¬(¬P ∨ Q) ∨ ¬A = 1   
    
  • Используем закон Де Моргана для последующего преобразования:
  • ¬(¬P ∨ Q) ∨ ¬A = 1    =>
    P ∧ ¬Q ∨ ¬A = 1
    
  • А — наше неизвестное, а выделенную часть формулы можно найти. Необходимо, чтобы А = 1. Значит предположим, что ¬А = 0, тогда P ∧ ¬Q = 1 (если P ∧ ¬Q = 0, то ¬А может равняться и 0 и 1, так как имеет место операция логического сложения ∨)
  • Значит, имеем P ∧ ¬Q = 1. Кроме того, в данном случае имеет место операция конъюнкция, которую проще вычислить, если выражение равно 1 (так как для конъюнкции существует один единственный случай истинности: 1 & 1 = 1). Таким образом имеем утверждения:
  • А = 1
    P = 1
    ¬Q = 1 или Q = 0
    
  • Т.е. A истинно (=1) на промежутке пересечения отрезков P и ¬Q.
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • решение 18 задания ЕГЭ с числовой приямой

  • Очевидно, что А будет истинно, только в части 2 (на рис. желтым цветом), то есть соответствовать отрезку [10,20], имеющему длину 10.

Отрезки на числовой прямой:

Вариант 6: ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина:

На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].
  
Укажите наибольшую возможную длину отрезка A, для которого формула

((x ∈ P) ~ (x ∈ Q))  → ¬(x ∈ A)

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Ответ: 8

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

  • Упростим выражение, введя обозначения:
  • A: x ∈ A
    P: x ∈ P
    Q: x ∈ Q
    
  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
  • (P ~ Q) → ¬A = 1
    
  • Избавимся от импликации:
  • (P ~ Q) → ¬A = 1      =>
    ¬(P ~ Q) ∨ ¬A = 1
    

    Далее возможно 2 способа решения.
      
    ✎ 1 способ:

  • Избавимся от эквивалентности по правилу преобразования эквивалентности:
  • (a ~ b) = a * b + ¬a * ¬b
    ¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) =
    = ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) 
    
  • Преобразуем часть данного выражения по закону Де Моргана:
  • ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) =
    = ¬(P ∧ Q) ∧ (P ∨ Q) 
    
  • В итоге получим:
  • ¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1
  • А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда, чтобы общее выражение было истинным (по условию), нужно чтобы ¬(P ∧ Q) ∧ (P ∨ Q) = 1.
  • Имеем:
  • ¬(P ∧ Q) ∧ (P ∨ Q) = 1
    А = 1
    
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • 18 задание  ЕГЭ отрезки

  • Очевидно, что А будет истинно в двух отмеченных на рисунке частях: 2 и 4 (на рис. желтым цветом). Но по условию нам необходимо найти А наибольшей длины, соответственно, выбираем отрезок [12,20], имеющий длину 8.
  • ✎ 2 способ:
    После того, как мы избавились от импликации, имеем:

    ¬(P ~ Q) ∨ ¬A = 1
    
  • А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда ¬(P ~ Q) = 1 (чтобы общее выражение было истинным, как указанно в условии).
  • Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
  • Это соответствует двум отрезкам (см. рисунок выше, желтым цветом): [3,6] и [12,20]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [12,20], имеющий длину 8.

📹 Видео


Отрезки на числовой прямой:

Вариант 7: ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина:

На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].
  
Укажите наибольшую возможную длину отрезка A, для которого формула

(x ∈ A) → ¬((x ∈ P)  ~ (x ∈ Q))

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.


Ответ: 19

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

  • Упростим выражение, введя обозначения:
  • A: x ∈ A
    P: x ∈ P
    Q: x ∈ Q
    
  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
  • A → ¬(P ~ Q) = 1
    
  • Избавимся от импликации:
  • A → ¬(P ~ Q) = 1    =>
    ¬A ∨ ¬(P ~ Q) = 1
    
  • А — наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P ~ Q) = 1 (так как общая формула должна быть истинной по условию).
  • Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • 18 задание отрезки на числовой прямой

  • Получаем, что А соответствует двум отрезкам (см. рисунок, желтым цветом): [11,15] и [21,40]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [21,40], имеющий длину 19.

Поиск наибольшего или наименьшего числа А:

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

Для какого наибольшего целого числа А формула
демоверсия егэ 2018 решение 18 задания
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

Ответ: 99

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

  • Условно разделим исходное выражение на части:
  • решение 18 задания демоверсии егэ информатика

  • Главное действие (внешняя операция) в исходном выражении — это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части 1 и 2 должны быть истинными (т.к. по условию общая формула должна быть истинной).
    Рассмотрим часть 1:

  • если в 1.1 имеем x > 9, то часть 1 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
  • x<=9

    (импликация 0 → 0 = 1, 0 → 1 = 1)

  • теперь, для того чтобы в части 1, выражение было истинным, надо чтобы часть 1.2 была истинной:
  • x*x <= A

    (импликация 1 → 1 = 1)

  • таким образом, получаем:
  • x <= 9
    x2 <= A
    
    при любых x
    
  • так как нам необходимо найти наибольшее возможное А, то, значит, надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:
  • возьмем наименьшее натуральное: x=1, тогда A>=1

    Рассмотрим часть 2:

  • если 2.2 истинно (т.е. y <= 9), то часть 2 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
  • y > 9
  • теперь, для того чтобы в части 2 выражение было истинным, надо чтобы часть 2.1 была ложной:
  • y * y > A

    (импликация 0 → 0 = 1)

  • таким образом, получаем:
  • y > 9
    y2 > A
    
    при любых y
    
  • данная часть выражения ограничивает значения А сверху:
  • возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100
  • Получаем, что наибольшее А меньшее 100: А = 99

📹 Видео


Поиск наибольшего или наименьшего числа А:

Досрочный егэ по информатике 2018, вариант 1:

Укажите наименьшее значение А, при котором выражение

(y + 3x < A) ∨ (x > 20) ∨ (y > 40)

истинно для любых целых положительных значений x и y.

Ответ: 101

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

  • Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.
  •     1                 2
    (y+3x < A) ∨ (x > 20) ∨ (y > 40)
    
  • Поскольку основными операциями являются операции дизъюнкции (логического сложения) и порядок их выполнения не важен, то последней, внешней, операцией будем выполнять дизъюнкцию слева, т.к. она объединяет неизвестную и известную часть.
  • Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:
  • (y+3x < A) ∨ (x > 20) ∨ (y > 40)
      1 или 0?                   1               = 1
    Не подходит!
    
  • Соответственно, рассмотрим вариант, когда вторая часть ложна, тогда часть выражения с неизвестным А будет обязательно истинной, т.е.:
  • 1. (y+3x < A) = 1
    2. (x > 20) ∨ (y > 40) = 0
    
  • Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:
  • x <= 20
    y <= 40
    
  • Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.
  • Выразим А:
  • А > 3x + y
    A > 3*20 + 40
    A > 100 
    
  • Поскольку требуется найти наименьшее значение А, то имеем А = 101.

📹 Видео


Задание с ДЕЛ:

18_5. Разбор 18 задания (Вариант 138, К. Поляков) :

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

 
Для какого наименьшего натурального числа А формула

ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 3

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

  • Введем обозначения:
  • A = ДЕЛ(x,A); 
    D28 = ДЕЛ(x, 28); 
    D42 = ДЕЛ(x, 42)
    
  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
  • A → (¬D28 ∨ D42) = 1
    
  • Разделим данную формулу на две части: в одной из них - искомое A, а в другой - часть формулы с x, которую можно найти:
  • A → (¬D28 ∨ D42) = 1
     1        2
    
  • В части 2 полученной формулы находится операция дизъюнкция, которую проще найти, когда логическое выражение равно 0 (только один случай: 0 ∨ 0 = 0):
  • (¬D28 ∨ D42) = 0   один случай: когда ¬D28 = 0 и D42 = 0
  • Если вторая часть формулы равна 0, тогда необходимо, чтобы A = 0:
  • A → ¬D28 ∨ D42 = 1
    0       0     = 1
    1       0     = 0  - так нельзя! т.к. формула должна = 1
    
    ¬D28 ∨ D42 = 0 только при A = 0 
    
  • Т.е. имеем:
  • A = 0 
    при ¬D28 = 0 и D42 = 0
    
    или
    A = 1 
    при D28 = 0 и D42 = 1
    
  • Очевидно, что наименьшим x можем взять число 42: ДЕЛ(42, 42) и ¬(ДЕЛ(42, 28))
  • Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 42) и ¬(ДЕЛ(x, 28)), то разложим 42 на сомножители, начиная с самого маленького числа - 2:
  • делитель 2 (A=2):
    42 = 2 * 21   тогда:   
    ДЕЛ(x, A): x может быть и 42 и 28, т.е.
    ДЕЛ(42, A=2) и ДЕЛ(28, A=2) - нам не подходит! (должно быть ¬(ДЕЛ(x, 28)))
    
    следующий делитель 3 (A=3):
    42 = 3 * 14   тогда:    
    ДЕЛ(x, A), x может быть только 42:
    ДЕЛ(42, A=3), т.к. 28 не делится целочисленно на 3
    (т.е. при A = 3 имеем ¬(ДЕЛ(x, 28)))
    
  • Т.е. наименьшим А является число 3.

Задание с ДЕЛ:

18_6. Разбор 18 задания (Вариант 136, К. Поляков) :

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

  
Для какого наименьшего натурального числа А формула

 (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A) 

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 285

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

  • Введем обозначения:
  • A = ДЕЛ(x,A); 
    D19 = ДЕЛ(x, 19); 
    D15 = ДЕЛ(x, 15)
    
  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
  • (¬D19 ∨ ¬D15) → ¬A = 1
    
  • Избавимся от импликации:
  • D19 ∧ D15 ∨ ¬A = 1
    
  • Разделим данную формулу на две части: в одной из них - искомое A, а в другой - часть формулы с x, которую можно найти:
  • ¬A ∨ D19 ∧ D15 = 1
     1       2
    
  • Начнем с известной части - части 2 формулы. В ней находится операция конъюнкция, которую проще найти, когда все ее операнды равны 1 (единственный случай для конъюнкции: 1 ∧ 1 = 1).
  • Вторая часть общей формулы может равняться только 1, когда ¬A = 0 (если ¬A = 1, то вторая часть может равнять 0, а нам нужно 1) :
  • ¬A ∨ D19 ∧ D15 = 1
     0       1      = 1
    
  • Т.е. получаем:
  • ¬A = 0 при D19 ∧ D15 = 1
    или
    A = 1 при D19 = 1 и D15 = 1
    
  • Таким образом, имеем:
  • A = 1
    D19 = 1
    D15 = 1
    
  • Очевидно, что наименьшим x можем взять число 285 (15 * 19 = 285): ДЕЛ(285, 19) и ДЕЛ(285, 15)
  • Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 19) и ДЕЛ(x, 15), то введем предположение:
  • предположим, A = 5 тогда: 
    ДЕЛ(x, A=5): x может быть любым числом кратным 5, 
    а нам необходимо, чтобы ДЕЛ(x, 19) и ДЕЛ(x, 15), т.е A = 5 - нам не подходит! 
    
  • Очевидно, что A должно быть таким числом, при котором x принимает единственно возможное (наименьшее) значение 285:
  • Таким наименьшим A является само число 285.

Задание с ДЕЛ:

18_7. Решение 18 задания (Вариант 133, К. Поляков) :

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

  
Для какого наибольшего натурального числа А формула

  (ДЕЛ(x, 40) ∨ ДЕЛ(x, 64))  → ДЕЛ(x, A) 

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 8

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

  • Введем обозначения:
  • A = ДЕЛ(x,A); 
    D40 = ДЕЛ(x, 40); 
    D64 = ДЕЛ(x, 64)
    
  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
  • (D40 ∨ D64)  → A = 1
    
  • Избавимся от импликации:
  • ¬(D40 ∨ D64) ∨ A = 1
    или
    (¬D40 ∧ ¬D64) ∨ A = 1
    
  • Разделим данную формулу на две части: в одной из них - искомое A, а в другой - часть формулы с x, которую можно найти:
  • (¬D40 ∧ ¬D64) ∨ A = 1
          1         2
    
  • В полученной формуле необходимо, чтобы A в конечном счете было истинно. Т.е. (¬D40 ∧ ¬D64) должно быть = 0. Это нам ничего не дает, т.к. конъюнкция ложна в трех случаях (1*0, 0*1 и 0*0), т.е. D40 и D64 могут быть равны как 0, так и 1 (исключение составляет лишь вариант, когда оба D истинны, тогда логическое умножение 1 * 1 ≠ 0).
  • Преобразуем выражение первой части формулы по закону Де Моргана (чтобы оно равнялось 1):
  • ¬D40 ∧ ¬D64 = 0
    или
    ¬(¬D40 ∧ ¬D64) = 1
    
    Преобразуем по закону Де Моргана и получим:
    D40 ∨ D64 = 1
    
  • В этом случае логическое сложение тоже дает истину в трех случаях (1+1, 1+0, 0+1). Т.е. мы не сможем найти А с помощью функции ДЕЛ. Необходимо прибегнуть к решению с помощью кругов Эйлера.
  • В множество A должны входить все числа, которые попадают в объединение D40 + D64. Таким образом, нужно найти множество, в которое входят оба этих множества.
  • Найдем наибольший общий делитель чисел 40 и 64; это число 8:
  • 64 / 40 = 1 (24 остаток)
    40 / 24 = 1 (16 остаток)
    24 / 16 = 1 (8 остаток)
    16 / 8 = 2 (0 остаток) - НОД = 8
    +++
    40 / 8 = 5
    64 / 8 = 8
    
  • Т.е. можно сказать, что A = D40 + D64 = D8*D5 + D8*D8 = D8*(D5 + D8). D8 входит в каждое из множеств D40 и D64. Объединение D40 + D64 тоже входит в D8:
  • 2

  • 8 - наибольший общий делитель числе 40 и 64, значит, оно соответствует максимальному значению A.

Поразрядная конъюнкция:

18_8. Решение 18 задания (№ 209, С.С. Поляков, Саратов):

Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) →
→ ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))

тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной х)?

Ответ: 48

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

Результат: 48

Поиск наибольшего и наименьшего числа A:

Разбор 18 задания. Демоверсия егэ по информатике 2019:

Для какого наибольшего целого неотрицательного числа А выражение
  
(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?


Ответ: 15

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

  • Разделим общее выражение на две части. Выделим неизвестную часть красным:
  • (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
    
  • Неизвестная часть должна быть истинной, она обязательно будет истинна, если известная часть — ложь:
  • (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y) = 1
          0                  1
    
  • Т.е. 48 ≠ y + 2x = 0 или y + 2x = 48. На графике это уравнение представляет линию. Из условия имеем два ограничения:(x > 0) and (y > 0). Отобразим линию для 1-й четверти, соответствующей положительным x и y:
  • y + 2x = 48  :
    при x = 0, y = 48
    при y = 0, 2x = 48 => x = 24
    

    решение 18 задания демоверсии егэ 2019

  • Возьмем некоторое значение A, например, A = 25, отметим его на графике белой областью так, чтобы выполнялось (A < x) ∨ (A < y). По условию имеем, что все точки данной части отрезка прямой y + 2x = 48 должны принадлежать отмеченной белой области. Заштрихуем область для всех точек прямой (голубым цветом):
  • То есть все точки голубого квадрата должны находиться под отрезком линии (включая вершину (A, A)), и данный квадрат, соответствует максимальному значению A.
  • Наибольшее значение голубая область приобретает в точке пересечения прямой y + 2x = 48 с прямой y = x:
  • линия на графике для решения 18 задания егэ

  • Далее решаем полученное линейное уравнение (для x = y):
  • x + 2x = 48 =>
    3x = 48
    x = 16
    
  • Так как значение A должно быть меньше x, то наибольшее А = 15.

📹 Видео


Поиск наибольшего и наименьшего числа A:

Разбор 18 задания ЕГЭ вариант № 3, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина:

Для какого наименьшего целого числа А формула
  
(y + 5x <= 34) → ((y - x > 4) ∨ (y <= A))
 
тождественно истинна, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Ответ: 9

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

  • Общая идея такова:
    необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое A. После чего разделить формулу на две части, в одной из которых находится искомое.
  • Избавимся от импликации, это даст нам возможность опустить общие скобки во второй части формулы:
  • ¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A)
    
  • Разделим формулу на две части таким образом, чтобы внешняя операции отделяла часть, в которой находится искомое A:
  • ¬(y + 5x <= 34) ∨ (y - x > 4)(y <= A) = 1
            1 часть                  2 часть
    
  • Формула по условию должна быть истинной (=1). Внешняя операция — дизъюнкция — истинна аж в трех случаях: a=1 b=0, a=0 b=1, a=1 b=1.
  • Если мы допустим, что первая часть истинна, то вторая, искомая часть, может быть как истинной, так и ложной. Поэтому такой вариант не подходит.
  • Допустим, что первая часть ложна, тогда вторая, искомая часть, должна быть только истинной:
  • ¬(y + 5x <= 34) ∨ (y - x > 4)(y <= A) = 1
            1 часть = 0               2 часть = 1
    
  • С учетом, что в первой части формулы находится операция дизъюнкция, которая ложна только в одном случае (a=0 b=0), то выпишем утверждения, получившиеся из первой части:
  • y + 5x > 34 = 0, значит:
    1. y + 5x <= 34
    y - x > 4 = 0, значит:
    2. y - x <= 4
    
  • Кроме того, имеем еще одно утверждение второй части:
  • y <= A
    или
    A >= y
    
  • Из второго уравнения первой части выразим x и затем подставим результат в первое уравнение первой части:
  • y - x <= 4
    x >= y - 4;
    подставим:
    y + 5x <= 34;
    y + 5(y - 4) <= 34;
    y + 5y - 20 <= 34;
    6y <= 54;
    y <= 9
    
  • Поскольку имеем утверждение, что A >= y и в задании требуется найти наименьшее A, то получаем:
  • чтобы покрыть все y, возьмем наибольший возможный y = 9:
    A >= 9 => наименьшее A = 9
    

📹 Видео


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить