Методические подходы к обучению способам решения задачи 27 ЕГЭ по информатике 1 1) выявить специфику задания типа 27 ( что именно и при каких « стартовых. - презентация

1 Методические подходы к обучению способам решения задачи 27 ЕГЭ по информатике 1 1) выявить специфику задания типа 27 ( что именно и при каких « стартовых » условиях должен сделать учащийся ); 2) предложить краткое описание последовательности этапов решения задач типа 27; 3) определить требования к подготовке учащегося, необходимые для решения задач типа 27 4) рассмотреть и проанализировать критерии проверки задач типа 27; 5) рассмотреть подходы к выполнению учащимся каждого этапа решения задачи 27;

2 Для получения максимального балла от учащегося требуется : 2 1. уметь анализировать «накрученное» условие и представлять метод решения в виде формальной записи на языке программирования; 2. хорошо знать способы описания и обработки переменных целого, вещественно, строкового, логического типов данных (так, примеров описания строковых данных в КИМе нет) 3. обладать знаниями и умениями необходимыми для решения задания 25 плюс следующими: A.Слияние двух упорядоченных массивов в один без использования сортировки. B.Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке. C.Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку. 4. иметь достаточный опыт написания программ, чтобы «чувствовать» и исправлять возможные ошибки без использования компьютера.

3 Решение задачи 27 имеет следующие обязательные составляющие : 3 Описание используемых переменных Инициализация Организация ввода Организация обработки Организация вывода При оптимальном по времени решении задачи 27 организация ввода и обработки организуется параллельно, а не последовательно ( как в задаче 25). Тогда количество используемых переменных сводится к минимуму, а значит, программа будет еще оптимальна и по памяти.

4 Алгоритм решения задачи : 4 Анализ условия, определение цели. Выявление связей между искомым и вводимыми данными. Запись описания алгоритма решения задачи на естественном языке. Оформление программы на языке программирования, включающее в себя : описание переменных и их типов, инициализацию нужных переменных, организацию ввода и обработки, организацию вывода. Анализ программы, выявление ошибок на 2-3 подобранных самостоятельно тестах ( кроме данного в задаче ), коррекция.

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

6 Изменения критериев оценивания задания 27 А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А равна 2 баллам. 6

7 Изменения критериев оценивания задания 27 Критерии оценивания задания А 2 балла : 1. Правильно 2. Допускается до семи синтаксических и приравненных к ним ошибок пропущен или неверно указан знак пунктуации ( запятая, точка с запятой, скобки и т. д.); неверно написано или пропущено служебное слово языка программирования ; не описана или неверно описана переменная ; применяется операция, недопустимая для соответствующего типа данных. 3. Допускается до двух содержательных ошибок неверная инициализация при поиске минимального значения ; неверная обработка начальных элементов данных, которая может, например, привести к получению ошибочного ответа при 4 < N < 8; неточное определение границ массива, выход за границу массива ( например, описан массив с границами от 1 до 4, а реально используется от 0 до 3 или наоборот ); вычисленный индекс элемента массива на 1 отличается от верного ; используется знак < вместо <=, or вместо and и т. п. 7

8 Изменения критериев оценивания задания – изменения Критерии оценивания задания А 1 балл : Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. 0 баллов : Не выполнены критерии, позволяющие поставить 1 или 2 балла 8

9 Изменения критериев оценивания задания 27 Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти ( или хотя бы по одной из этих характеристик ). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных данных N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, равна 4 баллам. 9

10 Изменения критериев оценивания задания 27 Критерии оценивания задания Б 4 балла : 1. Программа правильно работает для любых соответствующих условию входных данных. 2. Эффективна по времени и по памяти. 3. Может содержать не более трёх синтаксических ошибок. 3 балла : 1. Программа правильно работает для любых соответствующих условию входных данных. 2. Эффективна по времени. 3. Может содержать не более пяти синтаксических ошибок. 4. Допускается наличие не более одной « содержательной » ошибки : неверная инициализация при поиске минимального значения ; неверная обработка начальных элементов данных ; неточное определение границ массива, выход за границу массива ; вычисленный индекс элемента массива на 1 отличается от верного ; используется операция < вместо <=, or вместо and и т. п. На 2 и, 1 и 0 баллов – критерии для задания А. 10

11 Изменения критериев оценивания задания 27 11

12 27: сложная задача на программирование 12 Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Количество элементов последовательности не превышает Напишите на любом языке программирования программу для решения поставленной задачи. Ваша оценка будет зависеть не только от правильности программы, но и от того, насколько она эффективна.

13 13 27: сложная задача на программирование Задача А (2 балла). Данные хранятся в массиве. var N: integer; a: array[ ] of integer; i, j, max: integer; begin readln(N); for i:=1 to N do read(a[i]); max:= 0; for i:= 9 to N do for j:= 1 to i-8 do if a[j]*a[i] > max then max := a[j]*a[i]; writeln(max) end. var N: integer; a: array[ ] of integer; i, j, max: integer; begin readln(N); for i:=1 to N do read(a[i]); max:= 0; for i:= 9 to N do for j:= 1 to i-8 do if a[j]*a[i] > max then max := a[j]*a[i]; writeln(max) end.

14 27: сложная задача на программирование 14 Задача Б (3 балла). Данные в массиве. ii-8 m a[i] накапливать ! max:= 0; m:= 0; for i:= 9 to N do begin if a[i-8] > m then m := a[i-8]; if m*a[i] > max then max := m*a[i]; end; max:= 0; m:= 0; for i:= 9 to N do begin if a[i-8] > m then m := a[i-8]; if m*a[i] > max then max := m*a[i]; end;

15 27: сложная задача на программирование 15 Задача Б (4 балла). i-8 x var a: array[1..8] of integer; храним в массиве for i:=1 to 8 do read(a[i]); Начальное заполнение массива: Продвижение: for i:=1 to 7 do a[i]:=a[i+1]; a[8]:= x; for i:=1 to 7 do a[i]:=a[i+1]; a[8]:= x; i Это очередь ! !

16 27: сложная задача на программирование 16 Задача Б (4 балла). const d = 8; { сдвиг }... { уже прочитали первые d штук } max:= 0; m:= 0; for i:=d+1 to N do begin read(x); if a[1] > m then m:= a[1]; if m*x > max then max:= m*x; for j:=1 to d-1 do a[j]:= a[j+1]; a[d]:= x; end; const d = 8; { сдвиг }... { уже прочитали первые d штук } max:= 0; m:= 0; for i:=d+1 to N do begin read(x); if a[1] > m then m:= a[1]; if m*x > max then max:= m*x; for j:=1 to d-1 do a[j]:= a[j+1]; a[d]:= x; end; a[1]x

17 27: сложная задача на программирование 17 Задача Б (4 балла). Без сдвига (очередь-кольцо) N-1 0 i aa[i mod d]:= data[i]; for i:=0 to d-1 do read(a[i]); for i:=d to N-1 do begin read(x); k:= i mod d; if a[k] > m then m := a[k]; if m*x > max then max := m*x; a[k]:=x; end; for i:=d to N-1 do begin read(x); k:= i mod d; if a[k] > m then m := a[k]; if m*x > max then max := m*x; a[k]:=x; end; 9101 k 1212

18 Задача 18 По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) R делится на 21. Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: Вычисленное контрольное значение: … Контроль пройден (или – Контроль не пройден) Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение.

19 19 Пример входных данных: Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: Контроль пройден По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) R делится на 21. Если такого числа R нет, то контрольное значение полагается равным 0. Напишите эффективную, в том числе по используемой памяти, программу, которая будет проверять правильность контрольного значения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение.

20 20 Произведение двух чисел делится на 21, если : один из сомножителей делится на 21 ( второй может быть любым ) либо ни один из сомножителей не делится на 21, причём один из сомножителей делится на 7, а другой – на 3. Поэтому программа, вычисляющая кодовое число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин : М 7 – самое большое число, кратное 7, но не кратное 3; M3 – самое большое число, кратное 3, но не кратное 7; M21 – самое большое число, кратное 21; М AX – самое большое число среди всех элементов последовательности, отличное от М 21 ( если число М 21 встретилось более одного раза и оно же является максимальным, то MAX = M21). После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений М 21*MAX и М 7* М 3. Словесное описание алгоритма решения задачи, предваряющее ее запись на языке программирования является обязательной частью решения задачи 27:

21 21 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. Количество чисел N известно, но может быть очень велико. все числа не превышают 1000 … R – произведение двух различных переданных элементов последовательности

22 22 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности 2) R делится на 21

23 23 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. readln(dat); if ((dat mod 7) = 0) and ((dat mod 3) > 0) and (dat > M7) then M7 := dat; if ((dat mod 3) = 0) and ((dat mod 7) > 0) and (dat > M3) then M3 := dat; if (dat mod 21 = 0) and (dat > M21) then begin if M21 > MAX then MAX := M21; M21 := dat end else if dat > MAX then MAX := dat;

24 Решение задачи на 2 балла из 4 возможных 24 Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве (ниже n – количество прочитанных чисел), и перебираются все возможные пары элементов последовательности. Например, так: max := 0; for i := 1 to n - 1 do for j := i + 1 to n do if ((a[i]*a[j]) mod 21 = 0) and ((a[i]*a[j]) > max) then max := a[i]*a[j];

25 25 Задача 27 На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие символы, отличные от. и букв a..z, во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать эффективную программу, которая будет печатать буквы, встречающиеся во входной последовательности, в порядке уменьшения частоты их встречаемости. Каждая буква должна быть распечатана один раз. Точка при этом не учитывается. Если какие-то буквы встречаются одинаковое число раз, то они выводятся в алфавитном порядке. Например, пусть на вход подаются следующие символы: batat. В данном случае программа должна вывести atb

26 Пояснение к обычному решению 26 Про­грам­ма чи­та­ет все вход­ные сим­во­лы до точки один раз, подсчи­ты­вая в мас­си­ве, хра­ня­щем 26 целых чисел, ко­ли­че­ство каж­дой из букв. Сами вход­ные сим­во­лы при этом не за­по­ми­на­ют­ся. В до­пол­ни­ тель­ный мас­сив, со­сто­я­щий из 26 сим­во­лов, за­но­сят­ся буквы от «а» до «z». Затем эле­мен­ты пер­во­го мас­си­ва сор­ти­ру­ют­ся по неубы­ва­нию любым ал­го­рит­мом сор­ти­ров­ки, па­рал­лель­но перестав­ля­ют­ся и эле­мен­ты вто­ро­го мас­си­ва (воз­мож­но использование од­но­го мас­си­ва за­пи­сей, со­сто­я­щих из двух полей). При этом эле­мен­ты с рав­ным чис­лом вхож­де­ний сим­во­ лов местами не ме­ня­ют­ся. Во вто­ром из от­сор­ти­ро­ван­ных мас­си­ вов про­пус­ка­ют­ся эле­мен­ты, ко­ли­че­ство ко­то­рых равно 0, осталь­ ные эле­мен­ты пе­ча­та­ют­ся под­ряд.

27 Немного об особенностях символьного типа 27 Переменная типа char может принимать значения из определенной упорядоченной последовательности символов. Переменная этого типа занимает 1 байт и принимает одно из 256 значений кода ASCII Обычно символы, имеющие экранное представление, записывают в явном виде, заключив в апострофы (например, 'A', 'b', '*'). Две стандартные функции позволяют поставить в соответствие данную последовательность символов множеству целых неотрицательных чисел (порядковым номерам символов последовательности). Эти функции называются функциями преобразования: ord(ch) – выдает номер символа (нумерация с нуля), chr(i) – выдает i-ый символ из таблицы символов. Пример. ord(H) выдает номер символа Н в последовательности всех символов, используемых транслятором. chr(15) выдает 15-ый символ этой последовательности.

28 28 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end;... i:=0; while a[i]=0 do i:=i+1; for j:=i to 25 do write( b[j]); end. repeat read(c); … until c=.; … repeat read(c); … until c=.; … Обычное решение

29 29 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end;... i:=0; while a[i]=0 do i:=i+1; for j:=i to 25 do write( b[j]); end. repeat read(c); a[ord(c)- ord(a)]:=a[ord(c)- ord(a)]+1; until c=.; … repeat read(c); a[ord(c)- ord(a)]:=a[ord(c)- ord(a)]+1; until c=.; … Обычное решение

30 30 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end; repeat read(c); a[ord(c)-ord(a)]:=a[ ord(c)-ord(a)]+1; until c=.;... i:=0; while a[i]=0 do i:=i+1; for j:=25 downto i do write( b[j]); end. for i:=1 to 25 do begin for j := 0 to 24 do if a[j] > a[j +1] then begin k:= а [j]; с :=b[j]; а [j]:= а [j+1]; b[j]:=b[j+1]; a[j + 1] :=k; b[j+1] :=c end; for i:=1 to 25 do begin for j := 0 to 24 do if a[j] > a[j +1] then begin k:= а [j]; с :=b[j]; а [j]:= а [j+1]; b[j]:=b[j+1]; a[j + 1] :=k; b[j+1] :=c end; Обычное решение

31 Эффективное решение. Var a:array ['a'..'z'] of integer; d,b,c:char; Begin For c:='a' to 'z' do a[c]:=0; Read(c); While c<>'.' do Begin a[c]:=a[c]+1; Read(c); end; For d:='a' to 'z' do Begin b:='a'; For c:='a' to 'z' do If a[c]>a[b] then b:=c; If a[b]=0 then Break; a[b]:=0; Write(b); End; End.