ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6594
Скачиваний: 50
56
люции компьютеров. Первоначально, в эпоху ЭВМ 1 -го и 2-го поколений, когда они были еще
мало распространены, машинное время было дорого, а возможности ЭВМ очень скромны (с точки
зрения сегодняшних достижений), основным требованием к алгоритму была его узко понимаемая
эффективность:
1) минимальные требования в отношении оперативной памяти компьютера -.программа
должна была использовать наименьшее возможное число ячеек оперативной памяти компьютера;
2) минимальное время исполнения (минимальное число операций). При этом программы
составлялись из команд, непосредственно или почти непосредственно исполнявшихся компьюте-
ром (точнее говоря, процессором):
• операции присваивания;
• простейших арифметических операций;
• операций сравнения чисел;
• операторов безусловного и условных переходов (изменяющих порядок вычисления ко-
манд в программе);
• операторов вызова подпрограмм (вспомогательных алгоритмов).
Такой подход в программировании (создании алгоритмов), ориентированный на непосред-
ственно выполняемые компьютером операции, можно назвать операциональным.
Рассмотрим подробнее операции, которые выполняются компьютером и которые являются
шагами программы при операциональном подходе.
Операция присваивания состоит в том, что некоторое значение фигурирующей в программе
величины помещается в ячейку памяти компьютера. Эта ячейка может либо принадлежать опера-
тивной памяти, либо находиться в арифметико-логическом устройстве, выполняющем основные
операции (это устройство - часть процессора). После операции присваивания указанное значение
сохраняется в ячейке памяти, куда оно было помещено, пока не будет заменено другим в результа-
те другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается
именем (идентификатором) соответствующей переменной. Примеры идентификаторов:
а, х, у
1
, у
2
.
Важно помнить, что переменные и, соответственно, их значения могут быть разных типов - число-
вые (целые или действительные), литерные или логические. Значения различных типов представ-
ляются (кодируются) в компьютере по-разному, поэтому они должны соответствовать типам пе-
ременных, которым они присваиваются. При разработке алгоритма следует всегда помнить и
'тщательно различать типы переменных.
Набор простейших арифметических операций «сложения» (+), «вычитания» (-), «умноже-
ния» (*) и «деления» (/) (причем во многих случаях следует тщательно отличать деление, выпол-
няемое над целыми числами - в этом случае операция деления распадается на деление нацело и
вычисление остатка от деления) позволяет записывать арифметические выражения с использова-
нием числовых констант и идентификаторов переменных. Для определения порядка операций в
выражениях чаще всего используют стандартное математическое соглашение о старшинстве опе-
рации, согласно которому старшими и выполняемыми в 1-ю очередь являются умножение и деле-
ние, а младшими - сложение и вычитание. Для изменения «естественного» порядка выполняемых
операций служат скобки. Сравните, например, порядок операций в выражениях:
(а
+ 2) *
х
и а + 2 *
х.
Что же касается порядка выполнения операций одного старшинства, то они, как правило,
выполняются в порядке записи в выражении.
Операция сравнения числовых значений фактически сводится к определению знака разно-
сти этих значений. Этот знак отображается с помощью специальной ячейки памяти (флага знака
результата) вычислительного устройства компьютера и может использоваться при выполнении
условных переходов между командами (шагами) алгоритма.
Чтобы понять, что такое условные и безусловные переходы при выполнении алгоритма, на-
до исходить из того, что шаги или команды алгоритма обладают метками или адресами, и, помимо
естественного порядка выполнения команд соответственно их записи, возможен и другой порядок,
при котором последовательность выполнения команд определяется переходами на команды с оп-
ределенными метками или адресами.
Безусловным
называется переход, для которого изменение
порядка выполнения команд раз и навсегда определено и не зависит ни от каких условий. Услов-
57
ным называется переход, для которого порядок выполнения команд определяется по некоторому
условию, чаще всего условию сравнения величин числовых типов.
Операция вызова подпрограммы (вспомогательного алгоритма) - это такой переход в по-
следовательности команд алгоритма, при котором на определенном этапе выполнения алгоритма
происходит вначале переход на другую программу (подпрограмму по отношению к той, откуда
совершен переход), а затем, после ее завершения, возврат в точку вызова подпрограммы и про-
должение выполнения команд, начиная со следующей после команды вызова подпрограммы, в-их
естественном порядке. Очевидно, что операция вызова подпрограммы представляет собой пере-
ход, при котором запоминается адрес команды, следующей за командой вызова подпрограммы,
что позволяет вернуться к исходному алгоритму (головной программе) после выполнения вспомо-
гательного алгоритма (подпрограммы).
Отметим, что универсальность существующих компьютеров достигается за счет опреде-
ленного набора команд, типа только что описанного, и автоматического механизма их выполне-
ния, а проблема решения задачи с помощью компьютера состоит лишь в преобразовании решае-
мой задачи в последовательность этих команд. В качестве примера рассмотрим операциональное
представление алгоритма вычисления квадратного корня из положительного числа
а
с помощью
рекуррентной формулы:
n = 0,1,2,...
Можно показать, что
a
x
n
n
lim
.
Будем обозначать через
x
0
нулевое приближение (за него в данном случае можно принять
любое положительное число), через
заданную точность вычислений и через
c
0
какое-нибудь чис-
ло, удовлетворяющее условию 0 <
c
0
<
a
, необходимое для оценки достигнутой точности с по-
мощью неравенства
Алгоритм вычисления
a .
1) ввести числа
а,
, x
0
, c
0
;
2) присвоить переменной
х
значение
у,
3) присвоить переменной
у
значение
а/х;
4) присвоить переменной
у
значение
х
+
у,
5) присвоить переменной
х
значение
у/2;
6) присвоить переменной
у
значение
x
2
;
7) присвоить переменной
у
значение
y-а;
8) присвоить переменной
у
значение
у/c
0
;
9)
присвоить переменной
значение
у/2;
10) сравнить
и
; если
>
,
то перейти к команде 3, иначе перейти к следующей команде;
11) вывести числа
х, а
и
;
12) стоп.
В этом алгоритме все команды, кроме 10, предполагают переход к следующим за ними по
записи командам, и лишь команда 10, являющаяся командой условного перехода, меняет порядок
исполнения команд - после нее в нарушение порядка может выполняться команда 3, т.е. она опре-
деляет циклическую конструкцию в алгоритме.
Поясним эту программу. Команда 2 помещает значение начального приближения
x
0
в ячей-
ку памяти, в которой хранятся значения переменной
х
(на каждом этапе вычислений в этой ячейке
хранится значение
х,
равное значению одного из членов рекуррентной последовательности
x
n
).
Команды 3-5 вычисляют по числу
х
число
(х
+
а/х)/2.
Результат помещается в ячейку памя-
ти, в которой хранится значение переменной
х,
при этом старое значение «стирается» новым. Ко-
манды 6-9 вычисляют величину
58
0
2
2
/
)
(
c
a
x
,
с помощью которой оценивается сверху разность
х -
a
. Важное значение имеет команда
10. По ней не производятся вычисления, а сравниваются между собой вычисленное значение 5 и
заданная точность
.
Если
>
, то управляющее устройство вернет вычислительный процесс к
команде 3 и заставит повторить процесс.
В противном случае, когда требуемая точность достигнута, печатается полученный резуль-
тат и работа прекращается.
Данный алгоритм весьма экономичен: в качестве рабочих он использует всего две ячейки
памяти (для переменных
х
и
у),
его команды так продуманы, что никакие операции не выполняют-
ся с избыточным повторением.
В данном примере не были использованы какие-либо специальные обозначения команд,
чтобы сделать их независимыми от языка конкретных ЭВМ (такие языки называют Ассемблера-
ми), чтобы стал ясен общий характер операционального подхода к разработке алгоритмов. Одна-
ко, ориентированность этого подхода на возможности и особенности ЭВМ с появлением большого
числа компьютеров 3-го и особенно 4-го поколений не позволяла перейти к массовому промыш-
ленному программированию и стала сдерживать развитие вычислительной техники. Отметим ос-
новные недостатки алгоритмов, к которым приводил операциональный подход:
• злоупотребление командой условного и безусловного переходов зачастую приводило к
очень запутанной структуре программы, напоминавшей по образному сравнению «блюдо спагет-
ти»;
• вместе с разнообразными уловками, направленными на повышение эффективности про-
граммы (т.е. минимальных требований к оперативной памяти и минимального времени выполне-
ния), это приводило к непонятности программ, их ненадежности, трудностям в отладке и модифи-
кации, делая программирование трудоемким, сложным и чрезвычайно дорогостоящим.
Необходимость ориентироваться на ограниченный набор команд компьютера, на его
скромные возможности приводила к огромной трудоемкости, к сложности программ, к пробле-
мам, связанным с ошибками в них. В результате узким местом в развитии вычислительной техни-
ки оказалось именно программирование.
8.2. СТРУКТУРНЫЙ ПОДХОД
С появлением массовых ЭВМ 3-го поколения устаревшая технология программирования
оказалась основным фактором, сдерживающим развитие и распространение компьютерных (ин-
формационных) технологий, что подтолкнуло ведущие в этой сфере деятельности фирмы, в пер-
вую очередь IBM, к разработке новых методологий программирования. Появившийся в начале
1970-х годов новый подход к разработке алгоритмов получил название структурного.
С появлением структурного программирования описанные выше трудности были во мно-
гом преодолены. В основе технологических принципов структурного программирования лежит
утверждение о том, что логическая структура программы может быть выражена комбинацией трех
базовых структур: следования, ветвления и цикла (это содержание теоремы Бема-Якопини).
Следование
- самая важная из структур. Она означает, что действия могут быть выполнены
друг за другом, рис. 1.19:
Рис. 1.19.
Структура «следование»
Эти прямоугольники могут представлять как одну единственную команду, так и множество
операторов, необходимых для выполнения сложной обработки данных.
Ветвление
- это структура, обеспечивающая выбор между двумя альтернативами. Выпол-
няется проверка, а затем выбирается один из путей (рис. 1.20).
Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каждый из путей
59
(ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается не-
зависимо от того, какой путь был выбран.
Рис. 1.20.
Структура «ветвление»
Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В
этом случае можно применять только один обрабатывающий блок, рис.1.21:
Рис. 1.21.
Структура «неполное ветвление»
Цикл (или повторение) предусматривает повторное выполнение некоторого Набора команд
программы. Если бы циклы не существовали, вряд ли занятие программированием было бы оп-
равданным: циклы позволяют записать длинные последовательности операций обработки данных
с помощью небольшого числа повторяющихся команд. Разновидности цикла изображены на рис.
1.22 и рис. 1.23.
Цикл начинается с проверки логического выражения. Если оно истинно, то выполняется
«
a
», затем все повторяется снова, пока логическое выражение сохраняет значение «истина». Как
только оно становится ложным, выполнение операций «а» прекращается и управление передается
по программе дальше.
Рис. 1.22.
Структура цикла «пока»
Рис. 1.23.
Структура цикла «до»
60
Рис. 1.24.
Нахождение суммы трех чисел
Рис. 1.25.
Нахождение наибольшего из трех чисел
Эти структуры можно комбинировать одну с другой - как путем организации их следова-
ний, так и путем создания суперпозиций (вложений одной структуры в другую) - сколь угодно
разнообразно для выражения логики алгоритма решения любой задачи. Используя описанные
структуры, можно полностью исключить использование каких-либо еще операторов условного и
безусловного перехода, что является важным признаком структурного программирования. На-
правление выполнения команд часто изображают сверху вниз. На рис. 1.24 - 1.26 приведены про-
стейшие примеры структурной реализации алгоритмов работы с величинами.