Подготовка к ЕГЭ - 2010. Задание C4 (вариант 1) Заключительный этап олимпиады по астрономии проводился для учеников 9-11-х классов, участвующих в общем. - презентация

1 Подготовка к ЕГЭ

2 Задание C4 (вариант 1) Заключительный этап олимпиады по астрономии проводился для учеников 9-11-х классов, участвующих в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 50 баллов. Жюри олимпиады решило признать победителями и призерами 45% участников. По положению, в случае, когда у последнего участника, входящего в 45%, оказывается количество баллов такое же, как и у следующих за ним в итоговой таблице, решение по данному участнику и всем участникам, имеющим с ним равное количество баллов, определяется следующим образом: все участники признаются призерами, если набранные ими баллы больше половины максимально возможных; все участники не признаются призерами, если набранные ими баллы не превышают половины максимально возможных. Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая по результатам олимпиады будет определять, какой минимальный балл нужно было набрать, чтобы стать победителем или призером олимпиады. На вход программе сначала подается число участников олимпиады N. В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате: где – строка, состоящая не более, чем из 20 символов, – строка, состоящая не более, чем из 15 символов, – число от 9 до 11, – целое число от 0 до 50 набранных участником баллов. и, и, а также и разделены одним пробелом. Пример входной строки: Иванов Петр Программа должна выводить минимальный балл призера. Гарантируется, что хотя бы одного призера по указанным правилам определить можно.

3 Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла) Ответ Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от 0 до 50 количество участников, набравших тот или иной балл. Путем просмотра этого массива с конца (от 50 баллов) определяется число участников, заведомо попадающих в число 45% лучших (добавление всех участников, набравших следующий балл приводит к выходу за 45%). Последний балл, который набрали не менее 1 участника, запоминается. Если хотя бы один из следующих участников также попадает в 45%, то проверяется, что он и следующие, набравшие столько же баллов, набрали более половины баллов, в этом случае они все добавляются к числу победителей и призеров и их балл является искомым. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда все участники набрали различные баллы, каждый балл кто-то набрал и 45% от числа участников – целая величина).

4 Пример правильной и эффективной программы на языке Паскаль: var cnt: array[0..50] of integer; c: char; i, k, N, b, S, minb: integer; begin for i:=0 to 50 do cnt[i]:=0; readln(N); for i:=1 to N do begin repeat read(c); until c=' '; {считана фамилия} repeat read(c); until c=' '; {считано имя} readln(k,b); cnt[b]:=cnt[b]+1; end; 01234… …0000 S:=0; b:=50; while (S + cnt[b])*100

5 var cnt: array[0..50] of integer; c: char; i, k, N, b, S, minb: integer; begin for i:=0 to 50 do cnt[i]:=0; readln(N); for i:=1 to N do begin repeat read(c); until c=' '; {считана фамилия} repeat read(c); until c=' '; {считано имя} readln(k,b); cnt[b]:=cnt[b]+1; end; S:=0; b:=50; while (S + cnt[b])*1000 then minb:=b; b:=b-1 end; {определены те, кто наверняка стал призером} if (S+1)*10025 then minb:=b end; writeln(minb); end.

6 Указания по оцениваниюБаллы Программа работает верно для любых входных данных произвольного размера и находит ответ, не сохраняя все входные данные или баллы участников в массиве, размер которого равен числу участников. Программа просматривает входные данные один раз, заполняя во время считывания массив размерностью от 0 до 50 для хранения количества участников, набравших то или иное количество баллов. Искомые величины находятся путем однократного просмотра этого массива. При определении минимального балла рассматриваются только баллы, которые кто-то набрал. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). 4 Критерии оценивания

7 Программа работает верно, но все входные данные (или баллы участника) запоминаются в массиве, размер которого совпадает с количеством участников, или входные данные считываются несколько раз. Возможно, используется сортировка всех баллов участников и/или алгоритм поиска минимума, просматривающий баллы всех призеров. Допускается наличие от одной до трех синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных. Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, не относящаяся к алгоритму решения задачи, например, ошибка в принципиально верно организованном вводе данных. 3 Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма содержатся 1–2 ошибки (выход за границу массива, перевод символов в числа, используется знак < вместо

8 Программа, возможно, не всегда верно определяет количество победителей и призеров и, соответственно, минимальный балл у призеров. Возможно, считается, что каждый балл кто-то набрал. При использовании сортировки допущены ошибки в ее реализации. Допускается до 4 различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения двух баллов. Допускается наличие от одной до семи синтаксических ошибок, описанных выше. 1 Задание не выполнено или выполнено неверно0 Максимальный балл4

9 C4 (высокий уровень, время – 60 мин) Тема: Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из строк). Что нужно знать: символьная строка – это цепочка символов, которая может обрабатываться как единое целое для обращения к символу с номером 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' }

10 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) для работы со строками в наиболее распространенных Паскаль-средах (используют стандартные функции (здесь s – это переменная типа string, символьная строка; n и r – целые переменные)

11 Delete(s, 2, 5); удалить из строки s 5 символов, начиная со второго Insert('Вася', s, 3); вставить в строку s фрагмент 'Вася', начиная с третьего символа (между 3-м и 4-м) Val(s, n, r); преобразовать строку s в целое число и записать результат в переменную n ; если при этом произошла ошибка, в переменной r будет ноль, если все нормально – ненулевое значение и процедуры

12 структура (в Паскале она называется «запись», record) – это сложный тип данных, который может включать в себя несколько элементов – полей; поля могут иметь различный тип записи в Паскале объявляются с помощью ключевого слова record ; в простейшем случае можно выделить память под одну запись так: var x: record name: string; code: integer; end; эта запись состоит из двух полей: символьной строки name и целого числа code записи очень удобны для работы, когда все данные в целом представляют собой единый блок информации, например, данные об ученике; если не использовать записи, было бы нужно выделять в памяти отдельно символьную строку и отдельно целую переменную, причем эти данные внешне были бы никак не связаны, поэтому программа с записями часто получается логичнее и понятнее как для автора, так и для того, кто будет в ней разбираться для обращения к полям записи используют точку, например 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

13 Сложность алгоритмов: при увеличении в 2 раза размера массива данных количество операций тоже увеличивается примерно в 2 раза (для больших N) если в одном алгоритме решения задачи используется несколько циклов от 1 до N, а во втором – только один цикл, то алгоритм с одним циклом, как правило, эффективнее если в программе используется два вложенных цикла, в каждом из которых N шагов), то это увеличивает сложность в квадрат. Эту сложность имеют простые способы сортировки массивов: метод «пузырька», метод выбора иногда встречаются алгоритмы сложности (три вложенных цикла от 1 до N), при больших N они работают медленнее, чем любой алгоритм квадратичной сложности, то есть, менее эффективны

14 Пример задания: На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и, а также и разделены одним пробелом. Пример входной строки: Иванов П.С. 57 Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.

15 Как правильно понимать условие? на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную итак, сначала вводится количество записей в файле N, а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать номер школы стоит после второго пробела в строке « – не более чем двузначный номер» – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99! …

16 что означает выражение «как можно более эффективная программа»? прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь в программе не выполняются никакие лишние действия используемые алгоритмы имеют минимальную сложность (см. выше) расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

17 Решение: по условию, единственная информация, которая нам нужна в итоге для вывода результата – это количество участников по каждой школе так как номер школы состоит (по условию!) не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99) поэтому можно ввести массив C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкой- счетчиком, в которой накапливается число участников от школы с номером k; сначала во все элементы этого массива записываются нуль (обнуление счетчиков): for k:=1 to 99 do C[k]:=0; во многих системах программирования на Паскале все глобальные переменные автоматически обнуляются, и таким образом, этот цикл ничего не дает; однако на всякий случай нужно продемонстрировать эксперту, который будет проверять часть С вашей работы, что вы понимаете суть дела («счетчик необходимо сначала обнулить»)

18 основной цикл обработки вводимых строк можно записать на псевдокоде так: for i:=1 to N do begin { читаем очередную строку } { определяем номер школы k } C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end; поскольку данные вводятся в виде символьной строки, нужно выделить в памяти переменную s типа string для чтения очередной строки будем использовать оператор readln остается понять, как выделить из строки номер школы; по условию он закодирован в последней части строки, после второго пробела; значит, нужно найти этот второй пробел, вырезать из строки весь «хвост» после этого пробела, и преобразовать его из символьного формата в числовой

19 чтобы найти первый пробел и «отрезать» первую часть строки с этим пробелом, можно использовать команды p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); первая команда определяет номер первого пробела и записывает его в целую переменную p, в вторая – записывает в строку s весь «хвост», стоящий за этим пробелом, начиная с символа с номером p+1; длина хвоста равна Length(s)-p, где Length(s) – длина строки; поскольку нас интересует часть после второго пробела, эти две строчки нужно повторить два раза, в результате в переменной s окажется символьная запись номера школы, для преобразования ее в форму числа можно использовать функцию Val: Val(s, k, r); эта процедура преобразует символьную строку s в числовое значение k; с помощью переменной r обнаруживается ошибка: если раскодировать число не удалось

20 таким образом, основной цикл выглядит так: for i:=1 to N do begin readln(s); { читаем очередную строку } {выделяем часть после второго пробела } p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); { определяем номер школы k } Val(s, k, r); C[k] := C[k] + 1; { увеличиваем счетчик k- ой школы } end;

21 дальше стандартным алгоритмом определяем в массиве C минимальный элемент Min, не учитывая нули (школы, из которых не было участников): Min := N; for k:=1 to 99 do if (C[k] 0) and (C[k]

22 остается «собрать» программу, чтобы получилось полное решение; максимальное количество школ мы задали в виде константы LIM: const LIM = 99; var C:array[1..LIM] of integer; i, p, N, k, r, Min: integer; s:string; begin readln(N); for i:=1 to N do begin readln(s); { читаем очередную строку } p := Pos(' ', s); { выделяем часть после второго пробела } s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); { определяем номер школы k } Val(s, k, r); C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end; Min := N; for k:=1 to LIM do if (C[k] 0) and (C[k]

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

24 проверьте, правильно ли расставлены операторные скобки begin-end, ограничивающие тело цикла; их обязательно нужно ставить, если в теле цикла несколько операторов при использовании функции Pos не забывайте, что первый параметр – что ищем (образец), а второй – где ищем чтобы эксперту было легче понять вашу программу (особенно, если она получилась «нестандартной»), пишите комментарии; объясняйте, что хранится в основных переменных если это возможно, желательно работать только с целыми числами; этим вы избежите проблем, связанных с округлением и неточностью хранения дробных вещественных чисел в памяти компьютера

25 Спсибо за внимание!