Алгоритмизация и программирование

 

Задача 2 естественным образом выводит на идею вспомогательного алгоритма. Задание следующее: составить алгоритм рисования числа «1919». Учитель может поступить следующим образом: предложить ученикам написать алгоритм прежними средствами, т. е. используя только три основные команды: шаг, поворот, прыжок. Такое задание, очевидно, не вызовет энтузиазма учеников, поскольку принцип им уже понятен, а писать длинный линейный алгоритм довольно скучно. В этой ситуации вполне возможно самостоятельное «открытие» учениками идеи вспомогательного алгоритма. Обратив внимание на то, что в рисунке дважды присутствуют цифры «1» и «9», ученики могут прийти к идее отдельного описания алгоритмов рисования этих цифр, а затем использования их для получения четырехзначного числа «1919». После обсуждения этой идеи учитель вводит понятие вспомогательного алгоритма и объясняет, как производится его описание и использование. На языке Кенгуренка вспомогательный алгоритм называется процедурой.

Умение использовать вспомогательные алгоритмы необходимо вырабатывать у учеников как можно раньше, уже на примерах линейных алгоритмов. Важнейший прием алгоритмизации и программирования — декомпозиция задачи, т.е. выделение в исходной задаче некоторых более простых подзадач. Алгоритмы решения таких подзадач называются вспомогательными алгоритмами, а реализующие их программы — подпрограммами (процедурами). Таким образом, решение исходной задачи разбивается на несколько алгоритмов: основной алгоритм и вспомогательные алгоритмы. Как правило, в основном алгоритме происходит многократное обращение к вспомогательному алгоритму.

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

 

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

Механизм обратной связи наглядно иллюстрируется в отладочном режиме исполнения программы. В этом режиме анимационными средствами на экране изображается мальчик Кристоффер, который отдает команды управления Кенгуренку. В начале каждого цикла Кристоффер спрашивает Ру: «Впереди не край?» и получает в ответ: «Да» или «Нет». Дальнейшие действия зависят от ответа.

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

В теории алгоритмов существует два типа циклов: цикл с предусловием и цикл с постусловием. Цикл с предусловием (другое его название — «цикл-пока») является основным видом циклической структуры и достаточен для построения любого циклического алгоритма. В языке исполнителя Кенгуренок имеется только команда «цикл-пока».

 

Задача 4: построить прямоугольную рамку по краю поля. Решение этой задачи требует объединения умений, полученных учениками при решении предыдущих задач. Циклическая программа рисования линии оформляется в виде процедуры ЛИНИЯ. А в основной программе происходит четырехкратное обращение к этой процедуре.

 

Задача 5: расчертить экран горизонтальными линиями. Эта задача является прямым продолжением предыдущей задачи. Усложнение заключается в том, что используются две процедуры: ЛИНИЯ и ВОЗВРАТ. Кроме того, основной алгоритм сам становится циклическим. Здесь снова нужно отметить то важное обстоятельство, что при использовании процедур в основной программе необходимо учитывать начальное и конечное состояние исполнителя при их выполнении.

 

Задача 6: нарисовать орнамент, состоящий из квадратов, расположенных по краю поля. Здесь вводится еще одна структурная команда — ветвление. На примере этой задачи еще раз демонстрируется методика последовательной детализации. Причем, в отличие от предыдущих программ, здесь используется два шага детализации, поскольку в процедуре РЯД содержится обращение к процедуре следующего уровня — КВАДРАТ.

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

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

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

О способах описания алгоритмов. Традиционно в школьной информатике используются два способа описания алгоритмов: блок-схемы и учебный алгоритмический язык. В базовом курсе информатики необходимо использовать обе эти формы. Основное достоинство блок-схем — наглядность алгоритмической структуры. Однако это качество проявляется лишь в том случае, если изображение блок-схемы происходит стандартным способом. Эта тема затрагивается в подразделе 10.1 «Что такое структурное программирование» во второй части учебника [6]. Основным следствием освоения учениками структурной методики должно стать умение при построении алгоритмов «мыслить структурами». Например, исходя из условия задачи, делать следующие выводы: «Алгоритм решения данной задачи будет представлять собой два вложенных цикла: или — цикл с вложенным ветвлением, или — два последовательных цикла» и т.п. Структурно изображенные блок-схемы (рис. 1.4) помогают такому видению алгоритма.

Рис. 11.4. Блок-схемы:

 

Вот, например, две блок-схемы: а — пример структурного изображения алгоритма; б — пример неструктурного изображения алгоритма

На первый взгляд трудно понять, что на двух этих блок-схемах изображен один и тот же алгоритм. Из схемы а четко видна его структура: цикл-пока с вложенным ветвлением. В схеме б довольно сложно усмотреть эту же структуру. Блок-схема а нарисована стандартно, блок-схема б — произвольно.

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

 

Лекция №4 «Методические проблемы изучения алгоритмов работы с величинами»

 

Изучаемые вопросы:

ª ЭВМ — исполнитель алгоритмов.

ª Понятие «величина», характеристики величин.

ª Действия, выполняемые над величинами.

Есть две стороны в обучении алгоритмизации:

— обучение структурной методике .построения алгоритмов;

— обучение методам работы с величинами.

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

ЭВМ — исполнитель алгоритмов. Обсуждение методических вопросов изучения темы «Алгоритмы работы с величинами» будем проводить в программистском аспекте. Составление любой программы для ЭВМ начинается с построения алгоритма. Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет речь в теме «программирование для ЭВМ»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс «ЭВМ + система программирования (СП)». Программист составляет программу на том языке, на который ориентирована СП. Иногда в литературе по программированию такой комплекс называют «виртуальной ЭВМ». Например, компьютер с работающей системой программирования на Бейсике называют «Бейсик-машина»; компьютер с работающей системой программирования на Паскале называют «Паскаль-машина» и т.п. Схематически это изображено на рис. 11.5.

  Рис. 11.5. Взаимодействие программиста  с компьютером

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

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

Процесс программирования делится на три этапа:

1) составление  алгоритма решения задачи;

2) составление  программы на языке программирования;

3) отладка  и тестирование программы.

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

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

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

Рис. 11.6. Уровни данных относительно программы

 

Например, при решении квадратного уравнения: ах2 + bх + с = = 0, исходными данными являются коэффициенты а, b, с; результатами — корни уравнения: х1, х2; промежуточным данным — дискриминант уравнения: D = b2 — 4ас.

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

У всякой величины имеются три основных характеристики: имя, значение и тип. На уровне машинных команд всякая величина идентифицируется адресом ячейки памяти, в которой она хранится, а ее значение — двоичный код в этой ячейке. В алгоритмах и языках программирования величины делятся на константы и переменные.

Константа — неизменная величина и в алгоритме она представляется собственным значением, например: 15, 34.7, 'к', true и пр. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod!5 и пр. Однако ученики должны знать, что и константа, и переменная занимают ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

Таблица 11.1

Свойства основных типов данных

 

Тип	Значения	Операции	Внутреннее представление
Целый	Целые положительные и отрицательные числа в некотором диапазоне. Примеры: 23, -12, 387	Арифметические операции с целыми числами: +, — , х, целое деление и остаток от деления. Операции отношений (<, >, = и др.)	Формат c фиксированной точкой
Вещественный	Любые (целые и дробные) числа в некотором диапазоне. Примеры: 2,5, -0,01, 45,0, 3,6х109	Арифметические операции: +, -, х, /. Операции отношений	Формат с плавающей точкой
Логический	True (истина), False (ложь)	Логические операции: И (and), ИЛИ (or), HE (not). Операции отношений	1 бит: 1 — true; 0 - false
Символьный	Любые символы компьютерного алфавита. Примеры: V, '5', '+', '$'	Операции отношений	Коды таблицы символьной кодировки. 1 символ — 1 байт