«М.П.ЛАПЧИК, И.Г.СЕМАКИН, Е.К.ХЕННЕР МЕТОДИКА ПРЕПОДАВАНИЯ ИНФОРМАТИКИ Под общей редакцией М. П. Лапчика Рекомендовано Учебно-методическим объединением по специальностям педагогического образования в качестве учебного ...»
-- [ Страница 7 ] --
Приведите пример: найти в телефонном справочнике большого города номер телефона абонента по фамилии и инициалам легко, а наоборот, по тому же справочнику найти фамилию и инициалы абонента по телефонному номеру — очень большая работа. В чем разница? В первом случае структура упорядочена (по алфавиту), а во втором — нет. Если бы мы имели справочник, в котором номера телефонов расположены в порядке возрастания, то вторая задача решалась бы элементарно, а первая — нет.
Итак, подведите учащихся к мысли: поиск эффективен, а алгоритм его элементарен в упорядоченной (отсортированной) структуре, и переходите к рассмотрению основной задачи — сортировке.
Подчеркните, что термин «нечисловые алгоритмы», использованный выше, вовсе не исключает обработки информации числовой природы. Просто обработка такова, что никакие математические действия не требуются. Все сводится к операциям сравнения и перестановки элементов, а они возможны для любой порядковой структуры. Простейшая задача, которую по традиции рассматривают первой, как раз связана с объектом числовой природы: расположить числа в линейном массиве по возрастанию.
Как ни странно, опыт показывает, что подготовка к решению этой простейшей задачи требует от учителя заметных усилий. Наилучшее решение — подготовить материальную модель, расположив на листе ватмана линейную цепочку карманчиков, в которые можно вставлять карточки с числами — так, чтобы они были все время видны учащимся, и иллюстрировать алгоритмы, переставляя карточки из карманчика в карманчик.
Далее изложите два известнейших, фигурирующих во многих пособиях, метода решения указанной задачи: прямых обменов и «пузырька». Целесообразно вначале показать процедуру упорядочения на описанной выше модели, затем составить блок-схему алгоритма и провести ее трассировку, параллельно с этим переставляя карточки на модели; после этого запись на Паскале будет обычным кодированием.
Освоив простейшие схемы сортировки, объясните учащимся их общность. Не так уж важно, что сортировались числовые массивы. Точно так же могут сортироваться массивы символов, массивы записей (по одному из полей — ключу сортировки) и т.д.
Далее можно развивать эту тему в двух направлениях, оба из которых уже не столь просты и представляют практический интерес.
Первое — привести примеры более профессиональных, гораздо более эффективных методов сортировки массивов. На выбор учителя, это может быть сортировка Шелла, сортировка выбором с помощью дерева, шейкерная сортировка и др. Соответствующие алгоритмы описаны во многих пособиях. Следует учесть, что для их восприятия и реализации требуется существенно больше усилий, чем для простейших методов.
Второе направление развития этой темы — внешняя сортировка. По своей практической важности она еще выше. Объясните учащимся постановку задачи. Сколь бы ни была велика оперативная память современных ЭВМ, она все же гораздо меньше, чем объем многих структур, нуждающихся в сортировке.
На практике чаще всего в виде таких структур выступают файлы, которые нельзя целиком загрузить в оперативную память (если это можно сделать, то сортировка файла прямого доступа ничем не будет отличаться от сортировки массива). Сортировка файла, не помещающегося в ОЗУ, — внешняя сортировка, и рассмотренные выше методы неприменимы в принципе. Подведите учащихся к центральному приему внешней сортировки: загрузить файл в ОЗУ по частям, отсортировать эти части, а затем надо что-то предпринять, чтобы получить полностью отсортированный файл. Конкретные приемы внешней сортировки описаны в литературе по программированию.
Во вводной части лекции следует объяснить учащимся, что только с появлением модулей Паскаль стал средством разработки больших профессиональных программных комплексов. Модуль, как и процедуры, служит реализации идеи модульности — выделения подзадач внутри большой задачи. Отличие модуля от набора «внутренних» процедур — возможность отдельной трансляции и отдельного от программы хранения; к модулю может обращаться не °Дна программа, а много разных программ. Благодаря модулям в Паскале возможно организовывать внешние библиотеки программ По различным проблемам.
Целью школьного спецкурса не может быть самостоятельная Разработка учащимися модулей. Такое задание возможно в качестве проекта для некоторых учащихся, а для большинства эта тема является ознакомительной. Вполне достаточно привести примеры двух-трех несложных модулей и разобрать как их внутреннее устройство, так и механизм взаимодействия с обращающимися к ним программами.
Описав общую структуру модуля и объяснив назначение основных его разделов (заголовок, интерфейсная часть, раздел реализации, раздел инициализации), приведите пример модуля. Допустим, мы хотим дополнить'Паскаль средствами работы с комплексными числами (хотя бы на уровне четырех арифметических действий). В школе, в которой углубленно изучается программирование, учащиеся скорее всего с комплексными числами знакомы. Возможны два подхода к реализации этой задачи.
1. Комплексное число представляется парой действительных (а, Ь). Конструируют четыре процедуры — действия над комплексными числами; у каждой из них по 4 параметра-значения и по 2 параметра-переменных. Сводят их в модуль, в интерфейсной части которого находятся заголовки этих процедур.
Показывают, как обращается к нему внешняя программа, объясняют смысл
[ 
«