Алгоритмизация и программирование (решение заданий части 3 ЕГЭ) Надточий Ирина Сергеевна, к.п.н., МОУ лицей 6 г.о.Тольятти, 2010 г. - презентация

1 Алгоритмизация и программирование (решение заданий части 3 ЕГЭ) Надточий Ирина Сергеевна, к.п.н., МОУ лицей 6 г.о.Тольятти, 2010 г.

2 Противоречие: несоответствие содержательного объема предмета и объема времени, отводящегося на его освоение. -математика1155 часов -русский язык560 часов -физика350 часов -информатика175 часов Подготовка по смежным экзаменационным дисциплинам именно на базовом уровне за 5-11 классы школы:

3 Ознакомление – повторение – закрепление – обобщение – контроль 11 заданий по этой теме из 32 заданий позволяют набрать 48% от максимальной суммы баллов. Тема: «Алгоритмизация и программирование»: В 8-9 классе по базовому курсу отводится 20 часов. В старших классах - 11 часов. Анализ результатов ЕГЭ: 30% учеников не приступали к выполнению 3 части ЕГЭ, 14% получили 0 баллов. Менее 1% выпускников показывают знание технологии программирования, требуемое большинством ВУЗов.

4 Перечень возможных алгоритмических задач: Нахождение всех корней заданного квадратного уравнения. Нахождение минимума и максимума 2, 3, 4 данных чисел без использования массивов и циклов. Запись натурального числа в позиционной СС с основанием меньшим или равным 10. Обработка и преобразование такой записи числа. Нахождение сумм, произведений элементов конечной числовой последовательности (или массива).

5 Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т.д.) Операции с элементами массива. Линейный поиск элемента. Вставка и удаление элементов в массиве. Перестановка элементов данного массива в обратном порядке. Суммирование элементов массива. Проверка соответствия элементов массива некоторому условию. Заполнение элементов одномерного и двумерного массива по заданным правилам. Нахождение второго по величине (второго макси- мального или второго минимального) значения в данном массиве за однократный просмотр массива.

6 Операции с элементами массива, отобранными по некоторому условию (например, нахождение мини- мального четного элемента в массиве, нахождение количества и суммы всех четных элементов в массиве). Слияние двух упорядоченных массивов в один без использования сортировки. Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке. Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку.

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

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

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

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

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

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

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

14 X

15 1) Пример исходных данных, при которых программа неверно решает поставленную задачу: x=1, y=0.5. Результатов два – «Точка не лежит внутри области» и «Точка лежит внутри области». На самом деле точка принадлежит области.

16 2) Возможно следующее исправление задачи: var x,y: real; begin readln(x,y); if x

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

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

19 Что нужно знать: массив – это набор однотипных элементов, имеющих общее имя и расположенных в памяти рядом; для обращения к элементу массива используют квадратные скобки, запись A[i] обозначает элемент массива A с номером (индексом) i; для обработки всех элементов массива используется цикл вида: for i:=1 to N do begin { что-то делаем с элементом A[i] } end;

20 По традиции нумерация элементов массива в Паскале обычно начинается с единицы, далее N обозначает размер массива (количество элементов). переменная i обозначает номер текущего элемента массива, она меняется от 1 до N с шагом 1, то есть мы проходим последовательно все элементы.

21 Матрица (двумерный массив) – это прямоугольная таблица однотипных элементов. Если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k. Каждая строка матрицы – это обычный (одномерный, линейный) массив; для того, чтобы обработать строку i в матрице из M столбцов, нужно использовать цикл, в котором меняется номер столбца k: for k:=1 to M do begin { что-то делаем с элементом A[i,k] } end;

22 Каждый столбец матрицы – это обычный (одномерный, линейный) массив; для того, чтобы обработать столбец k в матрице из N строк, нужно использовать цикл, в котором изменяется номер строки i: for i:=1 to N do begin { что-то делаем с элементом A[i,k] } end;

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

24 Const n=50; var c:array [1..n] of integer; max1, max2, min1, min2, i: integer; 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.

25 Пример 2. Условие задачи: Опишите на русском языке или одном из языков программи- рования алгоритм подсчета максимального количества подряд идущих совпадающих элементов в целочисленном массиве из 30 элементов. Решение: 1)сначала нужно понять задачу; предположим, что в массиве есть одинаковые элементы, стоящие рядом: )самая длинная цепочка стоящих рядом элементов в данном случае состоит из 4-х единиц (она выделена красным цветом); 3)нам нужно по крайней мере две переменных: для хранения номера текущего элемента (при обработке массива в цикле) и для хранения максимального количества идущих подряд элементов (обозначим ее kMax);

26 4)в целом (пока неточный) алгоритм может выглядеть так: пройти весь массив, подсчитывая для каждого элемента длину цепочки подряд идущих одинаковых чисел, если эта длина больше kMax, то записать ее в kMax; 5) отсюда сразу следует, что необходима еще одна перемен- ная (обозначим ее через k), показывающая для каждого элемента массива длину цепочки одинаковых чисел, которая заканчивается на этом элементе: k kmax )следующий шаг к решению: нужно понять, как изменять переменную k при проходе по массиву; можно сделать так: если очередной элемент равен предыдущему, счетчик k увеличиваем на единицу, а если не равен – записываем в него 1 (цепочка одинаковых чисел кончилась, началась новая, в ней пока один элемент);

27 7)при таком подходе проблема может возникнуть при просмотре первого элемента, потому что для него нет предыдущего; поэтому описанную выше процедуру будем в цикле применять ко всем элементам массива, начиная со второго (а не с первого); в самом начале программы запишем в k и kMax по единице – таким образом, мы вручную (без цикла) рассмотрели первый элемент массива; 8)теперь можно написать алгоритм на русском языке: Выделим две вспомогательные переменные, k и kMax, и запишем в каждую из них по единице. В цикле рассматриваем все элементы массива со второго до последнего, если очередной элемент равен предыдущему, увеличиваем k; если k > kMax, записываем в kMax значение k. В конце цикла в kMax окажется требуемое значение.

28 Const N =30; var A: array[1..N] of integer; i, k, kMax: integer; begin for i:=1 to N do readln(A[i]); { ввод массива } k := 1; { обрабатываем A[1] } kMax := 1; for i:=2 to N do begin { а теперь в цикле A[2]...A[N] } if A[i] = A[i-1] then { цепочка продолжается } k := k + 1 else k := 1; { цепочка закончилась } if k > kMax then kMax := k; end; writeln(kMax); end.

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

30 3)В цикле от второго элемента до конца массива: прибавляем элемент к сумме, а также сравниваем его с Max. Если он больше, заносим его значение в переменную Max. В противном случае сравниваем его с Min. Если он меньше, заносим его значение в переменную Min. 4)По окончании цикла вычисляем среднее арифметическое Max и Min, заносим его в переменную SM. 5)В переменную SA заносим частное от деления суммы элементов на количество элементов в массиве. Выводим разность SM - SA. Пример программы с учетом однократного прохода по массиву:

31 Const 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.

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

33 Const N=10; var a: array [1..N; 1..N] of integer; i, j, Max,Min: integer; 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]; if a[i,j]

34 Const N=10; var A: array [1..N; 1..N] of integer; i, k, Max,Min: integer; begin for i:=1 to N do for k:=1 to N do readln (a[i, k]); {Ввод массива} Min:=a[1,2]; Max:=a[1,2]; {ищем максимум и минимум выше главной диагонали:} for i:=1 to N-1 do for k:=i+1 to N do begin if a[i,k]>Max then Max:=a[i,k]; if a[i,k]

35 Const M=7; N=5; var A: array [1..M; 1..N] of integer; i,k,S : integer; Begin S:=0; For i :=1 to M do For k := 1 to N do begin readln(A[i,k]); S:=S+A[i,k]; end; Writeln (сумма=, S); end. Пример 5. Условие задачи: В двумерном массиве размерностью M х N найти сумму всех элементов.

36 Const M=7; N=5; var A: array [1..M; 1..N] of integer; i,k,S : integer; Begin For i :=1 to M do For k := 1 to N do readln(A[i,k]); For i := 1 to M do begin S:=0; For k := 1 to N do S:=S+A[i,k]; Writeln (сумма=, S); end; end. Пример 6. Условие задачи: В двумерном массиве размерностью M х N найти сумму элементов в каждой строке.

37 Const M=7; N=5; var A: array [1..M; 1..N] of integer; i,k,S : integer; Begin For i := 1 to M do begin S:=0; For k := 1 to N do begin readln(A[i,k]); S:=S+A[i,k]; end; Writeln (сумма=, S); end; end. Пример 6. Условие задачи: В двумерном массиве размерностью M х N найти сумму элементов в каждой строке.

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

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

40 Тип record структура (в Паскале она называется запись, record) – это сложный тип данных, который может включать в себя несколько элементов – полей; поля могут иметь различный тип. Записи в Паскале объявляются с помощью ключевого слова record; Например: в строке записано: Иванов 1993 м var person: record fio: string; g: integer; p: char end;

41 Что нужно знать: записи очень удобны для работы, когда все данные в целом представляют собой единый блок информации, например, данные об ученике; если не использовать записи, было бы нужно выделять в памяти отдельно символьную строку и отдельно целую переменную, причем эти данные внешне были бы никак не связаны, поэтому программа с записями часто получается логичнее и понятнее как для автора, так и для того, кто будет в ней разбираться.

42 Что нужно знать: для обращения к полям записи используют точку, например x.name означает поле name записи x можно сразу объявить массив записей: var Info: array[1..100] of record name: string; code: integer; end; это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом; в каждой структуре есть поля nаme и code; чтобы работать с полями записи с номером k используют обращения вида Info[k].name и Info[k].code

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

44 Const N=500; var a:array [1..N] of char; p:array[A..Я] of integer; i,M: integer; c:char; begin readln(M); for c := А to Я do p[c]:=0; for i:=1 to M do begin read(a[i]); 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.

45 Пример 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); end.

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

47 var p:record name: string; sum: integer; end; c: char; b: boolean; N, m, k, i: integer; 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; {признак того, что оценка не 2 или3} k:=0; {количество оценок 4 и 5} while not eoln do begin read(m); if m in [2,3] then b:=false else begin p.sum:=p.sum+m; k:=k+1 end; end; if b and (p.sum>4.5*k) and (c:=А) then writeln(p.name); end; end.

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

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

50 На что обратить внимание (советы выпускникам): внимательно читайте условие, убедитесь, что вы понимаете смысл каждой строчки; для каждой мелочи постарайтесь определить, зачем она добавлена в условие, что она дает для решения задачи, что ограничивает, что не разрешает делать; определите, какая именно информация из условия нужна для решения задачи, а какая – не нужна; определите, что именно требуется вывести на экран в результате работы программы; начинайте составлять программу с больших блоков, записывая ее сначала на псевдокоде, а потом уточняя детали;

51 На что обратить внимание: проверяйте крайние варианты (например, возможность выхода за границы массива); проверьте, правильно ли заданы (и заданы ли вообще) начальные значения для всех переменных; будьте внимательны, когда в массиве есть мертвые элементы, которые не нужно учитывать; проверяйте, что в этом случае ваши алгоритмы (например, поиск минимального элемента) работают правильно; проверьте, правильно ли расставлены операторные скобки begin-end, ограничивающие тело цикла; их обязательно нужно ставить, если в теле цикла несколько операторов;

52 На что обратить внимание: чтобы эксперту было легче понять программу (особенно, если она получилась нестандартной), пишите комментарии; объясняйте, что хранится в основных переменных; если это возможно, желательно работать только с целыми числами; этим вы избежите проблем, связанных с округлением и неточностью хранения дробных вещественных чисел в памяти компьютера.

53 За что снимают баллы: программа работает не для всех исходных данных, не обрабатывает некоторые частные случаи; неверно реализован алгоритм поиска минимального элемента, сортировки и т.п.; неэффективность алгоритма: 1)используется несколько проходов по массиву, когда достаточно одного; 2)лишний расход памяти ( используются дополнительные массивы или размер массива определен неверно); используются операции с вещественными числами, когда можно все решить в целых числах; переменная не описана или описана неверно;

54 За что снимают баллы: переменным не присвоены нужные начальные значения (например, не обнуляются счетчики) или присвоены неверные значения; нет вывода результата в конце программы; перепутаны знаки, логические операции or и and; применяется недопустимая операция, например, div или mod для вещественных чисел; неверно расставлены операторные скобки begin-end; в цикле for используется вещественная переменная (Паскаль); в цикле while или repeat не изменяется переменная цикла, из-за чего происходит зацикливание;

55 За что снимают баллы: синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов): чтобы получить 4 балла, при абсолютно верном решении нужно сделать не более одной синтаксической ошибки; 3 балла – до трех ошибок; 2 балла – до пяти; 1 балл – до семи ошибок.

56 Статистические данные взяты с сайта: Использованные материалы: 1. Андреева Е.В. Методика обучения основам программирования, 2006 г. 2. Сайт Константина Полякова. 3. Ровнягина Л. В., МОУ СОШ г.Темрюк. 4.Шумилина Н.Д., Изучение информатики или подготовка к ЕГЭ? (цикл статей в газете «Информатика. Первое сентября»). Источники заданий: 1.Демонстрационные варианты ЕГЭ гг. 2.Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. СПб: Тригон, Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, Зорина Е.М., Зорин М.В. ЕГЭ-2010: Информатика: Сборник заданий. – М.: Эксмо, 2009.