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

Файлы

Записи

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

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

Рис. 15.6. Пример структуры типа «запись»

Обратите внимание учащихся на то, что поля записи могут иметь любой тип, в том числе сами могут быть записями. Последнее позволяет строить многоуровневое дерево-анкету. Например, на рис. 15.6 поле «Ф.И.О.» можно сделать записью, состоящей из трех полей: «фамилия», «имя», «отчество».

Необычной конструкцией, связанной с записями, является составное имя поля. Приведите примеры составных имен, объясните, что в пределах действия описания записи ими можно пользоваться как обычными переменными.

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

1. Сформировать массив записей об учащихся своего класса.

2. В сформированном предварительно массиве записей отыскать всех юношей; вывести на экран записи о них.

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

По ходу разработки указанных программ достаточно легко вводится оператор присоединения with. Его назначение предельно просто — в пределах некоторого оператора (чаще всего цикла), один раз указав имя переменной типа «запись», работать с именами полей, как с обычными переменными, т.е. не писать громоздких составных имен.

Обработка массивов записей может выглядеть не очень логично, в связи с чем возникает законный вопрос: неужели всякий раз этот массив надо формировать вводом данных с клавиатуры? В этом отношении гораздо логичнее использовать файлы записей, а к записям следует вернуться после изучения темы «файлы» (или изучать файлы до записей).

Перед нами — одна из центральных структур данных для всех языков программирования высокого уровня.

Некоторые методические трудности при изучении файлов в Паскале возникают из-за многозначности самого термина «файл» в информатике. Между хорошо знакомым учащимся значением слова «файл» в его пользовательском смысле (как поименованной порции информации на внешнем носителе) и одноименной структурой данных Паскаля имеется существенное различие.

Собственно говоря, переменные файлового типа в Паскале вовсе не имеют отношения к вопросу о носителе информации. Если не предпринять специальных (необязательных) усилий, то файловая переменная будет храниться в ОЗУ и при выходе из программы ее значение (как и всех остальных переменных) будет безвозвратно утеряно. Это не сразу осознается учащимися.

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

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

Элемент 0

Элемент 1

.....

Элемент N

маркер конца

Рис. 15.7. Иллюстрация файла

Введите операции «запись в файл» (write) и «чтение из файла» (read). При этом пользуйтесь средствами Турбо Паскаля, которые существенно удобнее операций put и get старых версий. Подчеркните, что запись происходит в текущее окно файла, на которое нацелен указатель, изображенный на рисунке стрелочкой. При записи указатель всегда нацелен на маркер конца (последний после записи передвигается во вновь открываемое окно).

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

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

В Турбо Паскале нет барьера между файлами последовательного и прямого доступа; любую из приведенных выше процедур можно использовать для организации каждого из способов доступа. Обсудив идею того и другого и подчеркнув методические преимущества прямого доступа, вводят средства его организации. К ним относятся логическая функция eof и числовые функции filesize и filepos (но только отчасти, так как со всеми ими приходится работать и при прямом доступе), процедуры seek и truncate.

Для демонстрации различий между последовательным и прямым доступом удобны следующие простейшие задачи:

1. Найти значение 10-го элемента некоторого уже существующего файла.

2. Вывести на экран последний элемент файла.

3. Вывести на экран элементы файла в обратном порядке. Каждую из подобных задач решают дважды: не используя и используя средства прямого доступа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тема «Графические возможности Турбо Паскаля»

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

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

Рассказ о процедурах модуля Graph начните с процедуры перехода в графический режим InitGraph. Надо заметить, что поскольку в модуле Graph более 50 графических процедур и функций, то целесообразно подготовить к занятиям короткий, на одной странице, справочник по основным из них. Поскольку уроки по этой теме ограничатся скорее всего построением простых геометрических примитивов, то именно с этой точки зрения и надо отобрать те процедуры, с которыми следует в первую очередь познакомить учащихся. Все остальные можно всему классу не приводить, а тем учащимся, которые получат задания на разработку соответствующих проектов, предоставить возможность самостоятельного изучения необходимых изобразительных средств.

Приведем список этих основных процедур (их назначение, списки параметров и др. — в любом учебнике по Паскалю, в котором разобран состав модуля Graph):

Arc Bar	CloseGraph Circle
Ellipse FillEllipse	FloodFill InitGraph
Rectangle OutTextXY	OutText PiesLice
PutPixel SetFillStyle	Sector SetLine
StileLine SetTextStyle

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

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

Освоив простейшие приемы графики Паскаля, целесообразно научиться строить графики функций. Это реализует связь с математикой, позволяет освоить масштабирование, формирует навыки пользования «экранной» системой координат. Поскольку эта система направлена нетрадиционно (начало координат — верхний левый угол экрана, ось ординат направлена вниз, а не вверх), то встает задача научиться простым аффинным преобразованиям Координат. Поставленная задача будет полностью выполнена, если Написанная учащимися программа может выполнить следующую Работу: построить на экране график произвольной функции (задаваемой внутри программы в строке function) на произвольном отрезке, координаты которого вводятся в диалоге. График должен включать оси координат, ориентированные традиционным образом, их разметку, кривую, изображающую функцию. Такая программа достаточно сложна; промежуточным этапом может быть построение графика одной хорошо знакомой учащимся функции на фиксированном отрезке (например: построить график функции у = sin(x) на отрезке от 0 до 2p).

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

Тема «Ссылочный тип и динамические структуры данных»

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

В начале обсуждения напомните учащимся различия между статическими и динамическими структурами данных. Далеко не всегда размер структуры очевиден заранее. Приведите примеры, связанные с самой простой из структур данных — массивом.

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

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

Манера описывать в таких случаях упорядоченную однородную линейную структуру данных как массив «с запасом» не соответствует логике таких задач, и в ряде случаев при разработке профессиональных программ вступает в противоречие с ограничениями, налагаемыми Паскалем на максимальный объем памяти, отводимый компилятором под массивы (64 Кбайт).

Разъясните учащимся, что качественного барьера между статическими и динамическими объектами в Паскале нет, так как возможно создание динамических объектов любого типа из числа имеющихся в языке.

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

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

Далее объясните, что такое указатель, какие значения он может принимать и как ссылочный тип технически определяется в программе. Поясните операции сравнения, которые можно проводить над ссылками, и в чем состоит их смысл, введите операции «взятие указателя» и «разыменование».

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

Тут же обсудите проблему ограниченности памяти в «куче», неспособность Турбо Паскаля отследить исчерпание памяти (без специальных усилий программиста) и использование в этих целях специальных средств (функций Maxavail и SizeOf), а также процедуру «очистки мусора» (Dispose).

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

Итак, на простых примерах «из жизни» можно показать полезность следующих динамических структур:

• стек (учащиеся скорее всего с этим понятием знакомы из базового курса информатики);

• линейный список с произвольным доступом (например, список учащихся класса, который может обновляться путем удаления фамилии одного учащегося с последующим смыканием списка, или, наоборот, в который можно вставить фамилию нового ученика на нужное место по алфавиту с раздвижением списка);

• очередь, в которой удаление происходит только через голову списка, а вставка — только через хвост.

Облегчают понимание условные графические изображения структур (рис. 15.8).

Рис. 15.8. Иллюстрация стека и очереди

Методика программирования списков включает ряд задач: связывание компонент, смещение ссылок и т.д. Элементы таких структур методически удобнее всего представлять в виде двухкомпонентных записей. В каждой записи одно из полей — содержательное, второе — для хранения ссылки на другой компонент. Обратите внимание учащихся, что при традиционном хранении элементов в регулярной структуре (массиве) этого не требуется, поскольку каждый элемент «знает», между какими он стоит.

Рассмотрите возможную методику объяснения создания стека. Итак, задача — создать цепочку связанных динамических переменных — целых, например:

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

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

Для ее реализации средствами Паскаля каждый элемент приходится представлять записью с тремя полями: одно — содержание, два — ссылки, рис. 15.9, б. Таким же способом можно реализовать структуру типа «направленный граф» и некоторые другие.

Рис. 15.9. Структура типа «двоичное дерево»

Дата добавления: 2014-12-27