Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3

Подождите немного. Документ загружается.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ

ФЕДЕРАЦИИ

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

О .Ф.Ускова

О .Д .Горбенко

ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ .

ЛУЧШИЕ РЕШЕНИЯ

Часть 3

Учебное издание

ВОРОНЕЖ – 2002

ББК 32.97

УДК 681.3

Олимпиадные задачи по программированию. Лучшие

решения. В трех частях. Часть 3.: Учебное издание/ О .Ф .Ускова,

О .Д .Горбенко – Воронеж: ООО ПФ «Джуди», 2002 – 80 с.

Редактор Андрейчикова Л .А.

Работа выполнена в рамках Федеральной целевой

программы «Интеграция науки и высшего образования» по

направлению 2.7 «Проведение научных конкурсов, школ и

конференций для студентов, аспирантов, молодых

преподавателей и сотрудников вузов и научныз организаций»

( проект Т0140).

Издается при финансовой поддержке ООО ПФ «Джуди».

ББК 32.97

УДК 681.3

ISBN 5-815-047-0

О Г Л А В Л Е Н И Е

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … 4

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

Положение о второй открытой региональной студенческой

школе - олимпиаде по программированию и компьютерному

моделированию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Положение о первом туре . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Задачи предшествующих олимпиад (с комментариями и

решениями) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Материалы первой открытой региональной студенческой

школы - олимпиады 2001 года. . . . . . . . . . . . . . . . . . . . . . . . . . . . .64

Результаты 1 тура первой открытой региональной студенческой

школы - олимпиады по программированию и компьютерному

моделированию 2001 года. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64

Результаты 2 тура первой открытой региональной студенческой

школы - олимпиады по программированию и компьютерному

моделированию 2001 года. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Варианты заданий, предлагавшихся на первой открытой

региональной студенческой школы - олимпиады по

программированию и компьютерному моделированию 2001

года. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70

Задания 1 тура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Задания 2 тура. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Автор логотипа школы - олимпиады – студентка факультета

прикладной математики , информатики и механики Воронежского

госуниверситета Людмила Артеменко

ПРЕДИСЛОВИЕ

Издание подготовлено в рамках проекта Т0140

Целевой Федеральной программы "Интеграция науки и

высшего образования» по направлению 2.7 «Проведение научных

конкурсов, школ и конференций для студентов, аспирантов,

молодых преподавателей и сотрудников вузов и научныз

организаций» ". Оно ориентировано в основном на

участников региональной открытой студенческой

школы-олимпиады по программированию и

компьютерному моделированию , но может быть

также полезно школьникам старших классов,

студентам и учителям информатики

общеобразовательных и профильных учебных заведений .

Организаторами школы -олимпиады являются

Воронежский госуниверситет , Воронежский

государственный педагогический университет ,

Воронежская государственная технологическая

академия , Федеральный научно - производственный центр

«Воронежский НИИ связи», Воронежский региональный

центр информатизации высшей школы , Центр правовой

информатизации Министерства юстиции Российской

Федерации по Воронежской области.

В первой части рассматривались задачи

предшествовавших олимпиад по информатике

различного уровня (факультетских, вузовских,

межвузовских, региональных, федеральных). Некоторые

задачи приведены с решениями, в основном

разработанными студентами факультета прикладной

математики и механики Воронежского университета,

ставшими в свое время призерами этих олимпиад . Во

второй части помимо задач, предложенных на

олимпиадах различного уровня , были представлены

материалы первого (заочного) тура школы -олимпиады.

Воронежский университет , на базе которого

проводится школа-олимпиада, выражает

признательность ООО ПФ "Джуди" (директор Андрей

.Васильевич Андрейчиков), оказавшему серьезную

поддержку в издании этой книги.

Введение

Среди целей проведения Открытых региональных

студенческих школ-олимпиад по программированию и

компьютерному моделированию можно выделить следующие

основные:

- развитие творческой активности студентов;

- ориентация учащейся молодежи на решение задач

информатизации научных исследований в сфере естественных

наук;

- выявление наиболее талантливых студентов в области

моделирования процессов в природе и в обществе ,

проектирования и разработки соответствующих программных

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

компьютерных технологий.

В планах проведения таких школ-олимпиад предусмотрен

цикл лекций ведущих ученых г.Воронежа по актуальным

проблемам современной науки , работа круглого стола

" Компьютерные технологии в образовании", что будет

способствовоать углублению знаний и расширению научного

кругозора участников школы - олимпиады .

В связи с тем , что число желающих принять уачстие в школе -

олимпиаде достаточно велико, первый тур олимпиады

проводится в телекоммуникационном режиме. Это позволяет не

только принять всех желающих, но и значительно расширить

«географию» участников при минимальных финансовых

затратах. Таким образом , отличительная особенность

проводимых школ-олимпиад – их открытость и отсутствие

каких-либо оргвзносов со стороны участников. (Заметим, что

команда, участвующая в четверть- финале мирового чемпионата

по программированию, который ежегодно проводится в

Саратове , платит ежегодно оргвзнос в размере 1000 рублей).

Кроме того , все участники очного тура обеспечиваются

бесплатным питанием , а иногородние участники - и бесплатным

проживанием .

Особое внимание было уделено студентам -инвалидам и

студентам из малообеспеченных семей. Они выступали в

отдельной номинации, каждый из них получил материальное

поощрение в виде денежного приза и подарка.

Широкая общественность информируется об организации,

проведении и результатах школы - олимпиады с помощью

средств массовой информации, включая электронные средства:

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

на сайте олимпиады www.main.vsu.ru/~pmmmo отражаются

самые свежие новости .

Наш город и университет дважды удостоены чести быть

центром проведения этого важного молодежного мероприятия в

рамках Федеральной целевой программы «Интеграция науки и

высшего образования» по направлению «Воссоздание

студенческих школ, конференций и олимпиад» в 2001 (грант

Р0054) и в 2002 (грант Т0140) году.

Головной организацией при проведении школы - олимпиады в

2001 году выступал Воронежский государственный

университет, на базе которого и проводилась школа - олимпиада,

в качестве соисполнителей были : Вычислительный центр им.

А.А. Дородницына РАН и Воронежский государственный

педагогический университет. В 2002 году головной

организацией также является Воронежский государственный

университет, исполнителями

- Воронежский государственный педагогический

университет (ректор проф. Подколзин В.В.);

- Воронежская государственная технологическая академия

(ректор проф. Битюков В .К .);

- Федеральный научно-производственный центр

«Воронежский НИИ связи» (директор проф. Борисов

В .И.);

- Воронежский региональный центр информатизации высшей

школы (директор проф. Ландсберг С .Е .);

- Центр правовой информатизации Министерства юстиции

Российской Федерации по Воронежской области (директор

Краснер И.Н.).

Без финансовой поддержки ФЦП "Интеграция" проведение

школы - олимпиады было бы невозможно. Значительную

поддержку проведению региональной школы - олимпиады

оказала администрация Воронежской области . Планом работы

Главного управления образования администрации Воронежской

области на 2002 год предусмотрена финансовая поддержка

проведению подобных олимпиад .

Спонсорами первой школы - олимпиады 2001 года

выступили ряд коммерческих организации и фирм Воронежской

и Белгородской областей. ООО ПФ "Джуди" (директор

А.В .Андрейчиков) оказало существенную спонсорскую

поддержку в подготовке и публикации 1 и 2 частей сборника

"Олимпиадные задачи по программированию. Лучшие

решения".

Информационную поддержку проведению школы -

олимпиады оказали ряд региональных и центральных средств

массовой информации Воронежской и Белгородской областей, а

также веб-сервер Воронежского госуниверситета .

Разработана методика проведения студенческих олимпиад

по программированию различного уровня, концептуальные

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

студенческих конференций, сделаны доклады по проблеме на

российских и международных научных и научно-методических

конференциях.

Школа - олимпиада 2001 года проводилась в регионе

впервые. В первом туре приняло участие около 600 студентов

Воронежской, Липецкой, Белгородской, Курской и Брянской

областей. В олимпиаде принимали также участие студенты из

малообеспеченных семей и студенты - инвалиды . Итоги

олимпиады подводились по номинациям : "Первокурсники ",

"Студенты , для которых информатика является профилирующей

дисциплиной", "Студенты , для которых информатика является

общепрофессиональной дисциплиной", "Иногородние

студенты ", "Студенты военных вузов".

Еще одна особенность проведенного мероприятия -

привлечение к участию в нем студентов, специализирующихся в

различных областях знания и технологий, обучающихся в

учебных заведениях разных уровней и источников

финансирования.

К подготовке заданий первой открытой региональной

студенческой школы - олимпиады были привлечены ведущие

ученые вузов Воронежа и ВЦ РАН. Воронежский

госуниверситет располагает необходимым научным

потенциалом , соверменным техническим оснащением ,

достаточным количеством учебных компьютерных классов и

учебно-методическим обеспечением для организации и

проведения олимпиады.

В составе коллектива исполнителей первой школы -

олимпиады: 6 профессоров, докторов наук, 20 кандидатов

наук, доцентов; 4 преподавателя ; 3 технических работника, 20

студентов, 1 аспирант, 4 магистранта .

При проведении практической части школы - олимпиады

была задействована лабораторная база факультета прикладной

математики , информатики и механики и факультета

компьютерных наук Воронежского государственного

университета .

Региональная школа - олимпиада создает базис для

проведения подобных олимпиад других уровней:

факультетского , вузовского , районного , городского ,

межвузовского .

Олимпиадные задачи могут использоваться в учебном

процессе при работе с талантливыми (одаренными) студентами,

в кружковой работе , на семинарах. Материалы школы -

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

учителями информатики общеобразовательных школ. Изданный

одним из спонсоров школы - олимпиады ООО ПФ «Джуди»

(директор А.В .Андрейчиков) по материалам школы - олимпиады

сборник "Олимпиадные задачи по программированию. Лучшие

решения" может быть использован как в учебной работе , так и

самостоятельно при подготовке к участию в подобных

олимпиадах.

Материальную спонсорскую поддержку школе - олимпиаде

оказали :

- Администрация Воронежской области ;

- Центрально-Черноземное представительство

корпорации "ПАРУС", г.Воронеж (Руководитель –

Александр Владимирович Азнаурьянц, выпускник

факультета ПММ ВГУ );

- ЗАО "РЕТ", г.Воронеж (Генеральный директор -

Владимир Михайлович Колыхалин, выпускник

факультета ПММ ВГУ );

- ЗАО ПКФ "Воронежский керамический завод "

(генеральный директор - Владимир Алексеевич

Горемыкин);