Олимпиадные задания по информатике. 9-11 кл

Подробное описание

Введение

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

Каков же этот минимум? Естественно, что уже должен быть изучен один из алгоритмических языков программирования (Basic, Pascal) – командные реализации базовых алгоритмических конструкций (следование, ветвление, цикл), стандартные математические функции и функции для обработки строковых переменных; дано понятие одномерных и двумерных массивов. Далее можно готовиться к олимпиадам, применяя предлагаемый материал:

• использовать типовые алгоритмы, которые позволят решить любую задачу. В данном пособии очерчен круг необходимых типовых алгоритмов, а затем рассмотрены некоторые олимпиадные задачи, которые решаются с применением этих алгоритмов. Все задачи в пособии приведены с решениями на двух языках (Бейсик, Паскаль);
• группировать задачи не по темам (задачи на «Строки», задачи из «Теории чисел» и др.), а по методам их решения. В пособии предложены некоторые методы решения часто встречающихся в практике программирования задач.
• анализировать и использовать комбинаторные задачи. Это бесспорные лидеры на олимпиадах. Поэтому этой теме в пособии уделено особое внимание. Комбинаторика рассматривается детально и подробно, тема иллюстрирована типовыми алгоритмами формирования комбинаторных групп, рассмотрен пример решения некоторых комбинаторных задач методом двоичного перебора.

В заключение приведены теоретические сведения по теме «Календарные исчисления». Эта тема может быть предложена учащимся для самостоятельного рассмотрения.

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

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

Содержание

Введение    3

Базовые формулы (зависимости) и задачи, решаемые с их помощью    4

Типовые алгоритмы и задачи, решаемые с их помощью    11

Типовые алгоритмы обработки одномерных массивов    11

Типовые алгоритмы обработки строковых переменных    16

Типовые алгоритмы обработки одномерных массивов (продолжение). Сортировка методом «Пузырька»    38

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

Обработка всего массива    48

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

Типовые алгоритмы обработки двумерного массива отдельно по столбцам    51

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

Обработка квадратной матрицы относительно диагоналей (рациональный способ)    53

Задачи, сгруппированные по методам решения    55

Тема 1. Решение задач с использованием дополнительного массива «флажков»    55

Тема 2. Три задачи – один алгоритм    60

Тема 3. От арифметического квадрата  до кратчайшего пути (четыре задачи – один алгоритм)    67

Тема 4. Метод вложенных матриц    75

Тема 5. Все через площадь треугольника    83

Комбинаторика    92

Формирование комбинаторных групп из N по К    92

Формирование комбинаторных групп из N (К – от 1 до N)    103

Календарные исчисления    108

Литература    110