Задание 19 егэ информатика 2019

Предлагаем вашему вниманию разбор задания №19 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

30 января 2019

Что нового?

В предстоящем ЕГЭ не появилось никаких изменений по сравнению с прошлым годом.

Возможно, вам также будут интересны демоверсии ЕГЭ по математике и физике.

О нововведениях в экзаменационных вариантах по другим предметам читайте в наших новостях.

Сегодня будем тренироваться решать 19 задание из ЕГЭ по информатике.

В девятнадцатом задании ЕГЭ по информатике обычно даются задачи, в которых есть программный код на пяти языках программирования, и нужно показать умение работать с массивами.

Но зачем вообще нужны массивы в программировании ? Давайте об этом немного поговорим!

Зачем нужны массивы ?

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

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

var x, y, z, m, n: integer;
begin

// Первоначальные значения
x := 2;
y := 3;
z := 1;
m := 6;
n := 8;

//Удваиваем значения
x := 2 * x;
y := 2 * y;
z := 2 * z;
m := 2 * m;
n := 2 * n;

Видим, что приходится каждую переменную умножать отдельно.

Теперь тоже самое сделаем с помощью массива.

const n = 5; {Заводим константу, это будет длина массива}
var i :integer; {Заводим переменную для ЦИКЛА}
A:array[1..n] of integer; {Заводим массив}
begin

// Первоначальные значения
A[1] := 2;
A[2] := 3;
A[3] := 1;
A[4] := 6;
A[5] := 8;

//Удваиваем значения
for i:=1 to n do
  A[i] := 2 * A[i];

Обратите внимание, что удвоение во втором случае идёт с помощью двух строчек, когда в первом случае, удвоение получается с помощью пяти строчек. Если бы переменных было 1000, то выигрыш в объёме кода, был бы ещё большим.

Схематично наш массив можно представить так:

Это те же 5 переменных, но они объединены общем именем A. К каждому элементу массива можно обратится по индексу A[1], A[2] и т.д.

Здесь мы задали нумерацию элементов массива от 1 до 5. В паскале можно задать нумерацию элементов массива и от нуля. Например A:array[0..24] of integer;

Удобство использования массива заключается в том, что его элементы можно перебирать и обрабатывать с помощью ЦИКЛОВ! Значит, обычно массив и цикл работают в связке.

Не терпится уже разобрать первый пример из предположительных задач ЕГЭ по информатике.

Примеры решения задач 19 задания из ЕГЭ по информатике

Задача (стандартная)

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

Определите значение переменной k после выполнения следующего фрагмента программы, записанной ниже на разных языках программирования.

k=0
FOR i=0 TO 8
    IF A(i) > A(i+1) THEN
        k = k + 1
        t = A(i)
        A(i) = A(i+1)
        A(i+1) = t
    END IF
NEXT i

k = 0
for i in range(9):
    if A[i] > A[i+1]:
        k = k + 1
        t = A[i]
        A[i] = A[i+1]
        A[i+1] = t

k := 0;
for i := 0 to 8 do
    if A[i] > A[i+1] then
    begin
      k := k + 1;
      t := A[i];
      A[i] := A[i + 1];
      A[i + 1] := t
    end;

k := 0
нц для i от 0 до 8
    если A[i] > A[i + 1] то
        k := k + 1
        t := A[i]
        A[i] := A[i + 1]
        A[i+1] := t
     все
кц

k = 0;
for (i = 0; i <= 8; i++)
    if (A[i] > A[i + 1]) {
        k = k + 1
        t = A[i];
        A[i] = A[i + 1];
        A[i + 1] = t;    
    }

Решение:

Рассмотрим программу на языке Паскаль.

В начале переменная k = 0.

Затем начинается ЦИКЛ. Цикл будет выполнятся, пока переменная i «бежит» от 0 до 8.

При первом проходе ЦИКЛА i = 0, при втором i = 1 и т.д.

Внутри цикла проверяется условие (A[i] > A[i+1]). Если условие ВЕРНО, то программа прибавляет к переменной k единицу, и плюс, меняет значения ячеек массива A[i] и A[i+1] с помощью дополнительной переменной t.

Про замену значений двух переменных у меня на сайте написана целая статья!

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

Сам массив нам дан! (4; 5; 4; 7; 6; 3; 9; 11; 7; 8).

На рисунке показана каждая итерация ЦИКЛА при всех значениях переменной i. Зелёной галочкой отмечены те итерации, где сработает условие, и, значит, переменная k будет увеличена на 1.

Важно: После первого срабатывания условия, программа меняет значения элементов A[1] и A[2]. И наш массив принимает следующий вид: 4; 4; 5; 7; 6; 3; 9; 11; 7; 8. И при следующем проходе A[2] снова принимает значение «5», а не «4»! И так во всех случаях, когда условие срабатывает!

Таким образом, значение k после выполнения программы равна 5.

Ответ: 5

Продолжаем подготовку к 19 заданию из ЕГЭ по информатике.

Задача (ЕГЭ по информатике, 2019, Москва)

Представленный ниже фрагмент программы обрабатывает элементы одномерного массива A с индексами от 0 до 9. Перед началом выполнения данного фрагмента эти элементы массива имели значения 2, 3, 5, 6, 10, 4, 8, 6, 12, 9 (т.е. A[0] = 2, A[1] = 3, … , A[9] = 9).

Определите значение переменной s после выполнения фрагмента этой программы (записанной ниже на разных языках программирования)

n = 6
s = 0
FOR i = 0 TO 9
    IF A(i) > A(n) THEN
        s = s + (A(i) MOD A(n))
        t = A(i)
        A(i) = A(n)
        A(n) = t
    END IF
NEXT i

n = 6
s = 0
for i in range(0, 10):
    if A[i] > A[n]:
        s += A[i] % A[n]
        t = A[i]
        A[i] = A[n]
        A[n] = t

n := 6
s := 0
for i:=0 to 9 do begin
    if A[i] > A[n] then
    begin
        s := s + (A[i] mod A[n]);
        t := A[i];
        A[i] := A[n];
        A[n] := t;
    end
end;    

n = 6;
s = 0;
for(i = 1; i <= 9; ++i) {
    if (A[i] > A[n]) {
        s += A[i] % A[n];
        t = A[i];
        A[i] = A[n];       
        A[n] = t;
    }
}

Решение:

В начале задаются начальные значения для переменных s и n. Если посмотреть дальше глазами, то видим, что переменная n участвует для указания индекса элемента массива, переменная s — это результат суммы некоторых вычислений.

В ЦИКЛЕ i проходит каждое значение от 0 до 9. В теле Цикла только условие! А в условии проверяется: будет ли элемент массива A с индексом i больше, чем A[n].

В первый раз n=6 (A[6] = 8). Напоминаю, что в этой задаче номера индексов массива начинаются с нуля! Но если условие «сработает», то A[n] поменяется.

Если условие выполнится, то значение A[n] станет равно A[i]. Опять присутствует блок, где элементы массива A[n] и A[i] меняются значениями (Найдите этот кусок кода сами!). И, соответственно, сравнивать в условии будем тоже с новым значением.

Так же, если условие выполнится, то мы к тому, что было к переменной s прибавим значение A[i] mod A[n] (mod — это операция, которая показывает остаток от деления).

Причем, сначала происходит суммирование для переменной s, а потом уже замена значения для A[n].

Таким образом, по окончании данного фрагмента программы, получится в переменной s значение 4.

Ответ: 4

Ещё один пример 19 задания из реального экзамена, который был в 2020 году в Москве!

Задача (ЕГЭ по информатике, 2020, Москва)

Представленный ниже фрагмент программы обрабатывает элементы одномерного целочисленного массива A c индексами от 0 до 11. Перед началом выполнения данного фрагмента эти элементы массива имели значения согласно таблице:

Определите значение переменной s после выполнения фрагмента этой программы (записанного ниже на разных языках программирования).

s = 0
FOR i = 1 TO 11
    IF A(i-1) DIV A(i) < 2 THEN
        s = s + A(i)
    ELSE
        A(i) = A(i) * i
    END IF
NEXT i

s = 0
for i in range(1, 12):
    if A[i-1] // A[i] < 2:
        s += A[i]
    else:
        a[i] = a[i] * i

s := 0;
for i:=1 to 11 do begin
    if A[i-1] div A[i] < 2 then
    begin
        s := s + A[i]
    else
        A[i] := A[i] * i;
    end
end;    

s = 0;
for (i = 1; i < 12; ++i ) {
    if (A[i-1] // A[i] < 2) {
        s += A[i]
    }
    else {
        A[i] = A[i] * i
    }
}

Решение:

Цикл «пробегает» весь массив. Здесь переменная i начинает идти с 1, потому что мы внутри тела цикла обращаемся к элементу с индексом i-1. Если бы i пошла с нуля, то получилось бы, что программа обратилась к элементу с индексом -1, и была бы ошибка.

Внутри ЦИКЛА находится одно условие. В условии сразу проверяется меньше ли двух результат от целочисленного деления A[i-1] на A[i] (div — это целочисленное деление, т.е. обычное деление, но дробная часть отбрасывается). Если условие выполнится, то программа к переменной s прибавит элемент A[i]. Если условие не будет выполнено, то элемент A[i] будет умножен на i, и это повлияет на следующую итерацию, ведь массив то изменится.

Ответ: 125

На этом всё! Счастливого ЕГЭ по информатике!

Теория игр. Разбираем задания №19, 20 и 21.

Задание №19. Умение анализировать алгоритм логической игры.
Задание №20. Умение найти выигрышную стратегию игры.
Задание №21. Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию.
Уровень сложности — повышенный, максимальный балл за выполнение каждого задания — 1, общее время на выполнение трёх заданий — 22 минуты.

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

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 72.

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

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

Разбор задания №19. Из условия мы знаем, что Петя не может выиграть своим первым ходом, но Ваня, независимо от хода Пети, выигрывает. Петя парень не глупый и, естественно, сделает самый маленький ход – добавит в кучу один камень (S+1), чтобы Ваня от выигрыша был как можно дальше. Далее Ваня делает свой первый ход и выигрывает. Ване необходимо максимально увеличить предыдущее значение камней в куче, следовательно, Ваня увеличивает количество камней в куче в пять раз (S+1)*5. Теперь просто решаем неравенство:

(S+1)*5 ≥ 73
5S  ≥ 70
S ≥ 13,6
S = 14

Ответ: 14.

№20. Для игры, описанной в предыдущем задании, укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в порядке возрастания.

Разбор задания №20. Здесь мы должны найти два значения S – наибольшее и наименьшее. Начнём с наибольшего (это проще). По условию Петя не выигрывает своим первым ходом, но он же его делает! Следовательно, Петя ходит минимальный ход, чтобы Ваня был максимально далёк от победы (S+1). Далее ходит Ваня, а он тоже парень не глупый и старается не дать Пете победить и делает минимальный ход (S+1)+1. Теперь Петя делает максимально возможный ход, чтобы победить – он увеличивает предыдущее значение камней в куче в пять раз ((S+1)+1)*5. Решаем неравенство:

((S+1)+1)*5 ≥ 73
5S ≥ 63
S ≥ 12,6
S = 13

Теперь определим наименьшее значение S. Мы только что определили, что при S = 13 Петя делает свой ход и количество камней в куче становиться равным 14. То есть из этой позиции Петя точно выигрывает, независимо от того, как будет ходить Ваня. А как ещё после первого хода Пети в куче можно получить количество камней равное 14? По условию мы можем добавить один камень или четыре или увеличить их количество в пять раз. Четырнадцать на пять не делится (камни у нас целые числа), а вот отнять от четырнадцати четыре можно. Следовательно, 14 – 4 = 10. Это минимальное количество камней в куче, при котором Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Ответ: 1013.

№21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Разбор задания №21. При решении этого задания мы будем опираться на уже известные нам данные, полученные из предыдущего задания. Мы знаем, что при S = 10 Петя выигрывает, а по условию должен выиграть Ваня своим вторым ходом, следовательно, достаточно уменьшить это значение на единицу: 10 – 1 = 9. После первого хода Петя увеличивает количество камней на один 9 + 1 = 10, далее Ваня увеличивает количество камней в куче на четыре 10 + 4 = 14. Позиция 14 – это выигрышная позиция, нам это известно из предыдущих заданий.

Ответ: 9.

Методическая разработка  «Решение одной задачи»

Камаева З.И.

учитель информатики МБОУ гимназия № 7

ИНФОРМАТИКА, ЕГЭ 2019, задание № 19.

По кодификатору задание №19 – это работа с массивами (дополнение, считывание, поиск, сортировка, массовые операции и др.);

код проверяемых элементов содержания 1.5.2 / 1.5.6;

код проверяемых требований к уровню подготовки 1.1.4;

уровень сложности  П (повышенный);

максимальный балл за выполнение задание 1;

примерное время выполнения задания 5 минут.

Разбор задания №19 из тренировочной работы №3 от 16 января 2019 года, вариант ИН10303

СтатГрад 2018-2019 учебный год.

 Для решения задания необходимо повторить:

1. Понятие цикла for со счетчиком.
2. Работа с одномерными и двумерными массивами.
3. Понятие матрицы, диагонали матрицы.

19. Представленный на пяти языках программирования фрагмент программы обрабатывает элементы одномерного целочисленного массива A с индексами от 0 до 9. Перед началом выполнения данного фрагмента эти элементы массива имели значения 3, 5, 8, 2, 1, 4, 3, 1, 2, 6 (т.е. A[0] = 3, A[1] = 5, …, A[9] = 6). Определите значение переменной s после выполнения фрагмента.

Разбор задания на Паскале.

s := 0;

for i:=0 to 8 do begin

    if  A[i] < A[9] then begin  

        t := A[i];    

        A[i] := A[8-i];    

        A[8-i] := t;    

        s := s + t;  

    end;

end;

Алгоритм решения:

1. определение исходных данных;
2. определение выходных данных;
3. определение схемы работы алгоритма программы;
4. заполнение трассировочной таблицы;
5. ответ.

1. Исходные данные. На входе имеем одномерный целочисленный массив, состоящий из 10 элементов:

A[0]=3, A[1]=5, A[2]=8, A[3]=2, A[4]=1, A[5]=4, A[6]=3, A[7]=1, A[8]= 2, A[9]=6;

Запишем массив в виде таблицы:

1. Выходные данные — значение переменной s.
2. Из фрагмента программы следует: первоначальное обнуление переменной s=0,

при каждом входе в цикл for i:= 0 до 8 происходит проверка условия A[i] < A[9] , означающее, что все действия в цикле будут производиться с элементами массива, значение которых меньше последнего. Если условие истинно, то переменной t присваивается значение элемента A[i] ( t:=A[i] ). Далее происходит обмен значений A[i]  и A[8-i] и следующим шагом  переменная s увеличивается на величину значения t (s= s+t). Схема работы алгоритма:

1. Исходя из схемы, строим трассировочную таблицу.

1. Ответ 24.

Или

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

Ответ : 24.