г. Темрюк Ровнягина Лидия Вячеславовна, МОУ СОШ 3 Чтобы решать задачи, нужно их решать.

Задание С1 Уровень сложности: повышенный Максимальный балл: 3 Время на выполнение: 30 минут. Решаемость – 48 % Рекомендации по подготовке учащихся: 1)Решить задачу математически. 2) Написать соответствующую программу. 3) Провести тестирование программы для различных наборов исходных данных 4) Предложить учащимся вариант программы с ошибками 5)Учащиеся исправляют ошибки в предложенной программе 6)Оценивают: можно ли в условном операторе использовать составное условие с применением AND или OR

Пример 1. Условие задачи: Требовалось написать программу, которая решает уравнение ax=b относительно х. Учитывается, что а может принимать любые значения, в том числе и 0. Программист сделал в программе ошибки. Последовательно выполните задания: 1)Приведите пример таких чисел a и b, при которых программа неверно решает поставленную задачу. 2)Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы.

Пример неправильно записанной задачи: var a,b,x: real; begin readln(a,b); if a0 then writeln(b/a:0:2) else if b0 then writeln(x – любое) else writeln(корней нет) end. 1) Пример исходных данных, при которых программа неверно решает поставленную задачу: a=0, b=5. Результат – «х - любое», на самом деле – корней нет.

2) Возможно следующее исправление задачи: var a,b,x: real; begin readln(a,b); if a0 then writeln(b/a:0:2) else if b=0 then writeln(x – любое) else writeln(корней нет) end.

Пример 2. Условие задачи: Требовалось написать программу, которая определяет, лежит ли точка A(x, y) в треугольной области, изображенной на рисунке. (Внутри понимается в строгом смысле – точка не может лежать на границе области). В результате выдается соответствующее текстовое сообщение Программист сделал в программе ошибки. Последовательно выполните задания: 1)Приведите пример таких чисел x и y, при которых программа неверно решает поставленную задачу. 2)Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. 3)Укажите, как можно доработать программу, чтобы она содержала логические операции AND или OR

Программа на Паскале: var x,y: real; begin readln(x,y); if x

X

1) Пример исходных данных, при которых программа неверно решает поставленную задачу: x=1, y=0.5. Результат – «Точка не лежит внутри области», на самом деле точка принадлежит области. 2) Возможно следующее исправление задачи: var x,y: real; begin readln(x,y); if x

3) Пример возможной доработки задания с использованием логических функций: var x,y: real; begin readln(x,y); if (x 0) then writeln(точка лежит внутри области) else writeln(точка не лежит внутри области); end.

Задание С2 Уровень сложности: высокий Максимальный балл: 2 Время на выполнение: 30 минут. Решаемость – 35 % Примеры возможных задач: суммирование массива; проверка упорядоченности массива; слияние двух упорядоченных массивов; сортировка; поиск заданной подстроки в последовательности символов; поиск корня делением пополам; поиск наименьшего делителя целого числа; разложение целого числа на множители (простейший алгоритм); умножение двух многочленов.

Пример 1. Условие задачи: В двумерном массиве размерностью 10 х 10 найти произведение максимального и минимального элементов, лежащих выше главной диагонали. Решение: Для хранения значений максимума и минимума будем использовать переменные max и min соответственно. В теле цикла проверяем: лежит ли элемент выше главной диагонали. Если да, будем сравнивать этот элемент массива с уже найденным максимумом. И если элемент окажется больше, то в переменную max занесем значение этого нового элемента. В противном случае сравниваем этот же элемент с уже найденным минимумом, и если он окажется меньше минимума, то в переменную min занесем значение этого элемента. В конце найдем произведение min и max.

Программа на Паскале: const n=10; var a: array [1..n; 1..n] of integer; i, j, max,min: integer; n: byte; begin {Ввод массива} for i:=1 to n do for j:=1 to n do readln (a[i, j]); min:=a[1,2]; max:=a[1,2]; {ищем максимум и минимум выше главной диагонали} for i:=1 to n-1 do for j:=i+1 to n do begin if a[i,j]>max then max:=a[i,j] else if a[i,j]

Пример 2. Условие задачи: В массиве из 50 элементов, заполненном произвольными целыми числами, найдите два числа, произведение которых максимально. Вложенные циклы не используйте. Решение: Из условия задачи очевидно, что искомые числа – это либо два максимальных элемента массива, либо два минимальных отрицательных элемента массива. Для промежуточного хранения двух минимумов и двух максимумов элементов массива С будем использовать целочисленные переменные min1, min2, max1, max2. В теле цикла сначала найдем искомые два минимума или два максимума, а затем выясним, произведение какой пары чисел больше.

Программа на Паскале: сonst n=50; var c:array [1..n] of integer; max1, max2, min1, min2, Sum, I: integer; i, j: real; begin for i:=1 to n do readln(c[i]); max1:=c[1]; max2:=c[1]; min1:=c[1]; min2:=c[1]; for i := 2 to N do begin {находим два максимума и два минимума} if c[i]>max1 then begin max2:=max1; max1:=c[i]; end else if c[i] > max2 then max2:=c[i]; if c[i] max1*max2 then write(min1,,min2) else write(max2,,max1); readln end.

Пример 3. Условие задачи: Опишите на русском языке или одном из языков программирования алгоритм вычисления разности между средним арифметическим максимального и минимального значений элементов заданного целочисленного массива из 30 элементов и средним арифметическим всех элементов этого массива Решение: Введем целочисленные переменные Max, Min и Sum, в которые будем заносить соответственно значения максимального и минимального элемента в просмотренной части массива, а также накапливать сумму значений элементов. Присвоим им в качестве начального значение первого элемента массива. Также определяем две переменные SM и SA типа real для хранения средних значений. В цикле от второго элемента до конца массива: прибавляем элемент к сумме, сравниваем его с Max, если он больше, заносим его значение в переменную Max. В противном случае сравниваем его с Min, если он меньше, заносим его значение в переменную Min. По окончании цикла вычисляем среднее арифметическое Max и Min, заносим его в переменную SM. В переменную SA заносим частное от деления суммы элементов на количество элементов в массиве. Выводим разность SM - SA. Пример алгоритма с учетом однократного прохода по массиву:

Программа на Паскале: сonst N=30; var a:array [1..N] of integer; Max, Min, Sum, I: integer; SM, SA: real; begin Max := a[1]; Min := a[1]; Sum := a[1]; for I := 2 to N do begin readln(a[i]); Sum := Sum + a[i]; if a[i] > Max then Max := a[i] else if a[i] < Min then Min := a[i]; end; SM := (Max + Min)/2; SA := Sum/N; writeln(SM - SA); end.

Основные ошибки при выполнении задания: неверное описание переменных (массивов) (2 % учащихся); неверный тип данных (7 % учащихся); неверная организация ввода-вывода данных (12 % учащихся); в организации работы циклов (неверное определение граничных значений счетчиков циклов) (7% учащихся); в организации работы с массивами (выход за пределы массива при организации циклов) (6 % учащихся); 5% ошибок в расстановке операторных скобок. 7% учащихся не знакомы с массивами и решают задачу, используя просто входную последовательность чисел; не выполнена инициализация переменных у 6% учащихся (не заданы или неверно заданы первоначальные значения переменных, например, при поиске максимального (минимального) элемента массива).

Задание С3 Уровень сложности: высокий Максимальный балл: 3 Время на выполнение: 30 минут. Решаемость – 48 % Пример 1. Условие: Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого, расстояние от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

1 ход2 ход3 ход4 ход Стартов ая позиция I-й игрок (все варианты хода) II-й игрок I-й игрок (все варианты хода) II-й игрок (выигрышн ый ход) 5,2 5,6 (61) 8,6(100) 11,6(157); 8,9(145); 8,10(164)14,6 5,9(106) 8,9(145);5,12(169);5,138,13 5,10(125) 8,10(164);5,13(194); 5,14(221) 11,10 5,5 (50) 8,5(89) 11,5(146);8,8(128);8,914,5 5,8(89) 8,8(128);5,11(146);5,1211,8 5,9(106) 8,9(145);5,12(169);8,10(164)11,9 8,2 (68) 8,5 Те же варианты третьего - четвертого ходов. 8,6 11,2 Вывод: выигрывает второй игрок при любом ходе первого игрока. Первый ход второго игрока может быть 5,6-8,6 или 5,5-8,5.

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

1 ход2 ход3 ход4 ход Стартов ая позиция I-й игрок (все варианты хода) II-й игрок (выигрыш- ный ход) I-й игрок (все варианты хода) II-й игрок (выигрышный ход) 2,3 4,3 (25) 4,6(52) 8,6(100) 16,6 4,12(160) 4,24 4,8(80)4,16 4,5(41) 8,5(89)16,5 4,10(116) 4,20 4,7 (65) 4,14 2,6 (40) 4,6(52) Повторяют предыдущие варианты третьего - четвертого ходов. 2,5 (29) 4,5(41) Вывод: выигрывает второй игрок при любом ходе первого игрока. Первый ход второго игрока может быть 4,3 - 4,6 или 2,5 - 4,5.

Основные ошибки при выполнении задания: неверно подсчитаны координаты точки 2% учащихся; 1,5 % учащихся не учла изменения условия задачи (решали на «камушки»); неверно указали выигравшего игрока (19%); неверно указали первый ход выигравшего игрока (7%); 1,5% учащихся в приведенном решении явно не выделили ответ на вопрос задачи (не указано, кто выигрывает, какой первый ход он должен сделать; 5% - не указали все варианты ходов играющих. 23% - стратегия игры описана неверно или отсутствует вовсе (бездоказательно).

Задание С4 Уровень сложности: высокий Максимальный балл: 4 Время на выполнение: 60 минут. Решаемость – 22 % Процедуры и функции для обработки текстовых файлов: assign – сопоставляет переменную и внешний файл; reset – открыть файл на чтение; rewrite – открыть файл на запись; аppend – открыть файл для дописывания информации; close – закрыть открытый файл; eof – проверяет, достигнут ли конец файла; eoln – достигнут ли при чтении конец строки; SeekEof – проверяет, достигнут ли конец файла, пропуская разделители; SeekEoln – проверяет, достигнут ли конец строки при чтении из файла, пропуская разделители; read (readln) – считывает одно или более значений из файла в одну или более переменных; write (writeln) – записывает одно или более значений в файл;

Тип record Например: в строке записана: Иванов 1993 м var person: record fio: string; g: integer; p: char end;

Пример 1. Обработка символьных величин: Текст на русском языке записан в массиве a[ ] of char. Помимо русских букв в нём встречаются пробелы и знаки препинания. В массиве p[А..Я] of integer необходимо записать сведения о том, сколько каких букв встречается в этом тексте. При подсчете строчные и прописные буквы не различаются. На вход программы подается значение n

Программа на Паскале: var a:array [1..N] of char; p:array[1..33] of integer; i: integer; c:char; begin readln(N); for c := А to Я do p(c):=0; for i:=1 to N do if a[i] in [A..Я,а..я] then begin c:=upcase(a[i]); p(c):=p(c)+1; end; for c := А to Я do writeln(c, -,p(c)) end.

Пример 2. Обработка символьных величин: Определить, сколько букв содержит самое длинное слово во введенной строке символов. На вход программы подается строка, состоящая не более чем из 255 символов. Слова разделены одним или несколькими пробелами. Вывести искомое число. Решение: использование признака конца слова (пробел). readln(s); s:=s+ ; max:=0 k:=0; for i:=1 to length(s) do begin if s[i] then k:=k+1 else begin if k>max then max:=k; k:=0; end; writeln(max);

Пример 3. Обработка записей: На вход программы подаются сведения о результатах экзаменов выпускников 11-х классов школы. В первой строке вводится количество выпускников N. Сведения о каждом выпускнике имеют формат: Здесь - строка, состоящая не более чем из 20 символов; - строка, состоящая не более чем из 15 символов; - номер класса и буква; - строка, содержащая оценки за экзамены выпускника, причем количество оценок у учащихся может быть различным.,,, разделены одним пробелом. Напишите программу, которая будет выводить фамилии и имена тех выпускников 11 А класса, у которых нет двоек и троек и средний балл больше, чем 4,5.

Программа на Паскале: var p: record name: string; sum: integer; end; c: char; n, m, k, i: integer; b: boolean; begin readln(n); for i:=1 to n do begin p.name:=; repeat read(c); p.name:=p.name+с; until c:= ; repeat read(c); p.name:=p.name+с; until c:= ; repeat read(c); until c:= ; p.sum:=0; b:=true; n:=0; while not eoln do begin read(m); if m in [2,3] then b:=false else p.sum:=p.sum+m; n:=n+1 end; if b and p.sum>4.5*n and c:=А then writeln(p.name); readln; end; end.

Пример 3. Обработка записей при чтении из файла: Сведения о результатах экзаменов выпускников 11-х классов школы записаны в файле input.txt. Сведения о каждом выпускнике имеют формат: Здесь - строка, состоящая не более чем из 20 символов; - строка, состоящая не более чем из 15 символов; - номер класса и буква; - строка, содержащая оценки за экзамены выпускника, причем количество оценок у учащихся может быть различным.,,, разделены одним пробелом. Запишите в файл output.txt фамилии и имена тех выпускников 11 А класса, у которых нет двоек и троек и средний балл больше, чем 4,5.

Программа на Паскале: var p: record name: string; sum: integer; end; c: char; n, m, k, i: integer; b: boolean; input, output: text begin assign(v,input); reset (v); assign(o,output); rewrite(o); repeat p.name:=; repeat read(v,c); …… while not seekeoln do ……… readln(v); end; until seekeof(v); close(o) end.

Пример 4. Обработка записей: На вход программе передается число N. Затем идет N строк, участников олимпиады разных школ, следующего формата:. Номер школы не более чем двухзначное число. Требуется написать программу, которая выведет номер школы (школ), с которых в олимпиаде участвовало больше всего учеников.

Программа на Паскале: var s : array[1.. 99] of integer; { Количество учеников с i-той школы } n, i, sn, max : integer; { N, i, номер школы, макс. кол-во учеников } c : char; { для хранения «лишней» информации } begin for i := 1 to 99 do s[i] := 0; readln(n); max := 0; for i := 1 to n do begin repeat read(c); until c = ' ';{ Пропуск фамилии} repeat read(c); until c = ' '; { Пропуск инициалов } readln(sn); { Считывание школы } s[sn] := s[sn] + 1; if s[sn] > max then max := s[sn]; end; if max 0 then begin for i := 1 to 99 do begin if s[i] = max then writeln(i); end; end.

Использованные ресурсы: Список использованной литературы: 1. Андреева Е.В. Методика обучения основам программирования, 2006 г. 2. А. Шень Программирование: теоремы и задачи, М.: МЦНМО, 2004.