Имя материала: Методика преподавания информатики

Автор: М.П.ЛАПЧИК

15.1. методика обучения структурному программированию

 

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

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

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

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

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

 

Тема «Алгоритмы. Структурная алгоритмизация»

 

Форма изложения материала — сочетание лекции с практическими занятиями. На лекции вспоминают и уточняют понятие «алгоритм», введенное в базовом курсе информатики, и обсуждают особенности алгоритмов, исполнителем которых является компьютер. Далее переходят к способам записи алгоритмов, акцентируя внимание на блок-схемах, приводят примеры нескольких простейших линейных алгоритмов.

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

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

 

 

Рис. 15.2. Схема структуры «выбор»

 

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

 

                          

 

Рис. 15.3. Пример вложенной структуры

 

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

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

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

 

Подпись: Здесь k — номер подпрограм-мы 
(вспомогательного алгоритма).

 

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

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

 

Тема «Введение в Паскаль»

 

Форма изложения материала — лекционная. Рассматриваются вопросы:

• что такое программирование;

• краткая история развития языков программирования;

• классификация методических подходов («парадигм») в программировании;

• язык Паскаль, история его создания и развития, области применения;

• структура программы на Паскале;

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

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

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

 

программа = заголовок + блок + точка, блок = [описание меток] + [определение констант] + [определение типов] + [описание переменных] + [описание процедур и функций] + составной оператор

 

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

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

 

Тема «Данные. Типы данных. Выражения»

 

Мысль о том, что объект обработки (данные) не менее важен, чем орудийные средства (алгоритмы, операторы), следует внедрять на самой ранней стадии изучения программирования.

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

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

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

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

Разговор о типах данных разумно привязать к изучаемому языку (т. е. Паскалю). Введите четыре стандартных типа (целочисленный — integer, вещественный — real, логический (булевский) — boolean и символьный — char), покажите, какие значения могут принимать величины этих типов. Укажите на обязательность явного описания типов переменных в Паскале и покажите на примерах, как это сделать. Рассказ о том, что в Турбо Паскале на базе целочисленного и вещественного типов образованы одноименные группы типов, можно отложить на тот момент, когда стандартных типов real и integer станет недостаточно для решения задач.

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

а) тип выражения определяется типом принимаемых им значений;

б) типов выражений потенциально столько же, сколько типов данных в языке программирования.

Уточните понятия операнд, функция, знак операции и на примерах отрабатывайте правила конструирования арифметических выражений. Попутно введите арифметические действия (в том числе и непривычные div и mod), стандартные математические функции, четко указывая для каждой из них тип аргумента и тип значения. Удобно сгруппировать эту информацию в таблицу, рассказать о «необычных» (на уровне школьного математического образования) функциях и объяснить смысл двойного вхождения некоторых из функций в таблицу (табл. 15.1).

Таблица 15.1

 

 

Значение

Аргумент

real

integer

integer

abs(X), sqr(x)

round (x), trunc (x)

real

sin(x), cos(x), arctan(x), ln(x), exp(x), sqrt(x)

abs(x), sqr(x), sin(x), cos(x), arctan(x), ln(x), exp(x), sqrt(x), int(x)

 

Большая часть этих функций не вызывает затруднений, так как знакома по курсу математики. Однако такие функции, как trunc и round требуют комментариев. Это функции преобразования типов, и нетривиальность равенства trunc(5.0) = 5 должна стать темой обсуждения.

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

В связи с введением функции ord(x) уместен разговор о различии понятий упорядоченный и порядковый тип (в некоторых пособиях используется иная терминология, но существо дела от этого не меняется). Все четыре базовых типа являются упорядоченными, так как внутри каждого из них возможно сравнение элементов по ≤ ≠ ≥ < > =. Однако тип real, в отличие от остальных трех, не является порядковым, так как в нем нельзя пронумеровать элементы. Это существенно сказывается на ряде моментов в программировании (например, величину этого типа нельзя использовать как аргумент функции ord).

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

После усвоения этого материала перейдите к построению нематематических выражений. На данном этапе, до введения строковых величин, отрабатывайте лишь логические выражения. Введите основные логические операции И, ИЛИ, НЕ и запишите для них таблицы истинности. Далее, не прибегая к нотациям Паскаля, строят простые логические выражения и показывают, как вычисляются их значения. При этом используют в этих выражениях как переменные величины, так и логические константы. Например: (А Ù В) Ú С, А Ù (В ÙØ С) Ù true и т.п.

Затем вводят нотации Паскаля и продолжают отработку навыков вычисления логических выражений, вводя в них элементы — сравнения. Например: (А < В) or С. На примере такого выражения (и ему подобных) можно объяснить, что сравнение по ≤ ≠  ≥ < > = возможно и для величин нечисловой природы (любых упорядоченных, в частности, для символьных и логических).

 

Тема «Операторы»

 

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

Начинать надо с тщательной отработки понятия присваивание, без которого в дальнейшем многое не будет правильно воспринято. Вопрос представляется крайне простым: вычисляется значение выражения, стоящего справа от знака := и его получает переменная величина, стоящая слева от этого знака. Однако понимание этого приходит не сразу. В частности, необходимо на примерах величин различных типов пояснить, что до первого присваивания переменная вообще не имеет значения.

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

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

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

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

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

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

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

Как правило, при организации циклических процессов при заранее известном числе выполнения тела цикла наиболее удобен цикл с параметром (цикл for). Познакомьте с ним учащихся; обратите внимание, что по организации работы в Паскале этот цикл вначале проверяет условие, а затем реализует тело цикла. Цикл for устроен достаточно сложно, и детальное, по пунктам, «проговаривание» порядка его исполнения существенно помогает пониманию темы. Обратите внимание учащихся на то, что параметр цикла может иметь не только тип integer, но и любой порядковый тип. Разберите, например, задачу: вывести на экран последовательность латинских букв а, Ь, ..., z- Достичь этого можно, например, так:

 

var i, j, k: integer;

…………………………………………………………………………

i:=ord(a); j:=ord(z); for k:=i to j do write (chr(k), '_')

 

но можно и более изящно:

 

var с:char;

………………………………………………………………………

for c:= 'a' to 'z' do write (c, '_')

 

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

Необходимо показать учащимся и задачи, в которых цикл с параметром неприменим (или применение его требует особых ухищрений). Это, прежде всего, итерационные циклические процессы, в которых выход из цикла определяется не заранее известным числом шагов, а условием, связанным с чем-то, вычисляемым в теле цикла. Хорошим примером будут математические задачи типа: найти приближенное значение  по итерационной формуле   с выходом из итераций при достижении условия |хя+1 - х„| < е.

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

 

Тема «Перечислимый и интервальный типы данных»

 

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

Начните эту тему с примеров описания типов. Некоторая свобода, допускаемая Паскалем при выборе средств описания между разделами var и type, может быть при начальном изучении языка ликвидирована выбором в пользу var. Однако, начиная с данной темы, использование type становится неизбежным.

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

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

С интервальным типом проблем гораздо меньше. Фактически отдельные задачи на отработку навыков использования этого типа данных решать необязательно. В дальнейшем, особенно при описании массивов, использование интервального типа станет обычным (и не всегда осознаваемым) делом.

 

Тема «Процедуры и функции»

 

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

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

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

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

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

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

Нелегко также учащимся понять различия между формальными параметрами-значениями и параметрами-переменными. Многословные объяснения в ряде руководств иногда лишь затрудняют понимание этого важного вопроса. Для начала вполне достаточно, если в разбираемых примерах процедур параметры будут четко подразделяться на входные и выходные и будет соблюдаться простое правило: входные параметры есть параметры-значения, выходные — параметры-переменные. Это правило страхует от ошибок, связанных с непониманием механизмов замещения параметров при обращении к процедуре. Разумеется, впоследствии этот вопрос должен быть отработан глубже.

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

 

Задание 1. Вычислить периметр треугольника по координатам его вершин.

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

 

Задание 2. Найти наибольший общий делитель (НОД) 100 натуральных чисел по алгоритму Евклида.

Процедура — НОД двух чисел. В заголовке — три переменные. Две из них — параметры-значения, третья — переменная (результат).

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

 

program parametr;

var k: integer;

procedure plusl (n: integer);

begin n:=n+10

end;

procudure plas2 (var n: integer);

begin n:=n+20

end;

begin

k:=10; plusl(k); writeln(k);

k:=10; plus2(k); writeln(k)

end.

 

Объясните, почему в первой печати результат оказался равен 20, а во второй — 30.

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

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

               

 

Рис. 15.4. Взаимное расположение описаний процедур

 

Объясните, почему из основной программы можно обратиться к подпрограммам А и В, из А1 — к А2, но не наоборот, из В1 можно обратиться к А, но нельзя к А1 и т.д.

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

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

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

 

Тема «Структурированные типы данных»

 

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

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

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

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

 

 

Рис. 15.5. Типы данных Турбо Паскаля

 

Массивы

 

Изучение структурированных типов начните с наиболее традиционного — массива. Подчеркните его групповые свойства: упорядоченная однородная статическая структура прямого доступа; приведите обоснование этих свойств.

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

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

 

Var A: array [1980..2000,1.. 15] of real

 

вместо альтернативного, явно отражающего фразу «массив массивов»:

 

Var A: array [1980 .. 2000] of array [1 .. 15] of real

 

Далее, на первом этапе изучения языка вносит путаницу наличие еще одной альтернативы — описание массива, сочетая type и var. На том же примере это выглядит так:

 

Туре В = array [1980 .. 2000,1 .. 15] of real

Var А:В

 

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

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

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

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

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

 

Строки

 

Очень полезный тип данных, которого не было в базовой версии Паскаля.

Вначале напомните учащимся, что в приложениях современной информатики обработка текстов является самым распространенным видом деятельности. Если вся задача состоит из обработки текста, то для этого существуют мощные специализированные программные средства — текстовые процессоры. Однако встречаются ситуации, когда обработка текста — часть задачи, решаемой алгоритмически, путем традиционного программирования. В этом случае нужны специальные структуры данных и средства их обработки. Покажите учащимся способ задания типа string. Нетривиально то, что хотя при задании строки ее максимальная длина часто указывается, величина является квазидинамической, т.е. ее реальный размер определяется текущим значением (хотя память все же резервируется по максимуму). Покажите автоматическую нумерацию элементов строки; подчеркните, что в нулевом элементе всегда находится число — автоматически определяемая длина строки. Введите немногие операции, возможные над строками, и особенно детально опишите нетривиальные операции сравнения строк (больше, меньше и т.д.). Важное преимущество строк над другими структурированными данными — возможность ввода-вывода полностью с помощью процедур writeln, readln. В принципе обсуждение этой возможности можно увязать с текстовыми файлами, но это загромождает основной материал.

Введите функции Турбо Паскаля, ориентированные на работу со строками (length, concat, copy, delete, insert, pos), и полезные процедуры преобразования типов (str, val) и можно переходить к решению задач для закрепления навыков работы со строками. Типичные задачи, с которых целесообразно начать эту деятельность, таковы.

1. Определить, сколько раз в данном тексте встречается заданный символ.

2. Заменить в некотором тексте один фрагмент на другой ('Саша' на Маша').

Эту задачу можно решить, как минимум, двумя способами:

а) с использованием функции сору и операции слияния строк;

б) с использованием функций copy, delete и insert.

3. Определить, есть ли в некотором тексте одновременно два заданных слова.

 

Множества

 

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

Итак, перед нами неупорядоченная однородная динамическая структура прямого доступа. При ее изучении и решении задач эти свойства будем подчеркивать.

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

После этого вводите способ описания множественного типа. Базировать его в первых примерах удобно на самостоятельно построенном перечислимом типе (фрукты, животные и т.п.). Тут же подчеркните, что, построив множество, мы потеряли возможность указать порядок следования элементов, так как его нет в принципе. Над элементами величин перечислимого типа можно произвести операции pred, succ, ord, а над множеством, построенном на базе этих величин — нет. Это не сразу осознается. Зато появляются принципиально новые операции, для отработки которых надо привести ряд примеров и решить несколько задач.

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

1. Дана символьная строка. Подсчитать в ней все знаки препинания (. — , ; : ! ?).

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

2. Выбрать все простые числа в диапазоне от 2 до N (соответствующий алгоритм «Решето Эрастофена» приводится в нескольких пособиях по Паскалю в разделе «Множества»).

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

 

Записи

 

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

Далее введите форму описания записи в языке Паскаль и соответствующую терминологию. Полезно иллюстрировать этот рассказ рисунками, не связанными нотациями Паскаля. Например, структура анкеты школьника, изображенная в виде двухуровневого дерева (рис. 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 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 |