ПРИНЦИПЫ СТРУКТУРНОЙ АЛГОРИТМИЗАЦИИ

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

 

Структурная алгоритмизация основывается на двух принципах:

1) последовательная детализация "сверху - вниз";

2) ограниченность базового набора структур для построения алгоритмов любой степени сложности.

Из принципов вытекают требования структурного программирования:

1) программа должна составляться мелкими шагами; таким об­разом, сложная задача разбивается на достаточно простые, легко воспринимаемые части;

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

Базовый набор структурной алгоритмизации содержит линейные, разветвляющиеся и циклические структуры.

Можно перечислить основные свойства и достоинства структур­ного программирования:

1) возможность преодоления барьера сложности программ;

2) возможность демонстрации правильности программ на раз­личных этапах решения задачи;

3) наглядность программ;

4) простота модификации (внесение изменений) программ;

 

ОСОБЕННОСТИ МЕТОДИЧЕСКОГО ОБЕСПЕЧЕНИЯ СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ В ВУЗе И БАЗОВОЙ ШКОЛЕ

ВЫБОР ПОДХОДА К ПРЕПОДАВАНИЮ СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ И

ОСОБЕННОСТИ ЕГО МЕТОДИЧЕСКОГООБЕСПЕЧЕНИЯ

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

1) "алгоритмический" подход; его заключается в следующем: схема решения задачи описывается на алгоритмическом языке (языке блок-схем алгоритмов) и затем переводится в програмную реализацию на конкретном языке программирования;

2) "программный" подход - описание решения задачи сразу на конкретном языке программирования.

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

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

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

При изучении программирования с использованием алгоритмичес­кого подхода учащиеся сталкиваются с двумя проблемами:

1) описание и детализация решения задачи на алгоритмическом языке;

2) переход от алгоритмических конструкций к конкретному языку программирования.

На разрешение этих трудностей должно быть направлено методи­ческое обеспечение.

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

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

БАЗОВЫЙ НАБОР СТРУКТУР И ПОСТРОЕНИЕ АЛГОРИТМОВ НА ИХ ОСНОВЕ

Теория структурного программирования доказывает, что алго­ритм любой степени сложности можно построить с помощью основного базового набора структур:

1) последовательная (линейная) структура (рис. 2);

2) ветвящаяся структура (рис. 3, 4);

3) циклическая структура (рис. 5, 6, 7,).

Наиболее простыми для понимания и использования являются ли­нейные структуры. Линейным называется алгоритм (фрагмент алгорит-

ма), в котором отдельные предписания выполняются  в  естественном

порядке (в порядке записи) независимо от значений исходных данных

и промежуточных результатов.

Алгоритм может быть реализован в ЭВМ, если он содержит толь­ко элементарные предписания. Такими элементарными, т.е. не требу­ющими детализации, можно считать следующие предписания или опера­ции:

1) начало, конец;

2) список данных;

3) ввод, вывод;

4) вычислительные операции, реализуемые оператором присваи­вания.

Пример простейшего линейного алгоритма представлен на рис. 9.

Не всякий алгоритм можно описать только линейными структура­ми. Часто для дальнейшей детализации используются ветвящиеся структуры (рис. 3, 4), т.е. такие, в которых в зависимости от ис­ходных данных или промежуточных результатов алгоритм реализуется по одному из нескольких, заранее предусмотренных (возможных) нап­равлений. Такие направления часто называются ветвями.

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

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

В циклических алгоритмах выполнение некоторых операторов (групп операторов) осуществляется многократно с одними и теми же или модифицированными данными.

Циклические алгоритмы часто называют циклами.  В зависимости от способа организации числа повторений различают три типа циклов:

1) цикл с заданным условием продолжения работы (ЦИКЛ - ПО­КА);

2) цикл  с заданным условием окончания работы (ЦИКЛ - ДО);

3) цикл с заданным условием повторений работы (ЦИКЛ С ПАРА­МЕТРОМ).

Структура цикла с заданным условием продолжения работы (ЦИКЛ

- ПОКА) представлена на рис. 5. Тело цикла может включать в себя группу операторов любой степени сложности. При выполнении условия продолжения работы выполняется тело цикла, если же условие не вы­полняется, то работа циклической структуры заканчивается и начи­нается выполнение следующей структуры.

Структура ЦИКЛ - ПОКА предусматривает вариант, когда тело цикла не выполняется ни разу. Такое возможно, если условие, стоя­щее в начале цикла, сразу же не выполняется. Когда на практике возникает необходимость использовать структуру, у которой тело цикла выполняется хотя бы один раз, то в этом случае применяется структура цикла, приведенная на рис. 6.

С помощью такой структуры обычно составляют алгоритмы итера­ционных вычислительных процессов, т.е. таких, в которых для опре­деления последующего значения переменной используется ее предыду­щее значение. Выход из конструкции ЦИКЛ - ДО осуществляется по достижении параметром требуемого значения.

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

В практических инженерных задачах обычно известны начальные значения изменяемых величин, закон изменения и конечное число повторений. Переменная, изменение которой организуется в ходе ре­ализации цикла, называется параметром цикла или управляющей пере­менной. Алгоритм работы цикла с заданным числом повторений предс­тавляет собой соединение линейной структуры (начало цикла), структуры ЦИКЛА - ПОКА (условие в нем заменено на противополож­ное) и снова линейной (последовательной) структуры в теле цикла, см. рис. 8.

Прочитать этот алгоритм можно следующим образом: "меняя па­раметр от начального значения до конечного с шагом < >, повторять тело цикла".

Алгоритм, приведенный на рис. 8, принято называть разверну­той схемой цикла с заданным числом повторений. Такая схема явля­ется очень удобной для анализа алгоритма и поиска ошибок. Однако при написании алгоритма можно использовать и компактную запись, представленную на рис. 7.

Таким образом, с помощью базового набора структур можно построить алгоритм любой степени сложности. Освоив принципы и средства структурной алгоритмизации, обучаемые должны уметь реа­лизовать их на конкретном языке программирования. Следовательно, основной концепцией в изучении ими любого языка програмирования будет являться методика перевода основных базовых структур в конструкции данного языка.

РЕАЛИЗАЦИЯ БАЗОВОГО НАБОРА СТРУКТУР НА ЯЗЫКЕ БЕЙСИК

Операторы программы, написанной на языке Бейсик, выполняются в порядке нумерации строк, где они находятся.

Пример:

10 INPUT A, X

20 X=A+2*X

30 PRINT X

40 END

Номера строк могут иметь целые значения от 0 до 65535. Для изменения построчной последовательности выполнения программы име­ется оператор безусловного перехода GOTO. Он имеет вид:

GOTO  <номер строки>.

При выполнении оператора GOTO программа продолжает выполнят­ся с той строки, которая указана в операторе.

Пример:

.  .  .

20 INPUT F

30 INPUT A, B, C

.  .  .

80 F=A+2*(B-C)

90 GOTO 20

100 PRINT F

.  .  .

В данном случае после строки с номером 90 будет выполнятся строка 20 и далее другие, следующие за ней.

Для организации ветвящихся структур в языке Бейсик имеется оператор условного перехода IF. Он имеет следующий вид:

IF  <условие> THEN  <оператор 1> ELSE <оператор 2>

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

Частные случаи оператора условного перехода IF:

50 IF  <усл.> THEN <оп. 1>

50 IF  <усл.> THEN <ном. строки k> ELSE <оп. 2>

50 IF  <усл.> THEN <ном. строки i> ELSE <ном. строки j>

Оператор IF используется также для организации циклических структур. Структура ЦИКЛА - ПОКА на языке Бейсик записывается следующим образом:

50 IF  <усл.> THEN 60 ELSE 102

60 <оператор тела цикла 1>

.  .  .

100 <оператор тела цикла N>

101 GOTO 50

102 <продолжение программы>

В данном случае, пока параметр цикла удовлетворяет заданному условию, осуществляется переход к телу цикла по строке 60 (THEN

60), и затем, после его выполнения и изменения параметра цикла, программа возвращается к сроке 50 ( 101 GOTO 50) для проверки ус­ловия и т. д. Как только параметр цикла удовлетворит условию, дальнейшее выполнение программы начинается со строки 102 (ELSE

102).

ЦИКЛ - ДО тоже организуется с помощью оператора IF, только тело цикла предшествует проверке условия:

50 <оператор тела цикла 1>

.  .  .

100 <оператор тела цикла N>

101 IF <усл.> THEN 50

102 <продолжение программы>

В данной конструкции тело цикла выполняется до тех пор, пока параметр цикла удовлетворяет условию (ветвь THEN 50).

Для реализации цикла с заданным числом повторений в языке Бейсик имеется специальная конструкция:

50 FOR <параметр>=<нач. знач.> ТО <кон. знач.> STEP<шаг.>

60 <оператор тела цикла 1>

.  .  .

100 <оператор тела цикла N>

101 NEXT <параметр>

102 <продолжение программы>

В строке 50 задаются начальное и конечное значения парамет­ров цикла, а также шаг, с которым осуществляется его изменение каждый раз после выполнения тела цикла (101 NEXT <параметр>). Операторы тела цикла выполняются до тех пор, пока текущее значе­ние параметра не превысит конечного значения, как только это про­изойдет, программа будет выполняться со строки 102.

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

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

ВЫВОДЫ ПО РАЗДЕЛУ

Таким образом, с помощью базового набора структур можно построить алгоритм любой степени сложности. Освоив принципы и средства структурной алгоритмизации, обучаемые должны уметь реа­лизовывать их на конкретном языке программирования. Следователь­но, основной концепцией в изучении ими любого языка программиро­вания будет являться методика перевода основных базовых структур в конструкции изучаемого языка. Основу методического обеспечения в данном случае составляют таблицы перехода от алгоритмических конструкций к конструкциям языка программирования, которые позво­ляют работать с языком пользователю, имеющему минимальный уровень подготовки, и значительно облегчают изучение языка.