Тема «Важнейшие нечисловые алгоритмы

(поиск и сортировка)»

 

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

Среди этих задач традиционно важнейшее место занимают алгоритмы поиска и сортировки. Обе задачи (тесно связанные между собой) имеют, с одной стороны, очень простую, совершенно прозрачную, постановку, а с другой — огромное прикладное значение для построения баз данных и поиска в них информации.

Задача поиска в общей постановке такова: имеется структурированная величина (массив, файл, массив записей, файл записей и др.), требуется определить, есть ли в ней некоторый объект и ^если да, то на каком месте он находится. На простейших примерах из повседневной жизни легко привести примеры: поиск номера в телефонном справочнике, поиск фамилии ученика в классном журнале, поиск адреса ученика в школьной базе данных, представляющей собой скорее всего файл записей, и т.д.

Поясните учащимся, что поиск путем простого просмотра значений структурированной величины уместен лишь при небольших ее размерах (числе элементов). В современных базах данных, объем которых может составлять несколько террабайтов, такой поиск предельно неэффективен даже на современных ЭВМ, особенно если эта процедура выполняется регулярно. Другое дело, если структура предварительно отсортирована, т.е. элементы в ней расположены в некотором порядке.

Приведите пример: найти в телефонном справочнике большого города номер телефона абонента по фамилии и инициалам легко, а наоборот, по тому же справочнику найти фамилию и инициалы абонента по телефонному номеру — очень большая работа. В чем разница? В первом случае структура упорядочена (по алфавиту), а во втором — нет. Если бы мы имели справочник, в котором номера телефонов расположены в порядке возрастания, то вторая задача решалась бы элементарно, а первая — нет.

Итак, подведите учащихся к мысли: поиск эффективен, а алгоритм его элементарен в упорядоченной (отсортированной) структуре, и переходите к рассмотрению основной задачи — сортировке.

Подчеркните, что термин «нечисловые алгоритмы», использованный выше, вовсе не исключает обработки информации числовой природы. Просто обработка такова, что никакие математические действия не требуются. Все сводится к операциям сравнения и перестановки элементов, а они возможны для любой порядковой структуры. Простейшая задача, которую по традиции рассматривают первой, как раз связана с объектом числовой природы: расположить числа в линейном массиве по возрастанию.

Как ни странно, опыт показывает, что подготовка к решению этой простейшей задачи требует от учителя заметных усилий. Наилучшее решение — подготовить материальную модель, расположив на листе ватмана линейную цепочку карманчиков, в которые можно вставлять карточки с числами — так, чтобы они были все время видны учащимся, и иллюстрировать алгоритмы, переставляя карточки из карманчика в карманчик.

Далее изложите два известнейших, фигурирующих во многих пособиях, метода решения указанной задачи: прямых обменов и «пузырька». Целесообразно вначале показать процедуру упорядочения на описанной выше модели, затем составить блок-схему алгоритма и провести ее трассировку, параллельно с этим переставляя карточки на модели; после этого запись на Паскале будет обычным кодированием.

Освоив простейшие схемы сортировки, объясните учащимся их общность. Не так уж важно, что сортировались числовые массивы. Точно так же могут сортироваться массивы символов, массивы записей (по одному из полей — ключу сортировки) и т.д.

Далее можно развивать эту тему в двух направлениях, оба из которых уже не столь просты и представляют практический интерес.

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

Второе направление развития этой темы — внешняя сортировка. По своей практической важности она еще выше. Объясните учащимся постановку задачи. Сколь бы ни была велика оперативная память современных ЭВМ, она все же гораздо меньше, чем объем многих структур, нуждающихся в сортировке. На практике чаще всего в виде таких структур выступают файлы, которые нельзя целиком загрузить в оперативную память (если это можно сделать, то сортировка файла прямого доступа ничем не будет отличаться от сортировки массива). Сортировка файла, не помещающегося в ОЗУ, — внешняя сортировка, и рассмотренные выше методы неприменимы в принципе. Подведите учащихся к центральному приему внешней сортировки: загрузить файл в ОЗУ по частям, отсортировать эти части, а затем надо что-то предпринять, чтобы получить полностью отсортированный файл. Конкретные приемы внешней сортировки описаны в литературе по программированию.

Тема «Модули»

Во вводной части лекции следует объяснить учащимся, что только с появлением модулей Паскаль стал средством разработки больших профессиональных программных комплексов. Модуль, как и процедуры, служит реализации идеи модульности — выделения подзадач внутри большой задачи. Отличие модуля от набора «внутренних» процедур — возможность отдельной трансляции и отдельного от программы хранения; к модулю может обращаться не °Дна программа, а много разных программ. Благодаря модулям в Паскале возможно организовывать внешние библиотеки программ По различным проблемам.

Целью школьного спецкурса не может быть самостоятельная Разработка учащимися модулей. Такое задание возможно в качестве проекта для некоторых учащихся, а для большинства эта тема является ознакомительной. Вполне достаточно привести примеры двух-трех несложных модулей и разобрать как их внутреннее устройство, так и механизм взаимодействия с обращающимися к ним программами.

Описав общую структуру модуля и объяснив назначение основных его разделов (заголовок, интерфейсная часть, раздел реализации, раздел инициализации), приведите пример модуля. Допустим, мы хотим дополнить'Паскаль средствами работы с комплексными числами (хотя бы на уровне четырех арифметических действий). В школе, в которой углубленно изучается программирование, учащиеся скорее всего с комплексными числами знакомы. Возможны два подхода к реализации этой задачи.

1. Комплексное число представляется парой действительных (а, Ь). Конструируют четыре процедуры — действия над комплексными числами; у каждой из них по 4 параметра-значения и по 2 параметра-переменных. Сводят их в модуль, в интерфейсной части которого находятся заголовки этих процедур. Показывают, как обращается к нему внешняя программа, объясняют смысл наличия в ней инструкции uses < список модулей.

2. Комплексное число представляется одним идентификатором, т.е. мы хотим иметь возможность записывать присваивания вида А: = В + ЕС, где А, Ви С — комплексные числа. Эта задача потруднее. Путь к ее решению — создать тип (назвав его Complex), элементы которого — двухполевые записи; первое поле — действительная часть числа, второе — коэффициент при мнимой части.

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

Более детально учащиеся знакомятся с модулями и приходят, в частности, к пониманию сформулированного выше утверждения на примерах стандартных модулей, входящих обычно в комплект программ Турбо Паскаля. Наиболее доступны из них два модуля — Crt (доступ к экрану дисплея в текстовом режиме, работа с клавиатурой, звуком) и Graph (управление графическим режимом работы дисплея).

⇐ Предыдущая48495051525354555657Следующая ⇒

Поделиться: