Организация и методика проведения турнира программистов в школе
Содержание
Введение
. Основные положения
. Методика организации и проведения турниров по
информатике, программированию
.1 С чего начинать?
.2 Первый шаг - создание оргкомитета
.3 Положение о проведении турнира
.4 Рекомендации по выбору систем проведения
.5 Языки программирования на соревнованиях
. Проведение турнира в учреждении образования (школе)
.1 Правила проведения олимпиад по информатике
.3 Подготовка школьников к олимпиаде
Заключение
Приложение 1
Приложение 2
Приложение 3
Приложение 4
Список использованной литературы
Введение
Главной задачей XXI века является, несомненно, улучшение качества жизни,
в том числе, качества образования, определяющего условия развития личности.
Именно поэтому реформирование и совершенствование систем образования и науки
являются определяющим фактором решения большинства проблем в условиях
глобализации.
Говорить о реформировании и совершенствовании систем образования не
рассматривая вопросы внеучебной деятельности, в частности по информатике,
программированию, невозможно. В условиях, когда компьютеризация общества,
различных общественных процессов протекает с огромной скоростью, важен уровень
компьютерной грамотности населения. Сегодняшний обучающийся завтра должен стать
полноправным и активным участником всех общественных, социальных,
производственных процессов государства.
Актуальность исследования. Нынешнее образование ориентировано на развитие
личности. Современному обществу нужен выпускник, самостоятельно мыслящий,
умеющий видеть и творчески решать возникающие проблемы.
Особую актуальность эта задача получает в динамично развивающемся
информационном пространстве. Однако учащиеся не всегда могут ориентироваться в
огромном потоке новых сведений, извлекать необходимые факты и данные,
продуктивно использовать их в своей работе.
Одним из выходов из создавшейся проблемной ситуации, когда обществу
требуются высококвалифицированные специалисты со знанием компьютера не просто
на уровне пользователя, а со знанием программирования, может и должна стать
организация учебного и внеучебного процесса в образовательных учреждениях
разного типа с учетом требований времени. В организациях образования происходит
процесс реформирования учебного процесса. А внимание организаторов и участников
процесса обучения: методистов, преподавателей, консультантов должно направить
на реализацию задач повышения уровня компьютерной грамотности населения и
развитие навыков программирования на различных языках.
Необходимо учитывать, что современная система образования ориентирует
педагога не на передачу знаний в готовом виде, а на организацию обучения
самостоятельной деятельности обучающихся и доведение её до уровня поисковой,
исследовательской работы, выходящей за рамки учебной программы.
Самостоятельная, исследовательская деятельность, нестандартный подход к решению
теоретических и практических задач различных областей науки, позволяет
вооружить обучающегося необходимыми знаниями, умениями, навыками для освоения
стремительно нарастающего потока информации, ориентации в нём и систематизации
материала. Обучение же может происходить как в урочной деятельности, так и во
внеурочной.
Цель работы - определение, систематизация, описание различных форм
внеурочной работы по программированию.
Объект исследования - процесс организации и проведения нестандартных форм
внеурочной деятельности по программированию.
Предмет исследования - методики, позволяющие повысить качество усвоения
программного материала обучающимися по информатике и программированию.
В основу разработки темы работы была положена рабочая гипотеза: использование
во внеурочной работе эффективных методик организации и проведения мероприятий,
позволяет обеспечить выполнение требований Государственных стандартов
образования на высоком уровне, дает возможность обучаемым быть не только
потребителями готового к усвоению знания, но и активно участвовать в процессе
поиска ответов на предлагаемые им вопросы, задания..
Теоретико-методологическая основа исследования:
Для достижения цели и решения поставленных задач был использован комплекс
теоретических и эмпирических методов исследования:
- теоретико-эмпирические: абстрагирование, анализ, синтез,
индукция, дедукция, моделирование;
- эмпирические: наблюдение, сравнение
- герменевтические: беседа, интервью, самонаблюдение,
самоанализ и др;
1. Основные положения
Нынешнее образование ориентировано на развитие личности. Современному
обществу нужен выпускник, самостоятельно мыслящий, умеющий видеть и творчески
решать возникающие проблемы.
Особую актуальность эта задача получает в динамично развивающемся
информационном пространстве. Однако учащиеся не всегда могут ориентироваться в
огромном потоке новых сведений, извлекать необходимые факты и данные,
продуктивно использовать их в своей работе.
Организовывая работу с учащимися, необходимо исходить из того, что
школьники (студенты) должны иметь возможность не только получить определённые
знания по тому или иному предмету, но и проявить себя, попробовать в различных
видах деятельности.
Работа по формированию интеллектуальных умений и навыков должна
осуществляться, главным образом, на уроках. Этому способствуют и современные
интерактивные технологии, такие как методы проектов и модульного обучения, а
также информационные технологии, которые широко внедряются в практику работы
школы.
В то же время применение этого метода на уроках позволяет развивать
критическое и творческое мышление, формировать навыки работы с научной,
научно-популярной литературой.
Массовая внеурочная работа - это интеллектуальные игры, олимпиады,
конференции, марафоны, турниры. Рассмотрим некоторые из этих мероприятий (их
понятия), используя в том числе и материалы свободной энциклопедии - Википедии
[1].
Игра́ - вид непродуктивной деятельности, с действиями,
ограниченными правилами, которые направлены на создание, развитие и поддержание
процесса в заданных границах. Задача процесса - доставить участникам ряд
переживаний и эмоций, дать процессы, в которых можно приобрести новый опыт
через непосредственное практическое участие. У животных стремление играть
наблюдается в ювенильном существовании и исчезает по мере взросления. Человек в
этом отношении отличается от животных тем, что сохраняет игровое поведение
долго после окончания ювенильного этапа развития. Кроме того человеческие игры,
в том числе и детские, являются культурно опосредованными.
Если говорить
об игре как о методе обучения, то необходимо отметить следующее: естественное и
непреодолимое стремление детей к игре всегда с большим успехом используется в
педагогической практике. Существуют научно обоснованные игровые методики и
технологии, рассчитанные на детей разного возраста. Основным отличием игры как
метода обучения является наличие чёткой цели. Конкретное содержание и формы
игрового процесса очень разнообразны и определяются рядом факторов.
Игра практически с древних времён выступает как форма обучения, как
первичная школа воспроизводства реальных практических ситуаций с целью их
освоения. Исторически одной из целей игры являлась выработка необходимых
человеческих черт, качеств, навыков и привычек, развития способностей.
«Я говорю и утверждаю, что человек, желающий стать выдающимся в каком бы
то ни было деле, должен с ранних лет упражняться… Например, кто хочет стать
хорошим земледельцем или домостроителем, должен ещё в играх либо обрабатывать
землю, либо возводить какие-либо детские сооружения». Так говорил об игре
Платон (427 - 347 до н.э.)
Игра - ведущий вид деятельности ребёнка. С.Л.Рубинштейн (1976) [2]
отмечал, что игра хранит и развивает детское в детях, что она их школа жизни и
практика развития. По мнению Д.Б.Эльконина (1978) [3], «в игре не только развиваются
или заново формируются отдельные интеллектуальные операции, но и коренным
образом изменяется позиция ребёнка в отношении к окружающему миру и формируется
механизм возможной смены позиции и координации своей точки зрения с другими
возможными точками зрения».
Какими признаками отличается игра от других видов деятельности?
Считается, что большинству игр присущи следующие главные черты:
- свободная развивающаяся деятельность, предпринимаемая лишь по
желанию, ради удовольствия от самого процесса деятельности, а не только от
результата;
- творческая, импровизационная, активная по своему характеру
деятельность;
- эмоционально напряжённая, приподнятая, состязательная,
конкурентная деятельность;
- деятельность, проходящая в рамках прямых или косвенных правил,
отражающих содержание игры;
- деятельность, имеющая имитационный характер;
- наличие минимальной игровой ситуации.
«Игра не есть «обыденная» жизнь и жизнь как таковая. Она скорее выход из
рамок этой жизни во временную сферу деятельности, имеющую свою собственную
направленность. Даже малое дитя прекрасно знает, что оно играет лишь «как будто
взаправду», что это всё «понарошку».
Деятельность, обособленная от «обыденной» жизни местом действия - игровой
зоной и продолжительностью. Она «разыгрывается» в определённых рамках
пространства и времени. Внутри игрового пространства царит собственный
безусловный порядок» (Й.Хезинг, 1992)[4].
Под минимальной игровой ситуацией понимаем обусловленное правилами игры
игровое состояние, реализация которого в любом случае приведёт как минимум к
ещё одному действию (ходу) соперника.
Когда минимальные игровые ситуации иссякают, игра, соответственно,
прекращается.
Любая игра - это прежде всего процесс, то есть временная одно- или
многонаправленная цепь событий. Таким образом, имеет смысл говорить об «атоме»
игры, о самой маленькой неделимой её части, о минимальной игровой ситуации.
В ситуационных (а не количественных) соревновательных видах игр задачу
соперников можно свести к совершению действий, в результате которых прекращение
игры (исчерпание игровых ситуаций) происходит в момент преимущества одного из
соперников - по условиям игры.
Конференция - большое собрание, совещание представителей разных
учреждений, стран, групп. С целью обмена знаниями, опытом в той или иной
области науки такая форма работы может быть использована и в организации
учебной и внеучебной деятельности организаций образования. В этом случае
участниками конференции становятся представители одной и/или нескольких
учреждений образования.
Марафон - специально организованное соревнование, проводимое по принципу
индивидуального зачета. Марафон (предметный) включает в себя элементы и
спортивного марафона: участники должны перемещаться по этапам достаточно
быстро, но соблюдая правила техники безопасности.
Предметная олимпиада - состязание учащихся учреждений среднего общего,
высшего или профессионального образования, требующее от участников демонстрации
знаний и навыков в области одной или нескольких изучаемых дисциплин. Олимпиады
нередко сопровождаются церемонией открытия (государственные - обязательно) и
торжественным закрытием (часто с творческими представлениями) с подведением
итогов и награждением лучших.
В России, Казахстане и других странах СНГ проводится значительное число
предметных олимпиад различного уровня.
Олимпиада по программированию - интеллектуальное соревнование по решению
различных задач на ЭВМ, для решения которых необходимо придумать и применить
какой-либо алгоритм и/или программу на одном из языков программирования.
Олимпиады по программированию проводятся с целью выявления наиболее
талантливых и способных людей в области программирования, а также пробуждения
интереса к программированию.
Олимпиады бывают личные и командные. В командных олимпиадах обычно
участвует 3 человека и им на всё время олимпиады дается 1 компьютер для решения
олимпиадных задач.
В России, Казахстане, Украине и других странах сложилась многоуровневая
система проведения олимпиад по программированию. Данный список даёт
представление о различных олимпиадах, проводимых среди школьников, но к ней
могут добавляться или наоборот отсутствовать некоторые этапы:
Районная олимпиада
Городская олимпиада
Региональная олимпиада
Всегосударственная олимпиада
Участие в данных олимпиадах и хорошие результаты, показанные на них,
могут давать некоторые привилегии при поступлении в высшее учебное заведение.
Участие в олимпиаде по программированию считается успешным, если участники
смогли составить программу и проверить её на ЭВМ на тестах, предоставленных
жюри. Решение задачи считается правильным, если ЭВМ дает правильные результаты
на (всех) тестах жюри. Алгоритм (программа) содержит ошибки, если на некоторых
тестах ЭВМ дает сбои, отказы или неправильные результаты. Победители олимпиад
составляют алгоритмы и программы практически без ошибок.
Среди студентов также проводятся олимпиады. Это может быть
внутривузовская олимпиада или олимпиада, в которой могут участвовать студенты
из разных вузов. Обычно эти олимпиады проводятся при финансировании какой-либо
фирмы, занимающейся разработкой программного обеспечения и заинтересованной в
привлечении талантливых студентов на работу в данную фирму. Также данные
олимпиады проводятся для определения кандидатов для участия в чемпионате мира
по программированию среди студентов. Для проведения подобных соревнований
используются турнирные системы, такие как Contester и eJudge.
Крупнейшая международная студенческая командная олимпиада по
программированию называется ACM International Collegiate Programming Contest (Международная студенческая олимпиада по
программированию).
Крупнейшее технологическое соревнование, кубок технологий Imagine cup (международный технологический конкурс среди
студентов и старшеклассников) организуется при поддержке компании Microsoft и других высокотехнологичных
компаний. Соревнование включает в себя 9 категорий: от программных проектов до
алгоритмов, от соревнований в области IT до художественных конкурсов фотографии
и короткометражных фильмов.
В последнее время начал циркуляцию также более общий термин «спортивное
программирование». Состязания по спортивному программированию не связаны
напрямую с системой образования, то есть в них также принимают участие и
профессиональные программисты. Популярные состязания по спортивному
программированию в мире - это конкурс Top Coder.
На классических олимпиадах по программированию участникам предлагается
некоторый набор задач различного уровня сложности. Решением задачи является
программа, написанная на одном из допустимых языков программирования. Эта
программа должна корректно считывать любые входные данные указанного формата из
определённого входного потока, корректно обрабатывать их согласно условию
задачи, и выводить в определённый выходной поток в указанном виде. Для
ввода-вывода могут использоваться как стандартные консольные потоки, так и
файловые (часто входной файл имеет имя «input.txt», а выходной - «output.txt»).
Все решения проверяются автоматизированной тестирующей системой. Она
запускает каждое решение на некотором наборе тестов. После завершения работы
программы она сличает выходные данные с эталонными или производит более сложные
действия. Последнее обычно имеет место, если для входных данных имеется
несколько корректных выводов.
Особенностью олимпиадных задач является художественность их условия. В
условиях редко ведётся речь о структурах данных и алгоритмах, приводящих к
решению. Чаще условие задачи представляет собой короткий рассказ со своим
сюжетом, героями и конфликтом. Таким образом, чтобы решить олимпиадную задачу,
нужно не просто написать заданный алгоритм, а предварительно составить
математическую модель событий, и уже по ней отыскать этот алгоритм. Алгоритм
может быть как одним из уже известных алгоритмов, так и абсолютно новым,
непохожим на другие.
Сюжет условия часто завязан на одном или нескольких героях, вступающих в
конфликт друг с другом или с окружающей средой. Часто они являются
программистами и также поставлены перед некоторой задачей. Нередко все задачи
олимпиады связаны единой сюжетной линией. В этом случае сюжет олимпиады
раскрывается постепенно от задачи к задаче.
Турнир
(от старофранцузского
<#"865279.files/image001.jpg">
Задача 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-ую строчку, при этом из
текущей клетки можно перейти
) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;
) в любую из 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). При этом можно перемножать любые две рядом стоящие
матрицы, в результате чего получается матрица нужного размера.
Замечание:(i) - число строк в матрице Ai(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 или Си/Си++)
Уметь:
. придумывать и реализовывать алгоритмы решения задач;
. оценивать время их работы;
. тестировать;
. отлаживать свои программы.
Знать следующие алгоритмы:
класс
Алгоритмы целочисленной арифметики
. Поиск делителей числа. Простые числа 2. Разложение числа на простые
множители 3. Поиск наибольшего общего делителя (НОД) и наименьшего общего
кратного (НОК) 4. Представление чисел. Выделение цифр числа 5. Перевод чисел из
одной системы счисления в другую 6. Делимость чисел 7. Действия с многозначными
(большими) числами
Рекуррентные уравнения и динамическое программирование
. Понятие задачи и подзадачи
. Понятие рекуррентного соотношения
Задачи комбинаторики
. Перестановки
. Сочетания
.