Чтобы решать задачи, нужно их решать.. Что нужно знать: правила построения программы на алгоритмическом языке, правила работы с переменными (объявление, - презентация

1 Чтобы решать задачи, нужно их решать.

2 Что нужно знать: правила построения программы на алгоритмическом языке, правила работы с переменными (объявление, ввод, вывод, оператор присваивания), ветвление – выбор одного из двух возможных вариантов действий в зависимости от значения некоторого логического выражения, на блок-схеме алгоритма ветвление изображается: Логическо е выражение Оператор-1Оператор-2 TrueFalse Логическ ое выражен ие Оператор-1 TrueFalse

3 If Then Else ; If Then ; Если логическое выражение принимает значение True, то выполняется Оператор-1, в противном случае – Оператор-2. Если логическое выражение принимает значение True, то выполняется Оператор-1, в противном случае – выполняется оператор идущий за условным оператором.. Пример If a = b Then a:=5 Else b:= a+10; If a = b Then a:=5;

4 в качестве Оператор-1 или Оператор-2 может стоять оператор ветвления: Логическое выражение Оператор-1 Оператор-2 TrueFalse If Then {Оператор-1} If Then Else Else ; Пример If a = b Then If a>5 Then a:=a-5 Else a:=a+5 Else b:= a+10;

5 в качестве Оператор-1 или Оператор-2 может стоять несколько операторов: Логическо е выражение Оператор-1 Оператор-2 TrueFalse Использование составного оператора (операторных скобок): begin- end If Then {Оператор-1} begin ; end Else ; Пример If a = b Then begin a:=a-5; b:=a+5 end Else b:= a+10;

6 основным вопрос этого задания – использование вложенных условных операторов; в тексте задания фрагмент программы записан без отступов или с неправильными отступами. Чтобы понять, как работает программа, нужно определить, к какому из условных операторов if относится часть else. Для этого используется правило: «else относится к ближайшему if» Пример if a = b then begin if a = c then c:=1; end else c:=0; a = c c:= 1 c:=0 TrueFals e a = b True Fals e

7 if a = b then if a = c then c:=1 else c:=0; a = c c:= 1 c:=0 TrueFalse a = b True False

8 в условных операторах можно использовать сложные условия, которые строятся из простых отношений (, >=, =, ) с помощью логических операций not («НЕ», отрицание), and («И», одновременное выполнение двух условий) и or («ИЛИ», выполнение хотя бы одного из двух условий),

9 в сложном условии существует приоритет выполнения действий: –выражение в скобках, –not, –and, –or, –отношения. операции равного приоритета выполняются последовательно слева направо.

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

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

12 Пример неправильно записанной задачи: 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. Результат – «х - любое», на самом деле – корней нет.

13 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.

14 Пример 2. Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (x, y – действительные числа) и определяется принадлежность этой точки заданной заштрихованной области (включая границы). Программист торопился и написал программу неправильно. var x,y: real; begin readln(x,y); if x*x+y*y>=4 then if x>= –2 then if y

15 Решение 1. Определим условие, которому должны отвечать точки, принадлежащие заштрихованной области. X Y Область Условие If x*x+y*y>=4 then write('принадлежит') else write('не принадлежит');

16 If x*x+y*y>=4 then If x>= –2 then write('принадлежит') else write('не принадлежит') else write('не принадлежит'); If x*x+y*y>=4 then If x>= –2 then If y

17 If x*x+y*y>=4 then If x>= –2 then If y= 0 then write('принадлежит') else write('не принадлежит') else write('не принадлежит') else write('не принадлежит') else write('не принадлежит'); Y= X X= 2

18 Полученную запись можно упростить, если использовать сложное логическое выражение: Мы получили ответ на второй вопрос. Для того, чтобы ответить на первый вопрос, представим исходный текст программы в структурированном виде: if (x*x+y*y>=4) and (x>= –2) and (y =0) then write('принадлежит') else write('не принадлежит'); var x,y: real; begin readln(x,y); if x*x+y*y>=4 then if x>= –2 then if y

19 В тексте программы три условных оператора, которые содержат три ветви Then и одну ветвь Else (принадлежит последнему условному оператору). Для наглядности представим текст программы в виде блок-схемы. X*X+Y*Y>=4 X>= 2 Y=4) и (y = –2) и (y

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

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

22 X

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

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

25 Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x, y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы. Программист торопился и написал программу неправильно. Вот она: var x,y: real; begin readln(x,y); if y = 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит') end. Последовательно выполните следующее: 1)Приведите пример таких чисел x, y, при которых программа неверно решает поставленную задачу. 2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы). 1) сначала лучше отложить в сторону программу и попытаться написать условие, которым должны отвечать точки, попавшие в выделенную область 2) заштрихованная область ограничена по координате, она находится -справа от оси, что равносильно условию (с учетом границы здесь и далее получаем нестрогие неравенства) -слева от первого максимума функции из математики мы знаем, что эта функция достигает максимума при поэтому получаем второе условие 3) заштрихованная область ограничена с двух сторон по координате : она находится -Ниже линии у=1, откуда следует третье условие -Выше линии у=sinx, что дает четвертое условие

26 4) итак, точка находится в заданной области, если все эти четыре условия выполняются одновременно; можно предположить, что в программе нужно использовать четыре вложенных условных оператора или один условный оператор, в котором четыре простых условия (отношения,,, связаны с помощью логической операции and («И», одновременное выполнение всех условий) 5) теперь смотрим на программу: здесь три (а не четыре!) вложенных условных оператора с простыми отношениями, поэтому явно какое-то условие не учтено; легко найти, что «забыли условие

27 6) оператор write('принадлежит') помещен внутрь всех трех условных операторов, то есть, он выполнится тогда, когда три (а не четыре!) условия истинны 7) отметим на рисунке область, где выполняются все нужные условия, кроме (красная зона); 8) для всех точек, которые находятся в «красной» зоне программа выдаст сообщение «принадлежит», хотя в самом деле эти точки не принадлежит заданной области; одна из таких точек имеет координаты 9) теперь выясним, когда программа выдает сообщение «не принадлежит» if y = 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит')

28 10) судя по записи «лесенкой», else относится к самому первому оператору if, однако в самом деле это не так; перед словом else нет end, поэтому ищем ближайший if: это самый внутренний оператор, правильная запись «лесенкой» выглядит так: if y = 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит') 11) этот фрагмент программы соответствует блок-схеме да нет принадлежит y >= sin(x) да x >= 0 да y

29 14) остается исправить эту программу; начнем с самого «лобового способа»: добавим в программу четвертый (вложенный) условный оператор, проверяющий условие и еще три блока else, чтобы выводить строку «не принадлежит» в том случае, когда хотя бы один из них не сработал: if x = sin(x) then write('принадлежит') else write('не принадлежит') else write('не принадлежит'); обратите внимание, что точка с запятой есть только после самого последнего оператора write, так как остальные стоят перед ключевым словом else, перед которым точка с запятой не ставится 15) хотя приведенный выше метод дает работоспособную программу, она получается слишком длинная и некрасивая для такой простой задачи; достаточно сказать, что оператор write('не принадлежит') повторяется в тексте 4 раза 16) более элегантное решение формулируется на словах так: «точка принадлежит области, если выполняются одновременно 4 приведенных выше условия, а иначе – не принадлежит»; а вот реализация на Паскале (приведем программу-ответ целиком): var x,y: real; begin readln(x,y); if (x >= 0) and (x

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

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

32 Программа на Паскале: 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]

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

34 Программа на Паскале: с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.

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

36 Программа на Паскале: с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.

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

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

39 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.

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

41 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.

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

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

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

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

46 Программа на Паскале: 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.

47 Пример 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);

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

49 Программа на Паскале: 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.

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

51 Программа на Паскале: 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.

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

53 Программа на Паскале: 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.

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