Программирование в средней школе. ЧАСТЬ 3.
Продолжение.
Анатолий Ремнев
После изучения основ программирования на любом алгоритмическом языке круг решаемых задач существенно зависит от категории учащихся.. Сформулируем лишь некоторые из тем, задания по которым могут быть полезны для широкого круга учащихся.
1. Задачи по системам счисления
Решение задач данного типа позволяет не только овладеть данным разделом теоретической информатики, но и усовершенствовать технику программирования.
2. Задачи на "длинную арифметику"
Помимо традиционных задач на сложение, вычитание, умножение и целочисленное деление "длинных" чисел (порядка 20-30!), в данный раздел можно включить различные задачи, получить точный ответ в которых можно, лишь самостоятельно реализовав те или иные арифметические операции. Для хранения "длинных" чисел используется массив, или стек, реализованный с помощью списка. Типы задач: поиск наибольшего общего делителя двух "длинных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извлечение квадратного корня из "длинного" числа и т.д.
3. Задачи на использование динамических структур данных
Пто такие задачи, как: список, стек, очередь, дерево, сбалансированное дерево бинарного поиска и т.п.
4. Алгоритмы на графах
В частности, наиболее часто в программировании встречаются следующие задачи: обход графа в глубину и в ширину, подсчет компонент связности, построение минимального остовного дерева, поиск кратчайшего пути в графе, нахождение эйлерова цикла, задача коммивояжера (гамильтонов цикл), задачи о размещениях. Следует отметить, что здесь очень важна очень мощная математическая подготовка как учащихся, так и самого учителя.
5. Целочисленные задачи линейного программирования
Это задача о назначениях, задача о максимальном потоке, общая задача линейного программирования, при решении которой используется симплекс-метод.
6. Задачи на полный перебор вариантов, при решении которых используется перебор с возвратом с применением метода ветвей и границ и других методов сокращения перебора
В частности, задачи на программирование игр и головоломок с использованием отсечений.
7. Комбинаторные задачи
Для каждой из основных комбинаторных конфигураций - множество всех подмножеств, сочетания, перестановки, размещения и т.п. - можно поставить следующие задачи. Для заданных входных параметров подсчитать количество всех возможных конфигураций того или иного типа, сгенерировать все конфигурации соответствующего типа, определить конкретную конфигурацию по ее номеру в лексикографическом порядке конфигураций и, наоборот, по конфигурации определить ее номер, для любой заданной конфигурации построить следующую в лексикографическом порядке.
8. Задачи вычислительной геометрии и компьютерной графики
Сюда можно отнести множество задач, решение которых должно быть получено в графическом представлении. Самыми простыми задачами такого рода можно считать такие.
Пример. Построить столбиковую (гистограммную) интерпретацию одномерного массива, в которой максимальный элемент выделен красным цветом, минимальный - зеленым, все остальные элементы представляются желтым цветом.
Пример. Найти площадь фигуры, изображенной на экране при помощи метода Монте-Карло.
9. Задачи по теории формальных грамматик и конечных автоматов
Начиная с проверки правильности записи арифметических выражений и подсчета их значений до элементов интерпретации и компиляции программ.
10. Задачи криптографии
Следует рассмотреть задачи, основанные на алгоритмах шифрации. Этот тип задач плотно связан с задачами на перебор.
Итак, мы с вами рассмотрели основной набор задач, который следует решать с учащимися на базовых и факультативных занятиях по программированию. Отдельным вопросом можно считать олимпиадные задачи, но тут, кроме простого практикума по решению как можно большего числа задач олимпиадного типа с выработкой навыка различения типов этих задач предложить нечего. Практика, практика и еще раз практика.