Pascal ABC - система программирования на языке Паскаль, используемая для эффективной подготовки учащихся средних школ к олимпиадам по программированию. [6]

Язык Pascal был создан в начале 70-х годов прошлого столетия выдающимся специалистом в области компьютерной науки Никлаусом Виртом как язык для изучения программирования. С методической точки зрения Pascal действительно хорошо подходит на роль учебного языка. Программы на Pascal легко читаются, а один из важнейших принципов современного программирования - удобочитаемость - более важна, чем краткость кода.

Язык Паскаль считается одним из лучших языков именно для начального обучения программированию. Однако, среда Borland Pascal, ориентированная на MS DOS, устарела, а среда Borland Delphi с ее богатыми возможностями сложна для начинающего программиста. Так, попытка начинать обучение с написания событийной программы в Borland Delphi, вызывает у обучаемого массу сложностей и приводит к ряду неправильно сформированных навыков.

Система Pascal ABC используется для обучения школьников программированию и подготовки к олимпиадам. Большое количество заданий по каждому разделу позволяет каждому учащему предоставить индивидуальное задание. Использование электронного задачника позволяет увеличить количество учащихся, которые могут успешно принять участие в олимпиадах по завершении изучения курса.

Система обучения, основанная на языке Delphi Pascal, позволяет осуществить плавный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию. Многие концепции в Pascal ABC сознательно упрощены, что позволяет использовать их на более ранних этапах обучения. Простейшие событийные программы также можно писать без объектов, пользуясь лишь процедурными переменными. Даже в консольных программах можно создавать таймеры и звуки, которые реализованы не в виде объектов.

В системе Pascal ABC школьник может выполнять так называемые проверяемые задания, обеспечивающие постановку задачи со случайными исходными данными, контроль операций ввода-вывода, проверку правильности решения, а также ведение протокола решения задач.

Проверяемые задания реализованы в виде электронного задачника по программированию Programming Taskbook, содержащего 1000 задач по программированию разного уровня сложности (от простейших задач до задач на файлы, указатели и рекурсию) а также в виде исполнителей Робот и Чертежник, предназначенных для быстрого обучения основам программирования школьников средних классов.

По использованию языков программирования на всероссийской олимпиаде 2011 года имеется такая информация:

Всего участников было 225. 218 участников использовали только один язык программирования. 7 участников использовало Паскаль и C++ одновременно (подсчет проведен по тому языку, который они использовали для решения большего числа задач).

Вот результат:

C++: 120 (53%)

Паскаль: 104 (46%)

Visual Basic: 1 (меньше 0.5%)

Если брать данные только по победителям олимпиады (16 человек): C++: 13 (81%)

Паскаль: 3 (19%)

Данные только по призерам олимпиады, которые не стали победителями (85 человек) такие:

C++: 52 (61%)

Паскаль: 33 (39%)

В Казахстане в марте прошел первый тур дистанционной Республиканской олимпиады по математике и информатике. Как сообщает Анна Шатерникова [7] учащиеся 10-11-х классов показали достаточно высокий уровень подготовки. Олимпиада, организованная Международным IT-Университетом для казахстанских школьников, это один из первых шагов по внедрению в Казахстане интерактивной системы обучения e-Learning. Дистанционный формат проведения мероприятия позволил охватить все регионы страны -- данные технологии не требуют больших затрат и вложений, для участия школьникам было достаточно иметь лишь выход в интернет и зарегистрироваться на сайте олимпиады.

До этого дистанционные олимпиады, в которых могли принять участие школьники, в Казахстане не проводились. Первый опыт проведения дистанционной олимпиады показал, что среди казахстанских школьников интерес к подобной форме электронного обучения очень высок -- опробовали свои силы в решении олимпиадных задач свыше 2500 человек. Участники выполняли задания в режиме онлайн, у каждого из них был свой индивидуальный ID-номер, который позволял им иметь доступ к задачам. Итоговый результат, свои ошибки и итоги всего тура школьники могли видеть сразу же по окончании исходного времени. Как отметили организаторы, наиболее высокие показатели продемонстрировали школьники из регионов. В ходе второго тура ребята, соревнующиеся в области информатики, могли на выбор решать задачи на трех языках программирования -- C++, Java, Pascal. Победители олимпиады получили гранты на обучение в Международном университете информационных технологий.

«Запуская этот проект, мы рассчитывали оценить уровень знаний школьников и создать базу своих потенциальных абитуриентов, однако разработанный формат тестирования вполне может стать своего рода учебно-методическим модулем для других вузов при проведении подобного предварительного тестирования поступающих. Недавно в своем послании народу глава государства поставил задачу, чтобы к 2015 году 50% организаций образования использовали электронное обучение, а к 2020 году их численность должна возрасти до 90%. И это -- требование времени, поскольку современные формы обучения необходимы для выполнения тех задач, которые сегодня решает экономика страны. На сегодняшний день электронное обучение становится наиболее востребованным способом получения новых знаний», -- отметил ректор IT-университета Дамир Шыныбеков.

В соответствии с планами организаторов, подобные дистанционные олимпиады будут проводиться ежегодно, а форма их проведения будет совершенствоваться. Такой подход позволит выявить талантливых ребят еще со школьной скамьи и станет своего рода отправной точкой для формирования интерактивной системы обучения в республике.

Однако, для того, чтобы успешно участвовать в таких соревнованиях, школьники должны:

- быть обучены языкам программирования;

- уметь решать задачи по программированию разного уровня сложности;

- иметь доступ в интернет.

Проводя подготовку школьников, необходимо учитывать предпочтения по языкам программирования, на которых решают задачи на соревнованиях мирового уровня, необходимо уже сегодня приступать к осваиванию языка С++. Именно этот язык со временем станет наиболее популярным и в нашей стране. Конечно эффективным обучение программированию на С++ станет возможным тогда, когда преподаватели овладеют этим языком на высоком и качественном уровне. И не отдельные преподаватели, а большинство.

C++ -- компилируемый статически типизированный язык программирования общего назначения. Поддерживая разные парадигмы программирования, сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником -- языком C, -- наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «C++» происходит от языка C, в котором унарный оператор ++ обозначает инкремент переменной.

Являясь одним из самых популярных языков программирования, C++ широко используется для разработки программного обеспечения. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (например, видеоигры). C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#.

При создании C++ Бьёрн Страуструп стремился сохранить совместимость с языком C. Множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико -- отчасти благодаря тому, что синтаксис C++ был основан на синтаксисе C.

В математических классах школ Республики Казахстан по учебному плану, в соответствии с Государственным общеобязательным стандартом образования (ГОСО) программирование изучается с 8-го или 9-го класса, при этом во многих школах уже используется язык С++. Постепенно происходит отказ от изучения языка Паскаль - не подходит ввиду отсутствия подходящих реализаций данного языка, а также ввиду его несовременности, небогатых средствах, как самого языка, так и стандартной библиотеки. По тем же причинам не подходит и язык Бейсик, который тоже меньше изучают в специализированных классах.

Кириенко Д.П. в своей статье «Язык программирования PYTHON - современный язык для обучения” [8] в последние годы все более популярным становится язык программирования Python [9], который во всем мире широко используется как для обучения, так и в промышленном программировании. В феврале 2011 года Python занял четвертое место (после Java, C и C++) в рейтинге популярности языков программирования TIOBE Programming Community Index [10]. Интерес к языку Python растет и в нашей стране, но в школах Казахстана по-прежнему преимущественно используется Бейсик и Паскаль.

Можно отметить следующие достоинства языка Python:

1. Понятность языка выше, чем у Паскаля и Бейсика. Простые программы записываются в несколько строк, не нужны инструкции, не имеющие непосредственного отношения к алгоритму (например, int main()).

2. Простой и лаконичный синтаксис. Как правило, программа на языке Питон записывается короче, чем на C++, Паскале, Бейсике, но при этом без ущерба для понятности кода (как это свойственно языку C++).

3. Свободная и кроссплатформенная реализация.

4. Интерпретируемая архитектура языка упрощает написание, запуск и отладку программ.

5. Современность языка, наличие в нем высокоуровневых структур данных (списки, множества, ассоциативные массивы, длинная арифметика).

6. Наличие средств объектно-ориентированного и функционального программирования.

7. Наличие богатой библиотеки, позволяющей легко разрабатывать графические приложения, web-приложения и т.д.

Таким образом, язык Python лучше традиционных для школы языков Бейсик, Паскаль и С++ подходит как для начального обучения программированию, так и для построения профильных курсов.

Важен также выбор среды разработки, которых для языка Python существует достаточно много. Сравнив около двух десятков различных сред разработки, рекомендуем использовать в школе Wing IDE 101 -- бесплатную учебную версию кроссплатформенной среды Wing IDE [11]. Для удобства учащихся, автор выполнил перевод основной части интерфейса этой среды на русский язык. Возможно также использование и стандартной среды IDLE, входящей в стандартный дистрибутив языка, хотя она менее удобна.

Существуют, конечно, и недостатки, мешающие распространению языка Python:

1. Небольшое количество русскоязычной учебной и методической литературы.

2. Небольшое быстродействие программ на языке Python.

Для школ, не использующих собственную тестирующую систему, можно порекомендовать сайт [12], содержащий большое число задач самого разного уровня и автоматическую тестирующую систему, поддерживающую язык Python и доступную всем пользователям. Из литературы можно порекомендовать [13].

Часто приходится слышать возражение от учителей информатики - «Python нельзя использовать на олимпиадах». Это неверно. Множество языков программирования, допустимых на олимпиадах, определяется организатором конкретной олимпиады и в последние годы число олимпиад, на которых допускается использование языка Python, растет. Например, на всех олимпиадах по информатике, проводимых в г. Москве, разрешается использовать Python, это относится также к Всероссийской командной олимпиаде по программированию и Открытой олимпиаде по программированию. А так, как казахстанские школьники достаточно активно участвуют в Открытой олимпиаде и других соревнованиях, проходящих в России и других странах, рассматриваемый язык программирования необходимо тоже изучать. Есть статистические данные, что число участников олимпиад и других соревнований, использующих язык программирования Python, растет с каждым годом.

Python является хорошей заменой для Бейсика, Паскаля и C++ в школе.

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

3. Проведение турнира в учреждении образования (школе)

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

Одна из задач, стоящих перед преподавателями информатики в это время: сделать все возможное, чтобы интерес у учащихся не пропал, и появилось желание не только играть на компьютере, но и изучать его технические характеристики, знакомиться с различными языками программирования.

Для учащихся 5 - 6 классов преподаватели информатики могут в рамках предметной недели или на постоянной основе проводить турниры по решению элементарных задач, открытым или закрытым тестам в форме:

· Командной олимпиады;

· Викторины;

· Марафона.

При проведении этих мероприятий необходимо строго следить за выполнением большинства правил поведения, присущих мероприятиям такого типа. Единственное, чем такие мероприятия будут отличаться от турниров для старшеклассников - набором задания. Все же для школьников 5 - 6 классов нужно использовать задания по информатике, а не по программированию. Для каждой возрастной группы могут быть подготовлены задания:

4-5 классы - 60 заданий;

6-8 классы -70 заданий;

9-11 классы - 100 заданий.

В первой части заданий даны три варианта ответов под буквами А), Б), В). Участник должен выбрать верный, по его мнению, ответ и занести в соответствующий бланк. Вторая часть заданий предполагает самостоятельную формулировку ответа, которая также заносится в бланк. На выполнение всего объема заданий дается 60 минут. Каждый верный ответ первой части оценивается в 1 балл. Во второй части заданий для 9-11 классов предусмотрены дополнительные баллы за трудность. Победителям присуждаются 1, 2, 3 места.

Если проводится разовое мероприятие, итоги подводятся сразу и обязательно награждаются победители. В случае постоянно действующей игры, подводятся промежуточные итоги, определяются лидеры турнира, а награждение проводится на последней игре.

Преподавателям информатики необходимо взять на заметку результаты мониторинга методистов математики, физики Костанайского городского управления образования, проведенного в конце 90-ых годов. Школьники, «засветившиеся» на аналогичных турнирах по этим предметам, чаще всего оказывались в последующем (т.е. в старших классах) победителями и призерами олимпиад городских, областных и республиканских.

3.1 Правила проведения олимпиад по информатике

Прежде, чем продолжить разговор о турнирах для школьников, прокомментируем наиболее важные правила проведения олимпиад по информатике. Многие из этих правил справедливы также и для большинства других видов турнирных соревнований по информатике, программированию.

1. Олимпиада проводится в два тура. Продолжительность каждого тура 5 часов. На каждом из туров для решения задач участнику предоставляется персональный компьютер типа IBM PC со следующим программным обеспечением: Turbo Pascal, Borland C++ (может быть и другое ПО, в зависимости от условий проведения олимпиады).

Из этого пункта становится ясно, что, во-первых, оба тура олимпиады, так называемые, практические. Во-вторых, для решения задач предлагается использовать лишь один из двух предусмотренных правилами языков программирования. Такое положение полностью соответствует международной практике, хотя на российских олимпиадах соблюдается не всегда строго. Basic часто исключают из числа официальных языков программирования олимпиады или конкурса, так как желание программировать только на нем высказывают очень небольшое число участников олимпиад высокого уровня, при профессиональной разработке программ он практически не используется, кроме того, решение задач с использованием этого языка иногда затруднено по сравнению с Pascal и C. Заранее объявляя об ограничениях на использование программного обеспечения, жюри и оргкомитет олимпиады способствуют практике изучения тех языков программирования в казахстанских школах, которые позволят ребятам добиваться не только успехов в различных соревнованиях, но и некоторым из них стать высокими профессионалами в области информатики и программирования. По мнению многих преподавателей информатики, программистов - практиков, именно язык программирования Pascal, как никакой другой, позволяет за короткий срок отлаживать довольно сложные программы, что особенно важно в условиях практического тура любой олимпиады, но и не менее значимо при изучении информатики в школе. Использование языка C (C++) на олимпиаде стоит приветствовать лишь тогда, когда участник владеет им почти в совершенстве, практически не допуская ошибок при записи решения задачи на C, часть из которых невозможно обнаружить на этапе компиляции программы. Кроме того, при программировании на C могут возникнуть сложности с настройкой компилятора, а в режиме олимпиады даже минута, потраченная не на собственно решение задач, может сказаться на результатах участника. Хотя, справедливости ради стоит сказать, что на международной олимпиаде процент участников, использующих язык программирования C (C++) достаточно высок, причем многие из них выступают более чем успешно, что опять же свидетельствует о высокой квалификации таких школьников, а размер кода программ на C (не следует путать с размером исполняемого файла) часто меньше кода на языке Pascal. В заключение заметим, что предоставляемое на олимпиадах программное обеспечение (операционная система, тип и версия компиляторов, среда программирования) со временем естественно может изменяться.

2. На каждом из туров участникам будет предложено решить несколько задач. Вопросы по условиям задач можно задавать только в течение первого часа тура. Вопросы следует задавать только в письменном виде и формулировать их так, чтобы на них можно было ответить “да” или “нет”.

Такая практика сложилась исторически и применяется на международных олимпиадах. Строгое соблюдение данного пункта правил иногда вызывает у ряда участников некоторые сложности. Так, школьникам зачастую тяжело именно в начале тура пытаться понять нюансы в формулировках сразу всех задач. Кроме того, часто вопросы по условию возникают лишь тогда, когда участник приступил к решению той или иной задачи. Поэтому немаловажным является умение с первого раза внимательно прочитать условие любой задачи, выделяя не ясные для себя места в тексте. Умение грамотно сформулировать вопрос, допускающий один из двух вариантов ответа, также зачастую у школьников отсутствует. Заметим, что при ответе на большинство задаваемых вопросов члены жюри используют фразу “без комментариев”. Это означает, что либо ответ на вопрос все же содержится в формулировке задачи и его следует искать самостоятельно, либо вопрос фактически касается уже способов ее решения и жюри не комментирует различные соображения участников по этому поводу.

3. Во время тура не допускается использование личных дискет, калькуляторов, электронных записных книжек, пейджеров, мобильных телефонов, а также учебной литературы и личных записей, сделанных до начала тура.

Подобные ограничения ставят всех участников олимпиады во время тура в равные условия и способствуют выявлению действительно наиболее талантливых ребят. Хотя на ряде соревнований использование специальной литературы допускается, что соответствует практике профессиональной работы ученого, инженера или программиста, в ходе турниров среди школьников такие ограничения вводятся.

4. Не забывайте периодически сохранять свои решения. В случае возникновения сбоев в работе компьютера и программного обеспечения необходимо срочно обратиться к дежурному преподавателю, который должен письменно зафиксировать сбой и сообщить о нем в жюри. По решению жюри вам может быть добавлено время, потраченное на восстановление работоспособности компьютера.

Комментарии тут, как говорится, излишни. Справедливости ради следует заметить, что подобные ситуации на олимпиадах высокого уровня крайне редки и возникают, в основном, в результате ошибочных действий самих участников или же вызваны ошибками в их же программах, например, связанными с некорректным обращением к оперативной памяти.

5. В решениях категорически запрещается:

-- использовать расширенную память;

-- использовать ассемблерные вставки;

-- создавать файлы и каталоги во время работы программы;

-- читать данные откуда-либо, кроме как из входного файла и записывать их куда-либо, кроме выходного файла;

-- читать и записывать вектора прерываний;

-- производить любые другие действия, нарушающие работу проверяющей системы во время тестирования.

Собственно говоря, последнее из приведенных ограничений во многом объясняет и наличие всех остальных. Кроме того, в случае правильного решения задач, увеличивать скорость работы соответствующих программ путем использования ассемблера нет необходимости, то же самое касается и создания вспомогательных файлов.

6. Для решения разных задач могут использоваться разные языки программирования. По каждой задаче на проверку должны быть сданы два файла -- исходный текст решения и соответствующий ему исполняемый файл (файл с расширением exe). Если программа написана на языке C или C++, то она должна быть скомпилирована в модели памяти large. Ваша программа не должна использовать созданные вами внешние модули. После окончания тура и сдачи работы вносить какие-либо изменения в текст решения не допускается. Файлы с решениями могут быть скопированы на личную дискету участника дежурным преподавателем после окончания тура.

Из данного правила следует, что проверка решения задачи производится в основном путем тестирования исполняемого файла, созданного участником во время тура. Однако жюри оставляет за собой право перекомпилировать решения участников, в исключительных случаях это делается по просьбе школьников с разрешения жюри во время тестирования. Текст же решения с целью оценки используемых в нем алгоритмов жюри не анализируется, проверка осуществляется путем запуска программы на различных тестах. Так было далеко не всегда, однако в последнее десятилетие это стало нормой проведения всех практических туров олимпиад по информатике и программированию различного уровня. Достаточно строгим является правило, согласно которому текст программы после окончания тура исправлениям не подлежит, даже если ошибки в программе незначительны (иногда требуется исправить всего один символ) или задача практически решена, но нарушен формат выходных данных. В противном случае довольно сложно определить, какие же именно исправления можно считать допустимыми. В последние годы такое правило неуклонно соблюдается и практически не вызывает возражений со стороны как участников, так и их руководителей. Ограничение же на модель памяти при использовании языка программирования C является искусственным и введено лишь потому, что данная модель памяти наиболее близка к модели памяти языка Turbo Pascal, что опять же ставит участников в равные условия при решении задач. На международных олимпиадах такое ограничение отсутствует. Копирование решения участником на собственную дискету в ряде случаев позволяет ему вместе с руководителем найти ошибки и разобраться в особенностях работы программы до окончания олимпиады. Это существенно снижает количество подаваемых в жюри апелляций.

7. Проверка решений осуществляется после окончания тура и проводится в присутствии участника (а по желанию и руководителя). По результатам тестирования заполняется лист проверки с результатами по каждому тесту. Ваша программа на одном и том же тесте должна всегда выдавать одинаковые результаты. Если с результатами проверки участник не согласен, то он вносит свои замечания в лист проверки.

Проверка решения в присутствии участника говорит об открытости работы жюри на этапе тестирования. Такой подход снимает множество вопросов относительно полученных за решение той или иной задачи баллов. Поэтому его применение можно рекомендовать для олимпиад любого уровня, начиная со школьной олимпиады. На последней, а также районной олимпиаде, участники зачастую получают за решение той или иной задачи нулевые баллы просто потому, что их решение просто не удалось запустить или файл с решением оказался не найденным. А ошибки в названиях файлов с решениями, входными и выходными данными, например на школьной олимпиаде, не должны оказаться для ребят фатальными. Но определить, что причины неработоспособности программы именно в этом, зачастую можно только лишь с помощью ее автора. Требование же стабильности работы программы имеет следующий смысл. Различные результаты работы программы на одном и том же тесте в большинстве случаев объясняются либо ошибками в ее работе (например, если значения каких-либо переменных в программе явным образом не проинициализированы, то работа исполняемого файла зависит от того, чем было заполнено содержимое используемой программой при запуске оперативной памяти). Либо ошибка в использовании датчика случайных (а на самом деле псевдослучайных) чисел. Причем правилами олимпиады использование случайных чисел как таковых не возбраняется. Просто программа должна применять датчик так, чтобы на одних и тех же входных данных, генерировалась последовательность из одних и тех же случайных чисел. Например, в языке Turbo Pascal этого легко добиться, если не использовать в программе процедуру randomize. Кроме того, генератор псевдослучайных чисел можно запрограммировать и самостоятельно. При нарушении указанного правила жюри оставляет за собой право запустить программу несколько раз и засчитать худший из показанных ею результатов.

8. Решения участников проверяются на компьютерах с одинаковой тактовой частотой, возможно не совпадающей с тактовой частотой компьютеров, предоставленных в их распоряжение на соревнованиях. При тестировании будет доступно не менее 350 килобайт динамической памяти. Для сравнения быстродействия тестирующего компьютера с используемым при выполнении заданий участникам во время тура предоставляется специальная программа, которая на тестирующем компьютере работает ровно 5 - 10 секунд.

Конечно, такое правило является вынужденным и объясняется лишь тем, что оргкомитету очень трудно предоставить участникам олимпиады порядка 50 одинаковых компьютеров. Хотя на международной олимпиаде такая задача решается. При отладке решения следует учитывать, что эталонная по времени работы программа позволяет лишь приблизительно оценить ожидаемое время работы программы участника на тестирующем компьютере. Но обычно время тестирования любой задачи как минимум в два раза превышает действительно необходимое время для работы программы с оптимальным решением этой задачи на любом из тестов. Напомним, что максимально допустимое время работы программы на одном тесте входит в текст условия задачи.

3.2 Турниры школьников среднего и старшего возраста

Любые внеурочные мероприятия должны способствовать развитию интеллектуальных способностей, конкретизируя знания в определенных образовательных областях, развивать быстроту реакции и сообразительность.

Организаторы турниров достигают этой цели, решая следующие задачи:

- создают условия для формирования у каждого школьника опыта индивидуальных достижений, опыта успеха в реализации своих способностей;

- работают над формированием образно-аналитического мышления;

- способствуют повышению интеллектуально-творческой активности учащихся;

- поощряют побуждение ребенка к расширению познавательных интересов, эмоциональному, эстетическому, интеллектуальному совершенствованию.

Начиная с седьмого класса необходимо для участников составлять задания так, чтобы это были задания и по информатике, и по программированию. Примерный перечень заданий показан в приложении 4. В этом случае можно использовать различные типы мероприятий.

На первом, самом массовом этапе это может быть марафон. Количество участников на этом этапе не ограничено, участвовать могут все желающие. Марафон - отборочный этап турнира.

Из победителей первого, отборочного этапа, формируются команды, которые примут участие в командной олимпиаде. Это могут быть команды, сформированные случайным образом. Методик, позволяющих выполнить формирование команд таким образом, описано в литературе достаточно много. Предлагаем воспользоваться, например, методиками американского тренера Роберта Лукаса [14].

Методики, предлагаемые эти автором сами по себе очень увлекательны, почти все в игровой форме, стимулирующие мозг и побуждающие участников к активному общению. Например, при входе в аудиторию каждый участник выбирает из стоящей у входа вазы фишку (игрушку, карандаш, ручку, цветной стикер и т.д.), цветовая гамма которых такова, что по завершении входа в аудиторию Вы предлагаете участникам найти «свою» команду по цвету фишек. Можно предложить еще такой способ формирования команд. На стене (доске) прикрепить стикеры-пазлы с написанными на каждом по одной букве. Буквы подобраны заранее таким образом, чтобы из них можно было сложить термины информатики (программирования). Термины должны содержать одинаковое количество букв. Заранее, чтобы несколько упростить выполнение задачи школьникам, Вы можете им сообщить, из скольких букв состоят подобранные Вами термины.

После того, как формирование команд завершено, можно приступать непосредственно к проведению командной олимпиады, правила которой уже были описаны выше.

Необходимо помнить, что и марафон, и командную олимпиаду желательно проводить в быстром темпе и не более 60 минут. Оптимальный вариант 45 - 50 минут непосредственно самого мероприятия. Если игра затягивается, школьники устают, им становится не интересно.

Проводит игру ведущий (педагог, методист, старшеклассник). Ведущий представляет игроков и членов жюри, знакомит с правилами, озвучивает вопросы и счет игры.

Для каждой возрастной группы предлагается определенное количество заданий:

2-3 классы - 50 заданий;

4-5 классы - 60 заданий;

6-8 классы -70 заданий;

9-11 классы - 101 задание.

В первой части заданий даны три варианта ответов под буквами А), Б), В). Участник должен выбрать верный, по его мнению, ответ и занести в соответствующий бланк. Вторая часть заданий предполагает самостоятельную формулировку ответа, которая также заносится в бланк. На выполнение всего объема заданий дается 60 минут. Каждый верный ответ части оценивается в 1 балл. Во второй части заданий для 9-11 классов предусмотрены дополнительные баллы за трудность. Победителям присуждаются 1, 2, 3 места. Победители 1 этапа участвуют во 2 этапе конкурса.

По завершении командной олимпиады, за ходом которой внимательно следят члены жюри (педагоги, методисты, старшеклассники, родители) определяются победители и награждается грамотами, подарками.

Самый серьезный этап проведения турнира - олимпиада в личном зачете, в которой принимают участие школьники старших классов, победители предыдущих этапов турнира. Желательно проводить этот этап в соответствии с правилами проведения олимпиад, которые описаны в пункте 3.1.

Учитывая, что в турнире принимают участие школьники с разным уровнем изучения языков программирования, задачи необходимо подбирать разноплановые. Например:

Задача 1.

Вычислить значение суммы

S = 1/1! + 1/2! + ... + 1/k!

Задача 2.

Написать программу определения количества шестизначных 'счастливых' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

Задача 3.

Написать программу определения количества 2*N -значных билетов, у которых сумма первых N десятичных цифр равна сумме N последних десятичных цифр; при этом N -произвольное натуральное число.

Задача 4.

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Пример. N=3, K=2

Возможные пути:

1,1,1

1,2

2,1

Ответ: 3.

Задача 5.

Покупатель имеет купюры достоинством A(1), ...,A(n), а продавец - B(1), .. ,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно.

Задача 6.

Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]<=M[2]<=...<=M[N].

Найти первое натуральное число, не представимое суммой никаких элементов этого массива, при этом сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз.

Задача 7.

У покупателя есть n монет достоинством H(1),..., H(n). У продавца есть m монет достоинством B(1),...,B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).

Задача 8.

Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]<=M[2]<=...<=M[N].

Написать алгоритм выплаты заданной суммы S минимальным количеством купюр достоинством M(1), ..., M(N).

Задача 9.

По матрице A(N,N) построить матрицу B(N,N). Элемент B(I,J) равен максимальному из элементов матрицы А принадлежащем части, ограниченной справа диагоналями, проходящими через A(I,J).

Задача 10.

Вводится матрица a(m,n) из 0 и 1. Найти в ней квадратную подматрицу из одних единиц максимального размера.

Задача 11.

Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

Переформулировка задачи 11.

Фермер хочет построить на своей земле как можно больший по площади сарай. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму сеткой размера MxN. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Прямоугольный сарай не должен ни с чем соприкасаться (т.е. в соседних с ним узлах сетки не может ничего быть).

Найти максимально возможную площадь сарая и где он может размещаться.

Задача 12.

Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.

Задача 13.

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и

а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти

1) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;

2) в любую из 8 соседних клеток;

б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).

Задача 14.

Дан выпуклый n-угольник, n=>3, своим обходом по контуру. Разбить его на треугольники (n-3)-мя диагоналями, непересекающимися кроме как по концам, таким образом чтобы

а) Cумма их длин была минимальной;

б) Максимальная из диагоналей имела наименьшую длину.

Задача 15.

Задано число А и два вектора b[1..n] и c[1..n].

Найти множество I, являющееся подмножеством множества {1,...,n}, такое, что

является максимальной из всех возможных

Задача 16.

Пусть x=(a1,a2,...,am) и y=(b1,b2,...,bn) - две заданных строки символов.

Определим d(x,y) как минимальное число вставок, удалений и замен символа, которое необходимо для преобразования x в y.

Например: d(ptslddf,tsgldds)=3

Для заданных x и y найти d(x,y).

Задача 17.

Вводится три неотрицательных числа d, i, c и две строки X и Y. Найти преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:

удалить любой символ из X (стоимость операции d);

вставить любой символ в X (стоимость операции i);

заменить символ в X на произвольный (стоимость операции e).

Задача 18.

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Задача 19.

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

Замечание:

n(i) - число строк в матрице Ai

m(i) - число столбцов в матрице Ai

n(i)=m(i)+1.

Задача 20.

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов (одного "разрыва" возрастающей подпоследовательности).

Например: A=(1,2,3,2,4,3,4,6);

Искомая подпоследовательность (1,2,3,2,3,4,6)

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, m пар соседних элементов (возрастающая подпоследовательность с m "разрывами").

Задача 21.

В заданной последовательности целых чисел найти максимально длинную подпоследовательность чисел такую, что каждый последующий элемент подпоследовательности делился нацело на предыдущий.

Задача 22.

Возвести число А в натуральную степень n за как можно меньшее количество умножений.

Задача 23.

Заданы z и y - две последовательности. Можно ли получить последовательность z вычеркиванием элементов из y.

Задача 24.

Найти максимальную по длине последовательность z, полученную вычеркиванием элементов как из x, так и из y.

Задача 25.

Пусть x и y - две бинарных последовательности (т.е. элементы последовательностей - нули и единицы); x и y можно рассматривать как запись в двоичной форме некоторых двух натуральных чисел.

Найти максимальное число z, двоичную запись которого можно получить вычеркиванием цифр как из x, так и из y. Ответ выдать в виде бинарной последовательности.

Компетентное жюри следит за ходом отдельных этапов турнира, разрешает возникающие спорные вопросы, подводит итоги и награждает победителей. В жюри могут входить педагоги и методисты, психолог, представители интересов игроков (дети, родители), школьники, спонсоры.

В подготовке вопросов, заданий для 1 и 2 этапов игры могут участвовать не только педагоги и методисты, но и сами школьники. Например, старшеклассники могут предлагать вопросы и задачи для школьников младших классов.

Вообще, для проведения турниров целесообразно составлять базу вопросов, заданий, задач. Это могут быть и прочитанные в учебниках, задачниках, интернет задания, и придуманные организаторами и участниками турнира задачи.

Желательно базу заданий формировать таким образом, чтобы задачи были сгруппированы оп темам и типам. Например:

Операторы цикла

№1. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (включая сами эти числа), в порядке их возрастания, а также количество N этих чисел.

№2. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (не включая сами эти числа), в порядке их убывания, а также количество N этих чисел.

№3. Дано вещественное число A и целое число N (> 0). Вывести A в степени N: AN = A·A·...·A (числа A перемножаются N раз).

№4. Дано вещественное число A и целое число N (> 0). Вывести все целые степени числа A от 1 до N.

№5. Дано вещественное число A и целое число N (> 0). Вывести 1 + A + A2 + A3 + ... + AN. Begin85. Дано вещественное число A и целое число N (> 0). Вывести 1 - A + A2 - A3 + ... + (-1)NAN.

№6. Дано целое число N (> 1). Вывести наименьшее целое K, при котором выполняется неравенство 3K > N, и само значение 3K.

№7. Дано целое число N (> 1). Вывести наибольшее целое K, при котором выполняется неравенство 3K < N, и само значение 3K.

№8. Дано вещественное число A (> 1). Вывести наименьшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет больше A, и саму эту сумму.

№9. Дано вещественное число A (> 1). Вывести наибольшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет меньше A, и саму эту сумму.

№10. Дано целое число N (> 0). Вывести произведение 1·2·...·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число.

№11. Дано целое число N (> 0). Если N -- нечетное, то вывести произведение 1·3·...·N; если N -- четное, то вывести произведение 2·4·...·N. Чтобы избежать целочисленного переполнения, вычислять это opnhgbedemhe с помощью вещественной переменной и выводить его как вещественное число.

№12. Дано целое число N (> 0). Вывести сумму 2 + 1/(2!) + 1/(3!) + ... + 1/(N!) (выражение N! -- "N факториал" -- обозначает произведение всех целых чисел от 1 до N: N! = 1·2·...·N). Полученное число является приближенным значением константы e = exp(1) (= 2.71828183...).

№13. Дано вещественное число X и целое число N (> 0). Вывести 1 + X + X2/2! + ... + XN/N! (N! = 1·2·...·N). Полученное число является приближенным значением функции exp в точке X.

№14. Дано вещественное число X и целое число N (> 0). Вывести X - X3/3! + X5/5! - ... + (-1)NX2N+1/(2N+1)! (N! = 1·2·...·N). Полученное число является приближенным значением функции sin в точке X.

№15. Дано вещественное число X и целое число N (> 0). Вывести 1 - X2/2! + X4/4! - ... + (-1)NX2N/(2N)! (N! = 1·2·...·N). Полученное число является приближенным значением функции cos в точке X.

№16. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X - X2/2 + X3/3 - ... + (-1)N-1XN/N. Полученное число является приближенным значением функции ln в точке 1+X.

№17. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X - X3/3 + X5/5 - ... + (-1)NX2N+1/(2N+1). Полученное число является приближенным значением функции arctg в точке X.

№18. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Отрезок [A, B] разбит на равные отрезки длины H с концами в N точках вида A, A + H, A + 2H, A + 3H, ..., B. Вывести значение H и набор из N точек, образующий разбиение отрезка [A, B].

№19. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Функция F(X) задана формулой F(X) = 1 - sin(X). Вывести значения функции F в N равноотстоящих точках, образующих разбиение отрезка [A, B]: F(A), F(A + H), F(A + 2H), ..., F(B).

№20. Дано число D (> 0). Последовательность чисел AN определяется следующим образом: A1 = 2, AN = 2 + 1/AN-1, N = 2, 3, ... Найти первый из номеров K, для которых выполняется условие |AK - AK-1| < D, и вывести этот номер, а также числа AK-1 и AK.

Двумерные массивы (матрицы)

№21. Дано число k (0 < k < 11) и матрица размера 4 x 10. Найти сумму и произведение элементов k-го столбца данной матрицы.

№22. Дана матрица размера 5 x 9. Найти суммы элементов всех ее четных1|нечетных2 строк3|столбцов4.

№23. Дана матрица размера 5 x 10. Найти минимальное1|максимальное2 значение в каждой строке3|столбце4.

№24. Дана матрица размера 5 x 10. В каждой строке1|столбце2 найти количество элементов, больших3|меньших4 среднего арифметического всех элементов этой строки1|столбца2.

№25. Дана матрица размера 5 x 10. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой строке1|столбце2.

№26. Дана матрица размера 5 x 10. Найти минимальное1|максимальное2 значение среди сумм элементов всех ее строк3|столбцов4 и номер строки3|столбца4 с этим минимальным1|максимальным2 значением.

№27. Дана матрица размера 5 x 10. Найти минимальный1|максимальный2 среди максимальных1|минимальных2 элементов каждой строки3|столбца4.

№28. Дана целочисленная матрица размера 5 x 10. Вывести номер ее oepbni1|последней2 строки3|столбца4, содержащего равное количество положительных и отрицательных элементов (нулевые элементы не учитываются). Если таких строк3|столбцов4 нет, то вывести 0.

№29. Дана матрица размера 5 x 10. Вывести номер ее первой1|последней2 строки3|столбца4, содержащего только положительные элементы. Если таких строк3|столбцов4 нет, то вывести 0.

№30. Дана целочисленная матрица размера M x N. Различные строки (столбцы) матрицы назовем похожими, если совпадают множества чисел, встречающихся в этих строках (столбцах). Найти количество строк1|столбцов2, похожих на первую3|последнюю4 строку1|столбец2.

№31. Дана целочисленная матрица размера M x N. Найти количество ее строк1|столбцов2, все элементы которых различны.

№32. Дана целочисленная матрица размера M x N. Вывести номер ее первой1|последней2 строки3|столбца4, содержащего максимальное количество одинаковых элементов.

№33. Дана квадратная матрица порядка M. Найти сумму элементов ее главной1|побочной2 диагонали.

Деревья

№34. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл с именем Name все возможные пути, ведущие от корня к листьям (каждый путь записывается в отдельной строке файла). Перебирать пути, начиная с "самого левого" и заканчивая "самым правым", при этом первыми заменять конечные элементы пути.

№35. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл с именем Name все пути, ведущие от корня к листьям и удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Каждый путь записывается в отдельной строке файла. Порядок перебора путей -- тот же, что в задании №34.

№36. Дано упорядоченное дерево глубины N (N > 0 -- четное), каждая внутренняя вершина которого имеет два непосредственных потомка: A с весом 1 и B с весом -1. Корень дерева C имеет вес 0. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей -- тот же, что в задании №34.

№37. Дано упорядоченное дерево глубины N (N > 0) того же типа, что и в задании Proc83. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2. Каждый путь записывается в отдельной строке файла. Порядок перебора путей -- тот же, что в задании №34.

№38. Дано упорядоченное дерево глубины N (N > 0 -- четное) того же типа, что и в задании Proc83. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующим условиям: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2, а суммарный вес всех элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей -- тот же, что в задании №34.

3.3 Подготовка школьников к олимпиаде

Не секрет ни для кого, что только успех помогает человеку поверить в свои силы и стремиться преодолевать новые вершины. Для успешного участия в олимпиаде по программированию школьник должен:

Владеть языком программирования (Pascal или Си/Си++)

Уметь:

1. придумывать и реализовывать алгоритмы решения задач;

2. оценивать время их работы;

3. тестировать;

4. отлаживать свои программы.

Знать следующие алгоритмы:

9 класс

Алгоритмы целочисленной арифметики

1. Поиск делителей числа. Простые числа 2. Разложение числа на простые множители 3. Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) 4. Представление чисел. Выделение цифр числа 5. Перевод чисел из одной системы счисления в другую 6. Делимость чисел 7. Действия с многозначными (большими) числами

Рекуррентные уравнения и динамическое программирование

1. Понятие задачи и подзадачи

2. Понятие рекуррентного соотношения

Задачи комбинаторики

1. Перестановки

2. Сочетания

3. Размещения

4. Подмножества

5. Реализация перебора вариантов. Сокращение перебора

10-11 класс

Структуры данных

1. Очереди

2. Стеки

3. Списки

Теория графов

1. Основные понятия теории графов

2. Смежность и инцидентность

3. Представление графов

4. Маршруты

5. Маршруты в графах

6. Поиск в ширину

7. Поиск в глубину

8. Исчерпывающий поиск с возвратом

9. Алгоритм построения кратчайших путей

10. Эйлеровы графы

11. Основная теорема об эйлеровом графе

12. Алгоритм построения эйлерова цикла

Сортировка

1. Понятие сортировки

2. Сортировка простым обменом

3. Квадратичные алгоритмы

4. Алгоритмы порядка n log n

5. Линейный поиск

6. Бинарный поиск

Геометрия

1. Прямая и отрезок прямой

2. Треугольник

3. Площадь произвольного треугольника

4. Замечательные линии и точки треугольника

5. Многоугольник

6. Выпуклый многоугольник

7. Площадь простого плоского многоугольника

Рекурсия

1. Примеры рекурсивных программ.

2. Рекурсивная обработка деревьев

Проводя подготовку своих воспитанников к турниру, не забывайте дать им несколько советов:

1. Если вы участвуете в турнире впервые, заранее посмотрите примеры предлагаемых на турнирных задач, например, в архивах олимпиад, представленных сайтах.

2. Все решения проверяются автоматически, и если выходной файл содержит постороннюю информацию или если его формат не соответствует описанному в условии, он будет признан неправильным.

3. Ваша программа не должна ничего выводить на экран (если это особо не оговорено в условии задачи), а также ждать какого-либо ввода пользователя.

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

5. Прежде всего, вы должны уметь работать с текстовыми файлами (считывать и записывать информацию).

6. Лучше всего попробовать работать с файлами до того, как вы придете на олимпиаду, это не сложно - скорее всего, вы с легкостью разберетесь, как это делается, посмотрев приведенный ниже пример