С1 ЗАДАЧА1 С1 ЗАДАЧА 2 С2 С3С3 задача1 С3 задача2 С3 Задача 3 С4. - презентация

1 С1 ЗАДАЧА1 С1 ЗАДАЧА 2 С2 С3С3 задача1 С3 задача2 С3 Задача 3 С4

2 С1 Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно var x: real; begin readln(x) ; if x=-4 then if x>=8 then write('принадлежит') else write('не принадлежит') end.

3 1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 3, 9 и 15) принадлежат заштрихованным областям (B и D соответственно). Последовательно выполните следующее. В столбцах условий укажите «Да», если условие выполнится. «Нет», если условие не выполнится; «» (прочерк), если условие не будет проверяться; «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет». Область Условие 1 (X=-4) Условие 3 (x>=8) Программа выведет Область обрабатывается верно А В С D Е

4 if x=-4 then if x>=8 then write('принадлежит') else write('не принадлежит') Решение части 1

5 В программе else относится к последнему оператору if. if x=-4 then if x>=8 then write('принадлежит') else write('не принадлежит') Область Условие 1 (x=-4) Условие 3 (х>=8) Программа выведет Область обрабатывается верно А данет– В да нет С да нет D да Е нет–– Второе условие проверяется в программе только тогда, когда истинно первое, а третье – только тогда, когда истинны первые два. В остальных ячейках (если условие не проверяется) нужно ставить прочерк:

6 Область Условие 1 (x=-4) Условие 3 (х>=8) Программа выведет Область обрабатывается верно А данет–– В да нетне принадлежитнет С да нетне принадлежитда D принадлежитда Е нет––– Программы выводит какой-то ответ только тогда когда истинны первые два условия; в этом случае ответ зависит от истинности третьего условия if x=-4 then if x>=8 then write('принадлежит') else write('не принадлежит') -5 -4нет -3Нет -2Нет Нет 7 8Да 10Да 14Да 15

7 Исправленная программа на Паскале: if ((-4

8 Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). С1 задача 2 (Демо-версия) Pascal var x: real; begin readln(x); if x>=-3 then if x1 then write('не принадлежит') Else write ('принадлежит ') end. Программист торопился и написал программу неправильно

9 Область Условие 1 (x >= –3) Условие 2 (x 1) Программа выведет Область обрабатывается верно A B C D E 1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно). В столбцах условий укажите «Да», если условие выполнится. «Нет», если условие не выполнится; «» (прочерк), если условие не будет проверяться; «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите « » (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет».

10 Область Условие 1 (x >= –3) Условие 2 (x 1) Программа выведет Область обрабатывается верно AНет---нет Bда нет'принадлежит'ДА CДа не принадлежит'Нет DДа не принадлежит'НЕТ Eданет-- Решение В программе else относится к последнему оператору if. if x>=-3 then if x1 then write('не принадлежит') Else write ('принадлежит ') Второе условие проверяется в программе только тогда, когда истинно первое, а третье – только тогда, когда истинны первые два. В остальных ячейках (если условие не проверяется) нужно ставить прочерк: Программы выводит какой-то ответ только тогда когда истинны первые два условия; в этом случае ответ зависит от истинности третьего условия.

11 2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.) If ((x>= -3) and (x =5) and (x

12 Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести произведение элементов массива, которые имеют нечётное значение и делятся на 3. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого нечётно и кратно 3. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них. Исходные данные всегда подобраны так, что результат произведения не выходит за пределы объявленных типов данных. С2 Const N=30; var a: array [1..N] of longint; i, j, p: longint; begin for i := 1 to N do readln(a[i]); … end.

13 Русский (естественный) язык Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, J, P. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. … Решение даже если вы хорошо владеете программированием, сначала лучше (прежде всего, для себя) написать алгоритм на русском языке Присвоим переменной P начальное значение, равное 1. В цикле от 1-го элемента до 30-го находим остаток от деления элемента исходного массива на 2 и на 3. Если остаток от деления на 2 не равен 0 и остаток от деления на 3 равен 0, то считаем произведение данного элемента массива и значения переменной P или достаточно проверить, что остаток от деления на 6 равен 3. Результат умножения сохраняем в переменную P. Переходим к следующему элементу массива. После завершения цикла выводим значение переменной P

14 p := 1; for i := 1 to N do if (a[i] mod 20) and (a[i] mod 3=0) then p := p * a[i]; writeln(p);

15 С3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней. В начальный момент в куче было S камней, 1 S 21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

16 1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. Решение Последним ходом может быть «+1» или «*2». Выиграть последним ходом «+1» можно, если S = 21. Ходом «*2» можно выиграть из любой позиции при S > 10 (сюда входит и 21!). Поэтому ответ должен быть такой: «1а. Петя может выиграть за один ход при любом S > 10. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 22 камней.»

17 1 б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Решение Для ответа на этот вопрос нужно найти позицию, из которой все возможные ходы ведут к выигрышу за 1 ход, то есть к позиции, отмеченной в таблице как «В 1 ». Например, это позиция при S = 10: ход «+1» ведёт в выигрышную позицию S = 11, а ход «*2» ведёт в выигрышную позицию S = 20. Поэтому позицию S = 10 отметим в таблице как «×­ 1 » (проигрыш за 1 ход): Ответ на вопрос 1б должен быть такой: «1б. При S = 10 Петя не может выиграть в один ход, потому что при его ходе «+1» число камней в куче становится равно 11 (меньше 22), а при ходе «*2» число камней в куче становится равно 20 (также меньше 22). Других возможных ходов у Пети нет. Из любой позиции после одного хода Пети (это может быть 11 или 20), Ваня может выиграть своим первых ходом, удвоив количество камней в куче.»

18 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня Решение Пете, для того, чтобы гарантированно выиграть на втором ходу, нужно из начальной позиции перевести игру в проигрышную позицию, отмеченную знаком «× 1 ». Пока мы нашли одну такую позицию: S = 10. Петя может перевести игру в эту позицию из позиций S = 9 (ходом «+1») и S = 5 (ходом «*2») В таблице отмечаем эти положения как «В­­ 2 » – гарантированный выигрыш за 2 хода: Поэтому ответ должен быть такой: «2. Из позиций S = 9 и S = 5 Петя не может выиграть в один ход, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. При S = 9 ходом «+1» Пете нужно перевести игру в позицию S = 10, которая является проигрышной (см. ответ на вопрос 1б). При S = 5 Петя переводит игру в ту же позицию ходом «*2».»

19 3. Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в куче. Решение Нужно найти такую позицию, из которой оба возможных хода Пети ведут в позиции, отмеченные в таблице как «В­ 1 » (выигрыш в 1 ход) и «В­ 2 » (выигрыш в 2 хода). Например, это позиция S = 8, из которой можно «попасть» только в S = 9 («В 2 ») и S = 16 («В 1 »). Отмечаем эту позицию как «× 2 » – проигрыш в два хода: Поэтому ответ должен быть такой: «3. В позиции S = 8 у Вани есть выигрышная стратегия, которая позволяет ему выиграть первым или вторым ходом. Если Петя выбирает ход «+1», в куче становится 9 камней и Ваня выигрывает на 2-м ходу (см. ответ на вопрос 2). Если Петя выбирает ход «*2», Ваня выигрывает первым ходом, удвоив число камней в куче.»

20 Остается нарисовать дерево возможных вариантов игры из позиции S = 8. Для этого используем построенную таблицу: Здесь красным цветом выделены позиции, в которых игра заканчивается.

21 Обратите внимание, что на каждом шаге мы рассматриваем все возможные ходы Пети и только один лучший ход Вани. Например, в позиции S = 11 Ваня может сделать ход «+1» и получить 12 камней в куче, но тогда он проиграет (Петя следующим ходом удвоит число камней и получит 24 камня). Этот ход мы не рассматриваем, потому что мы хотим доказать, что у Вани есть выигрышная стратегия – ему достаточно хода «*2», после которого он выиграет. В то же время нужно рассмотреть все возможные ответы Пети, чтобы доказать, что у него нет шансов на выигрыш при правильной игре Вани. В этом суть теории игр – добиться лучшего результата в худшем случае, то есть при безошибочной игре соперника. Ещё один вариант – представить дерево в виде таблицы:

22 С3 2 Два игрока играют в следующую игру. Перед ними находится две кучки камней. В одной кучке находится 2 камня, в другой 3. У каждого игрока имеется бесконечное количество камней. Игроки ходят по очереди. В свой ход каждый игрок может либо удвоить количество камней в одной из кучек, либо добавить 3 камня в ка­кую-нибудь кучку. Игра заканчивается, когда общее количество камней в обоих кучках становится больше или равно 17. Если при этом в каждой кучке не больше 15 камней, то выигрывает первый игрок. Иначе выигрывает второй игрок. Кто выигрывает при безошибочной игре обоих игроков игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

23 Выигрывает второй игрок. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записано через запятую количество камней в первой и второй кучке, соот­ветственно, на каждом этапе игры. 1 ход2 ход3 ход4 ход Стартовая позиция 1-й игрок (все вари­ анты хода) 2-й игрок (выигрышный ход) 1-й игрок (все варианты хода, кроме непосредственно проигрышных) 2-й игрок (выигрышный ход, один из вариантов) 2,34,38,311,322,3 8,616,6 5,38,311,322,3 8,616,6 2,62,92,122,24 5,95,18 4,94,18 Таблица содержит все возможные варианты ходов первого игрока. Из нее видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

24 3 У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? Ответ обоснуйте.

25

26 Что нужно знать: символьная строка – это цепочка символов, которая может обрабатываться как единое целое для обращения к символу с номером i строки s используется запись s[i], это говорит о том, что строка – особый вариант массива, в котором хранятся символы знак сложения при работе с символьными строками означает сцепку, объединение двух строк в одну (добавление второй строки в конец первой), например: s := '123' + '456'; { получили '123456' } с помощью функции Ord можно получить код символа; цифры имеют коды от 48 (цифра 0) до 57 (цифра 9), например k := Ord('1'); { получили 49 } то же самое можно сделать с помощью преобразования типа (привести char к integer) k := integer('1'); { получили 49 } с помощью функции Chr можно сделать обратный переход: получить символ по его коду, например c := Chr(49); { получили символ '1' } то же самое можно сделать с помощью преобразования типа (привести integer к char) c := char(49); { получили символ '1' } для работы со строками в наиболее распространенных Паскаль-средах (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) используют стандартные функции (здесь s – это переменная типа string, символьная строка; n и r – целые переменные)

27 n := Length(s); записать длину строки s в целую переменную n s1 := Copy(s, 2, 5); записать в символьную строку s1 подстроку строки s, которая начинается с символа с номером 2 и состоит из 5 символов (важно – не со 2-го по 5-ый символ!) n := Pos('Вася', s);записать в целую переменную n номер символа, с которого в строке s начинается подстрока 'Вася' (если ее нет, в переменную n записывается 0); так же можно искать отдельные символы (важно: сначала указываем, что ищем, а потом – где) n := StrToInt(s); преобразовать строку s в целое число и записать результат в переменную n (PascalABC, Delphi) и процедуры Delete(s, 2, 5); удалить из строки s 5 символов, начиная со второго Insert('Вася', s, 3); вставить в строку s фрагмент 'Вася', начиная с третьего символа (между 2-м и 3-м) Val(s, n, r); преобразовать строку s в целое число и записать результат в переменную n; если при этом произошла ошибка, в переменной r будет номер ошибочного символа, если все нормально – ноль

28 С4 На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке сообщается число пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения М, которое не меньше 10, но не превосходит Каждая из следующих N строк имеет следующий формат:, где – строка, состоящая не более чем из 20 не пробельных символов; – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); имеет тот же формат. и, а также и разделены одним пробелом. Время освобождения больше времени сдачи. Сведения отсортированы в порядке времени сдачи багажа. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них. Требуется написать программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет выводить на экран для каждого пассажира номер ему предоставленной ячейки (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается.

29 Пример входных данных: 3 10 Иванов 09:45 12:00 Петров 10:00 11:00 Сидоров 12:00 13:12 Результат работы программы на этих входных данных: Иванов 1 Петров 2 Сидоров 1

30 var mas:array[ ] of integer; n,m,t1,t2,c,c1,code,x,y:integer; f:text;s:string; begin assign(f,input.txt');reset(f); readln(f,n);readln(f,m); {считываем кол-во людей и ячеек} while not eof(f) do begin {или for y:=1 to n do begin} readln(f,s); val(copy(s,length(s)-10,2),c,code); {первое время} val(copy(s,length(s)-7,2),c1,code); t1:=60*c+c1; {переводим в секунды} val(copy(s,length(s)-4,2),c,code); {второе время} val(copy(s,length(s)-1,2),c1,code); t2:=60*c+c1; {переводим в секунды} for x:=1 to m do begin if mas[x]

31 Каталог заданий ЕГЭ Тесты