Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: СРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ (В C++, PASCALABC, QBASIC).pdf

Исследователь, с именем которого связано превращение программирования из хаотичного интуитивного процесса в упорядоченный научный процесс, — нидерландский ученый Эдсгер Дейкстра (рисунок 7). Он сумел доказать, что программирование является интеллектуальным творчеством и высоким искусством.

Рисунок – Эдгер В. Дейкстра

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

Графическая иллюстрация теоремы Бема-Якопини представлена на рисунке 8.

Рисунок – Иллюстрация теоремы Бема-Якопини

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

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

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

2.2 Простая команда

Элементарной структурной единицей любого алгоритма является простая команда.

Простая команда представляет один простейший этап переработки или передачи информации.

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

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

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

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

Значение переменной может быть изменено, например, при помощи команды присваивания:

<идентификатор> := <выражение> //Pascal

<идентификатор> = <выражение> //C++, Basic

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

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

Например, в языке программирования PascalABC оператором ввода информации служит команда read() и ее модификации, оператором вывода write() и ее разновидности:

read (a,n); // Ввод значений a,n

writeln(‘a = ‘,a); // Вывод значения переменной a

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

Рисунок – Простая команда

2.3 Составные команды

Составная команда строится из последовательности команд, идущих одна за другой.

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

Общий вид команды следования:

начало

<команда 1> ;

<команда 2> ;

… ;

<команда N>

конец;

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

Блок-схема линейного алгоритма представлена на рисунке 10.

Рисунок – Линейный алгоритм

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

если < условие >

то < команда 1 >

иначе <команда 2 >

все

Блок-схема разветвляющегося алгоритма представлена на рисунке 11.

Рисунок – Разветвляющийся алгоритм

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

Рисунок – Неполная форма ветвления

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

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

В программировании используются несколько видов цикла.

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

повторять

< команда >;

Блок-схема бесконечного цикла представлена на рисунке 13.

Рисунок – Бесконечный цикл

Традиционно в программировании выделяют три вида цикла:

цикл с предусловием;
цикл с постусловием;
цикл с параметром.

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

пока < условие > повторять

< команда >;

Блок-схема цикла с предусловием представлена на рисунке 14.

Рисунок – Цикл с предусловием

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

В отличие от цикла с предусловием, цикл с постусловием (цикл – до) предусматривает выполнение команды как минимум один раз:

повторять

< команда >

до < условие >;

Блок-схема цикла с предусловием представлена на рисунке 15.

Рисунок – Цикл с постусловием

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

Цикл с параметром используется в различных модификациях:

для всякого элемента х принадлежащего М выполнить

< команда >;

для х принадлежащего М пока < условие > повторять

< команда >;

для х от m до n повторять

< команда >;

для х от m до n шаг h повторять

< команда >;

Блок-схема цикла с предусловием представлена на рисунке 16.

Рисунок – Цикл с параметрами

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

3 РЕАЛИЗАЦИЯ ОСНОВНЫХ АЛГОРИТМИЧЕСКИХ СТРУКТУР В C++, PASCALABC, QBASIC

3.1 Следование

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

Чаще всего в линейном алгоритме используются операторы ввода и вывода информации и присваивания.

Оператор присваивания используют для присваивания переменной, стоящей слева от знака присваивания, значения выражения, указанного в правой части. Реализация оператора присваивания в языках программирования C++, PascalABC, QBasic представлена в таблице 1.

Таблица – Реализация оператора присваивания

Язык программирования	Оператор присваивания	Пример использования
C++	=	A = 3*b + 7.5
PascalABC	:=	A: = 3*b + 7.5
QBasic	=	A = 3*b + 7.5

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

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

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

Реализация ввода в языках программирования C++, PascalABC, QBasic представлена в таблице 2.

Таблица – Реализация оператора ввода информации

Язык программирования	Оператор ввода информации	Пример использования
C++	форматированный ввод scanf (<список ввода>); потоковый ввод cin>> (<имя переменной>);	scanf("%d%d",&x,&y); cin>>x; cin>>y;
PascalABC	без переноса курсора на следующую строку read (<список ввода>); с переносом курсора на следующую строку readln (<список ввода>); специальные функции PascalABC ReadInt(‘<комментарий>’); для разных типов переменных	read (x, y); readln(x, y); x := ReadInteger(‘<комментарий>’); y := ReadlnReal(‘<комментарий>’);
QBasic	INPUT <комментарий>, <список ввода>	INPUT “Введите значения X и Y”, X, Y

Несмотря на синтаксические различия в записи оператора ввода на разных языках программирования, результат использования представленных в таблице 2 примеров будет одинаковым – переменным x и y будут присвоены значения, введенные пользователем с клавиатуры.

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

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

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