🗊Презентация Задания ЕГЭ. Исправление ошибок в программе

Задания ЕГЭ. Часть 6 24 Исправление ошибок в программе 25 Алгоритмы обработки массивов 26  Выигрышная стратегия 27 Программирование

24-2 Требовалось на­пи­сать программу, при вы­пол­не­нии ко­то­рой с кла­ви­а­ту­ры вво­дит­ся по­сле­до­ва­тель­ность из шести не­от­ри­ца­тель­ных целых чисел, не пре­вы­ша­ю­щих 106, под­счи­ты­ва­ет­ся и вы­во­дит­ся сумма введённых чётных чисел или 0, если чётных чисел в по­сле­до­ва­тель­но­сти нет. Уче­ник на­пи­сал такую программу:

24-2 программа var n, s: longint; i: integer; Begin s:=1; for i:=1 to 6 do begin readln(n); if i mod 2 = 0 then s := s + n; end; write(s); end.

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

24-2 Решение Первая стро­ка с ошибкой: s:=1; Исправленная строка: s:=0;   Вторая стро­ка с ошибкой: if i mod 2 = 0 then Исправленная строка: if n mod 2 = 0 then  

24-3 Дано целое по­ло­жи­тель­ное число N. Не­об­хо­ди­мо опре­де­лить наи­мень­шее целое число K, для ко­то­ро­го вы­пол­ня­ет­ся неравенство:   1 + 2 + … + K > N.   Для ре­ше­ния этой за­да­чи уче­ник на­пи­сал программу, но, к сожалению, его про­грам­ма неправильная.

24-3 Программа var n, k: integer; begin    read(n);   k := 1;    while n>0 do begin     n := n-k;     k := k+1;   end;   writeln(k) end.

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

24-3 Решение 1. Примеры чисел, при вводе которых программа выводит неверный ответ:

24-3 Решение 2. Примеры чисел, при вводе которых программа выводит верный ответ: Заметим, что программа выдаёт верный ответ для тех значений N, которые можно представить в виде суммы 1 + 2 + … + K. При K = 1, 2, 3, 4 получим примеры, приведённые в таблице. Во всех остальных случаях программа выдаёт неверный ответ.

24-3 Решение 3. Программа содержит две ошибки: 1) неверное условие цикла; 2) неверный вывод результата (выводится значение, на 1 превышающее верное).   Пример ис­прав­ле­ния для языка Паскаль: Первая ошибка: while n>0 do begin Исправленная строка: while n>=0 do begin Вторая ошибка: writeln(k) Исправленная строка: writeln(k-1) Незначительной опиской, не вли­я­ю­щей на оценку, сле­ду­ет счи­тать от­сут­ствие слу­жеб­ных слов и зна­ков после со­дер­жа­тель­ной части исправления.

24-1 На об­ра­бот­ку поступает по­сле­до­ва­тель­ность из четырёх не­от­ри­ца­тель­ных целых чисел (некоторые числа могут быть одинаковыми). Нужно на­пи­сать программу, ко­то­рая выводит на экран ко­ли­че­ство чётных чисел в ис­ход­ной последовательности и мак­си­маль­ное чётное число. Если чётных чисел нет, тре­бу­ет­ся на экран вы­ве­сти «NO». Известно, что вво­ди­мые числа не пре­вы­ша­ют 1000. Про­грам­мист написал про­грам­му неправильно. Ниже эта на­пи­сан­ная им про­грам­ма для Ва­ше­го удобства при­ве­де­на на пяти язы­ках программирования.

const n = 4; const n = 4; var i, x: integer; maximum, count: integer; begin    count := 0;   maximum := 1000;    for i := 1 to n do    begin      read(x);      if x mod 2 = 0 then      begin       count := count + 1; if x > maximum then maximum := i     end    end;    if count > 0 then   begin       writeln(count);     writeln(maximum)    end    else     writeln('NO') end.

Последовательно вы­пол­ни­те следующее. Последовательно вы­пол­ни­те следующее. 1. Напишите, что вы­ве­дет эта про­грам­ма при вводе последовательности: 2 9 4 3 2. При­ве­ди­те пример такой последовательности, со­дер­жа­щей хотя бы одно чётное число, что, не­смот­ря на ошибки, приведённая про­грам­ма печатает пра­виль­ный ответ. 3. Най­ди­те все ошиб­ки в этой про­грам­ме (их может быть одна или несколько). Известно, что каж­дая ошибка за­тра­ги­ва­ет только одну стро­ку и может быть ис­прав­ле­на без из­ме­не­ния других строк. Для каж­дой ошибки: 1) вы­пи­ши­те строку, в ко­то­рой сделана ошибка; 2) укажите, как ис­пра­вить ошибку, т.е. при­ве­ди­те правильный ва­ри­ант строки. Достаточно ука­зать ошибки и спо­соб их ис­прав­ле­ния для од­но­го языка программирования. Обратите внимание, что тре­бу­ет­ся найти ошиб­ки в име­ю­щей­ся программе, а не на­пи­сать свою, возможно, ис­поль­зу­ю­щую другой ал­го­ритм решения. Ис­прав­ле­ние ошибки долж­но затрагивать толь­ко строку, в ко­то­рой находится ошибка.   Примечание. 0 – чётное число.

Решение 1. Программа вы­ве­дет 2 1000. 2. Например, набор 2 4 5 1000. 3. Пример ис­прав­ле­ний для языка Паскаль Первая ошибка:  maximum := 1000;  Исправленная строка: maximum := -1; Вторая ошибка: maximum := i Исправленная строка: maximum := x

24-4 Для за­дан­но­го по­ло­жи­тель­но­го ве­ще­ствен­но­го числа A не­об­хо­ди­мо найти мак­си­маль­ное целое число K, при ко­то­ром вы­пол­ня­ет­ся неравенство Для ре­ше­ния этой за­да­чи уче­ник на­пи­сал такую программу.

24-4 Программа var a, s: real; k: integer; Begin     read(a);     k := 1;     s := 1;     while s<a do begin         s := s + 1.0/k;    k := k + 1;     end;     write(k); end.

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

24-4 Решение Решение ис­поль­зу­ет за­пись про­грам­мы на Паскале. До­пус­ка­ет­ся ис­поль­зо­ва­ние про­грам­мы на дру­гих языках. 1. При вводе числа 1.2 про­грам­ма вы­ве­дет число 2. 2. При­ме­ры чисел, при вводе ко­то­рых про­грам­ма вы­во­дит вер­ный ответ: 1.6, 2.05. Примечание для проверяющего. Про­грам­ма со­дер­жит две ошибки, одна из ко­то­рых при­во­дит к уве­ли­че­нию ответа, дру­гая – к уменьшению. В не­ко­то­рых слу­ча­ях эти ошиб­ки ком­пен­си­ру­ют друг друга, и ответ ока­зы­ва­ет­ся правильным. Это происходит, если зна­че­ние A по­па­да­ет в один из сле­ду­ю­щих диапазонов: 1.5 < A < 1.83, 2 < A < 2.08.

24-4 Решение (продолжение) 3. Про­грам­ма со­дер­жит две ошибки. 1) Не­вер­ная инициализация. На­чаль­ное зна­че­ние S долж­но быть равно нулю. В приведённом ва­ри­ан­те вы­чис­лен­ная сумма ока­зы­ва­ет­ся на 1 боль­ше пра­виль­но­го значения. Строка с ошибкой:         s := 1; Правильная строка:         s := 0; 2) Не­вер­ное опре­де­ле­ние ответа. Приведённая про­грам­ма на­хо­дит не мак­си­маль­ное K, при ко­то­ром вы­пол­ня­ет­ся неравенство, а минимальное, при ко­то­ром оно не выполняется, то есть уве­ли­чи­ва­ет вер­ное зна­че­ние на 1. Кроме того, ис­поль­зо­ван­ный по­ря­док дей­ствий в цикле (увеличение K после уве­ли­че­ния S) при­во­дит к уве­ли­че­нию ещё на 1. Это можно было бы исправить, из­ме­нив по­ря­док дей­ствий в цикле и умень­шив K после за­вер­ше­ния цикла, но эти дей­ствия не раз­ре­ше­ны по усло­вию задачи. Поэтому для ис­прав­ле­ния ошиб­ки можно про­сто скор­рек­ти­ро­вать зна­че­ние при выводе. Строка с ошибкой:         write(k); Правильная строка:         write(k-2);

25-1 Условие Дан це­ло­чис­лен­ный мас­сив из 20 элементов. Эле­мен­ты мас­си­ва могут при­ни­мать целые зна­че­ния от –10 000 до 10 000 включительно. Опи­ши­те на одном из язы­ков про­грам­ми­ро­ва­ния алгоритм, поз­во­ля­ю­щий найти и вы­ве­сти ко­ли­че­ство пар эле­мен­тов массива, в ко­то­рых сумма эле­мен­тов де­лит­ся на 3, но не де­лит­ся на 9. В дан­ной за­да­че под парой под­ра­зу­ме­ва­ют­ся два со­сед­них эле­мен­та массива. Исходные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже. За­пре­ща­ет­ся ис­поль­зо­вать переменные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать не­ко­то­рые из опи­сан­ных переменных.

25-1 Начало программы const N = 20; var a: array [1..N] of integer; i, j, k: integer; begin for i := 1 to N do readln(a[i]); … end.

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

25-1 Решение k := 0; for i := 1 to N-1 do if ((a[i]+a[i+1]) mod 3=0) and ((a[i]+a[i+1]) mod 9<>0) then k:=k+1; writeln(k);

25-2 Условие Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых оба числа являются чётными. В данной задаче под парой подразумевается два подряд идущих элемента массива. Например, для массива из пяти элементов: 6; 1; 4; 6; 10 – ответ: 2. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

25-2 Условие (начало программы) const     N = 20; var     a: array [1..N] of integer; i, j, k: integer; begin     for i := 1 to N do         readln(a[i]);     ... end. В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия.

25-2 Решение k := 0; for i := 1 to N - 1 do     if (a[i] mod 2 = 0) and (a[i + 1] mod 2 = 0) then         k:=k+1; writeln(k);

25-3 Условие Дан массив, содержащий 2017 положительных целых чисел, не превышающих 1000. Необходимо найти и вывести максимальный из тех элементов этого массива, восьмеричная запись которых содержит не менее четырёх цифр и оканчивается цифрой 4. Если таких чисел в массиве нет, ответ считается равным нулю. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.

25-3 Пример начала программы const     N = 2017; var     a: array [1..N] of integer;      i, m, k: integer; begin     for i := 1 to N do         readln(a[i]);     ... end. В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия.

25-3 Решение m := 0; for i := 1 to N do     if (a[i] >= 512) and (a[i] mod 8 = 4) and (a[i] > m) then   m := a[i]; writeln(m);

26-1 Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Игра завершается в тот момент, когда общее число камней в двух кучах становится не менее 31. Если в момент завершения игры общее число камней в двух кучах не менее 40, то выиграл Петя, в противном случае — Ваня. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

26-2 Два игрока, Петя и Вася, иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки камней, в пер­вой из ко­то­рых 2, а во вто­рой — 1 камень. У каж­до­го игрока не­огра­ни­чен­но много камней. Иг­ро­ки ходят по очереди, пер­вым ходит Петя. Ход со­сто­ит в том, что игрок или уве­ли­чи­ва­ет в 3 раза число кам­ней в какой-то куче, или до­бав­ля­ет 3 камня в какую-то кучу. Вы­иг­ры­ва­ет игрок, после хода ко­то­ро­го в одной из куч ста­но­вит­ся не менее 24 камней. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре? Каким дол­жен быть пер­вый ход вы­иг­ры­ва­ю­ще­го игрока?

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

26-3 Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (3, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трёх точек: или в точку с координатами (x + 3, y), или в точку с координатами (x, y + 2), или в точку с координатами (x, y + 4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0, 0) больше 12 единиц. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Постройте де­ре­во партии для выигрышной стратегии (в виде ри­сун­ка или таблицы).

26-3 Решение Квадрат расстояния от фишки до точки с координатами (0, 0): r2 = x2 + y2. Побеждает игрок, после хода которого r2> 144. Алгоритм выигрышной стратегии определим при помощи дерева всех возможных партий. Не будем приводить здесь полное дерево, отметим лишь, что при ходе первого игрока в точку (3, 4) первый игрок при любом ответе противника имеет выигрышный набор ходов. Построим дерево партии для выигрышной стратегии первого игрока: в узлах будем указывать координаты фишки и квадрат расстояния до начала координат. Зелёным отмечены позиции, в которых выигрывает первый игрок. Дерево со­дер­жит все воз­мож­ные ва­ри­ан­ты ходов вто­ро­го игрока. Из него видно, что при любом от­ве­те вто­ро­го иг­ро­ка у пер­во­го име­ет­ся ход, при­во­дя­щий к победе.

26-3Решение

27-1 Условие На спут­ни­ке «Фотон» уста­нов­лен прибор, пред­на­зна­чен­ный для из­ме­ре­ния энер­гии кос­ми­че­ских лучей. Каж­дую ми­ну­ту при­бор передаёт по ка­на­лу связи не­от­ри­ца­тель­ное ве­ще­ствен­ное число — ко­ли­че­ство энергии, по­лу­чен­ной за по­след­нюю минуту, из­ме­рен­ное в услов­ных единицах. Временем, в те­че­ние ко­то­ро­го про­ис­хо­дит передача, можно пренебречь. Не­об­хо­ди­мо найти в за­дан­ной серии по­ка­за­ний при­бо­ра ми­ни­маль­ное про­из­ве­де­ние двух показаний, между мо­мен­та­ми пе­ре­да­чи ко­то­рых про­шло не менее 6 минут. Ко­ли­че­ство энергии, по­лу­ча­е­мое при­бо­ром за минуту, не пре­вы­ша­ет 1000 услов­ных единиц. Общее ко­ли­че­ство по­ка­за­ний при­бо­ра в серии не пре­вы­ша­ет 10 000. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной задачи.

27-1 Условие (продолжение) Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.

27-1 Условие (продолжение) А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А – 2 балла. Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.  Обязательно укажите, что программа является решением задания Б.

27-1 Условие (продолжение) Перед про­грам­мой ука­жи­те вер­сию языка и крат­ко опи­ши­те ис­поль­зо­ван­ный алгоритм. В пер­вой стро­ке задаётся число N — общее ко­ли­че­ство по­ка­за­ний прибора. Гарантируется, что N > 6. В каж­дой из сле­ду­ю­щих N строк задаётся одно не­от­ри­ца­тель­ное ве­ще­ствен­ное число — оче­ред­ное по­ка­за­ние прибора.   Пример вход­ных данных: 11 12 45 5 4 25 23 21 20 10 12 26   Программа долж­на вы­ве­сти одно число — опи­сан­ное в усло­вии произведение. Пример вы­ход­ных дан­ных для приведённого выше при­ме­ра вход­ных данных: 48

27-1 Решение Для по­стро­е­ния программы, эф­фек­тив­ной по времени, можно опре­де­лить для каж­до­го эле­мен­та вход­ных дан­ных ми­ни­маль­ное зна­че­ние от на­ча­ла дан­ных до этого эле­мен­та включительно. Затем нужно умно­жать каж­дый элемент, начиная с седьмого, на зна­че­ние этого минимума, взя­то­го на шесть эле­мен­тов раньше, и вы­брать наи­мень­шее из этих произведений. Пред­ло­жен­ный ал­го­ритм ре­а­ли­зо­ван в сле­ду­ю­щей про­грам­ме на ал­го­рит­ми­че­ском языке

27-1 Решение program c4; const s = 6; {требуемое рас­сто­я­ние между показаниями} Var N: integer; a: array[0..s - 1] of real; {хранение по­ка­за­ний прибора} {k-е вве­ден­ное число за­пи­сы­ва­ем в ячей­ку a[k mod 6]} a_: real; {ввод оче­ред­но­го показания} mn: real; {минимальное вве­ден­ное число} {не счи­тая 6 последних} m: real; {минимальное зна­че­ние произведения} i: integer; begin readln(N); { Пролог. Ввод пер­вых шести чисел} for i:=1 to s do begin readln(a_); a[i mod s] := a_ end; {Ввод осталь­ных значений, поиск ми­ни­маль­но­го произведения} mn := 1001; m := 1000 * 1000+1; for i := s + 1 to N do begin readln(a_); if a[i mod s] < mn then mn := a[i mod s]; if a_ * mn < m then m := a_ * mn; a[i mod s] := a_ end; writeln(m) end.

Успеха, Вам на экзамене!