ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6591
Скачиваний: 50
61
Рис. 1.26.
Нахождение суммы 100 чисел
Умение образовывать из базовых структур их суперпозиции в соответствии с условиями
конкретной задачи - одно из важнейших в программировании. Допустим, надо ввести в память
компьютера 100 чисел и по дороге отсуммировать те из них, которые положительны. Ясно, что
ввод - операция циклическая, а внутри этого цикла находится развилка, в которой проверяется
знак числа и производится суммирование. Схематически соответствующая суперпозиция изобра-
жена на рис. 1.27.
Так как выражение, управляющее циклом, проверяется в самом начале, то в случае, если
условие сразу окажется ложным, операторы циклической части «
a
» могут вообще не выполняться.
Операторы циклической части «
а
» должны изменять переменную (или переменные), влияющие на
значение логического выражения, иначе программа «зациклится» - будет выполняться бесконечно.
Рассмотренная циклическая конструкция называется также цикл «пока», или «цикл с предуслови-
ем».
Существует и иная конструкция цикла, которая предусматривает проверку условия, по ко-
торому, наоборот, выполнение команд циклической части прекращается, после команд цикличе-
ской части (см. рис. 1.23).
62
Рис 1.27
Алгоритм типа развилка, вложенная в цикл,
для нахождения суммы положительных чисел из 100 возможных
Схематические изображения нескольких суперпозиций базовых алгоритмических структур
представлены ниже на рис. 1.28-1.31.
Еще одним важным компонентом структурного подхода к разработке алгоритмов является
модульность. Модуль - это последовательность логически связанных операций, оформленных как
отдельная часть программы. Использование модулей имеет следующие преимущества:
1) возможность создания программы несколькими программистами;
2) простота проектирования и последующих модификаций программы;
3) упрощение отладки программы - поиска и устранения в ней ошибок;
4) возможность использования готовых библиотек наиболее употребительных модулей.
Но, пожалуй, самым важным достижением структурного подхода к разработке алгоритмов
является нисходящее проектирование программ, основанное на идее уровней абстракции, которые
становятся уровнями модулей в разрабатываемой программе. На этапе проектирования строится
схема иерархии, изображающая эти уровни. Схема иерархии позволяет программисту сначала
сконцентрировать внимание на определении того, что надо сделать в программе, а лишь затем ре-
шать, как это надо делать. При нисходящем проектировании исходная, подлежащая решению за-
дача разбивается на ряд подзадач, подчиненных по своему содержанию главной задаче. Такое раз-
биение называется детализацией или декомпозицией.
Рис. 1.28.
Алгоритм типа «цикл,
вложенный в неполную развилку»
Рис. 1.29.
Алгоритм типа «цикл в цикле»
63
Рис. 1.30.
Алгоритм типа «развилка в развилке»
Рис. 1.31.
Иллюстрация трехкратного вложения
одной базовой структуры в другую
На следующем этапе эти задачи, в свою очередь, разбиваются на более мелкие подчинен-
ные подзадачи и так далее, до уровня относительно небольших подзадач, вторые требуют для ре-
шения небольших модулей в 3 - 5 строк. Такой метод роектирования программ позволяет преодо-
левать проблему сложности разработки программы (и ее последующей отладки и сопровождения).
8.3. НОВЕЙШИЕ МЕТОДОЛОГИИ РАЗРАБОТКИ ПРОГРАММ ДЛЯ ЭВМ
Структурный подход сыграл огромную роль в программировании и вычислительной техни-
ке. С его использованием создан большой запас программного обеспечения, решено множество
практически значимых задач. Однако, развитие программирования на этом не остановилось. Сего-
дня дополняющим структурное программирование, создающим основу для разработки современ-
ных аудиовизуаль-программных комплексов стало объектное (иногда говорят объектно-
ориентированное) программирование, а противостоящим ему при решении определенных классов
задач является декларативное программирование, выраженное двумя разными подходами - функ-
циональным и логическим.
Здесь мы ограничимся кратчайшей характеристикой этих направлений, более детально
описанных в гл. 3.
Само структурное программирование, наиболее отчетливо выраженное в языке Паскаль
(PASCAL), возникло в ходе развития процедурно-ориентированного подхода, заложенного в исто-
рически первом из языков программирования - Фортране (FORTRAN). Во всех языках этого на-
правления разработчик алгоритма (он же, как правило, и программист) описывает, какими дейст-
виями следует реализовать процесс. В основе языков этой группы лежат понятия команд (опера-
торов) и данных. Отдельные группы операторов могут объединяться во вспомогательные алго-
ритмы (процедуры, подпрограммы).
Объект - основное понятие объектного программирования - в первом приближении похож
на процедуру. Однако, процедура (подпрограмма) «оживает» лишь внутри той программы, к кото-
рой она относится, а объект может вести себя вполне независимо. Он может относиться к иной
предметной области нежели основная программа, быть исполненным в ином стиле. Объекты дос-
таточно причудливо связываются друг с другом, могут перенимать свойства друг у друга («насле-
дование»). В объектно-ориентированном подходе исходная задача представляется как совокуп-
ность взаимодействующих объектов. Наиболее популярные реализации объектного программиро-
вания созданы на основе языков Паскаль, Бейсик (BASIC).
Декларативный подход в разработке компьютерных программ появился в начале 70-х го-
дов. Он не получил столь широкого применения как процедурный, поскольку был направлен на
относительно узкий круг задач искусственного интеллекта. При его применении программист
описывает свойства исходных данных, их взаимосвязи, свойства, которыми должен обладать ре-
зультат, а не алгоритм получения результата. Разумеется, для получения результата этот алгоритм
все равно нужен, но он должен порождаться автоматически той системой, которая поддерживает
декларативно-ориентированный язык программирования. При логическом варианте такого подхо-
да (прежде всего это относится к языку Пролог, PROLOG) задача описывается совокупностью
фактов и правил в некотором формальном логическом языке, при функциональном варианте - в
виде функциональных соотношений между фактами (язык Лисп, LISP).
Процедурно-ориентированное программирование развивается и в другом направлении - так
64
называемого, параллельного программирования. В привычных алгоритмах и программах действия
совершаются последовательно одно за другим. Однако, логика решения множества задач вполне
допускает одновременное выполнение нескольких операций, что ведет к многократному увеличе-
нию эффективности. Реализация параллельных алгоритмов на ЭВМ стала возможной с появлени-
ем многопроцессорных компьютеров, в которых специалисты видят будущее вычислительной
техники.
Контрольные вопросы и задания
1. Какие требования предъявлялись к алгоритмам для компьютеров первых поколений?
2. Какой подход к созданию алгоритмов называется операциональным?
3. Охарактеризуйте операции, которые использовались при разработке программ при опе-
рациональном подходе.
4. Проделайте программу вычисления
x
из текста с помощью ручки, бумаги и калькуля-
тора.
5. В чем состоят недостатки операционального подхода к программированию?
6. Охарактеризуйте базовые структуры алгоритмов.
7. В чем состоит модульность при структурной разработке алгоритмов?
8. Что такое нисходящее проектирование программ?
§ 9. СТРУКТУРЫ ДАННЫХ
9.1. ДАННЫЕ И ИХ ОБРАБОТКА
Суть всех алгоритмов (и компьютерных программ) состоит в том, что они описывают пре-
образование некоторых начальных данных в конечные. Какие-то данные алгоритм (программа)
может использовать как промежуточные. Естественно, что представление и организация данных
имеет при разработке алгоритма первостепенное значение. Вопрос о том, как должны быть орга-
низованы данные, необходимо решать до того, как начинается разработка алгоритма (программы).
Ведь прежде, чем выполнить какие-либо операции, надо иметь объекты, к которым они будут
применяться, и четко представлять себе структуру объектов, которые будут получены.
Развитие вычислительной техники и программирования сопровождалось эволюцией пред-
ставлений о роли данных и их организации. Одним из свойств компьютеров является способность
хранить огромные объемы информации и обеспечивать легкий доступ к ней. Информация, подле-
жащая обработке, в некотором смысле представляет абстракцию фрагмента реального мира. Мы
говорим о данных как об абстрактном представлении реальности, поскольку некоторые свойства и
характеристики реальных объектов при этом игнорируются (как несущественные ддя данной зада-
чи). Например, каждый сотрудник в списке сотрудников некоторого учреждения представлен
множеством данных. Это множество может включать идентифицирующие данные (например, фа-
милию), данные, относящиеся к тому, что сотрудник делает или к тому, что делают для него. Од-
нако маловероятно, что будут включены такие сведения, как цвет глаз или волос, рост и вес.
Решая конкретную задачу, необходимо выбрать множество данных, представляющих ре-
альную ситуацию. Затем надлежит выбрать способ представления этой информации. Представле-
ние данных определяется исходя из средств и возможностей, допускаемых компьютером и его
программным обеспечением. Однако очень важную роль играют и свойства самих данных, опера-
ции, которые должны выполняться над ними. С развитием вычислительной техники и программи-
рования средства и возможности представления данных получили большое развитие и теперь по-
зволяют использовать как простейшие неструктурированные данные, так и данные более сложных
типов, полученные с помощью комбинации простейших данных. Такие данные называют
струк-
турированными,
поскольку они обладают некоторой организацией. Современные средства про-
граммирования позволяют оперировать с множествами, массивами, записями, файлами (очередя-
ми).
В более сложных случаях программист может задать динамические структуры данных, па-
мять для хранения которых выделяется прямо в процессе выполнения программы. К таким дан-
ным относят линейные списки (одно- и двунаправленные), стеки, деревья, графы.
65
В последние годы получило развитие, так называемое, объектно-ориентированное про-
граммирование, в котором в известной мере устранено противостояние . данных и программ. Объ-
ект - это некое образование, состоящее не только из данных, но и из процедур их обработки.
Остановимся подробнее на свойствах различных представлений данных или, как | еще го-
ворят, типах данных.
9.2
.
ПРОСТЫЕ (НЕСТРУКТУРИРОВАННЫЕ) ТИПЫ ДАННЫХ
В математике принято классифицировать величины в соответствии с их характеристиками.
Различают целые, вещественные, комплексные и логические величины, величины, представляю-
щие собой отдельные значения, множества значений или множества множеств. Аналогично этому
в информатике любая константа, переменная, выражение или функция относится к некоторому
типу. Фактически тип характеризует множество значений, которые может принимать константа,
переменная, выражение или функция. Широко используется правило, по которому тип явно ука-
зывается в описании константы, переменной или функции. К данным каждого типа применимы
определенные операции и их поведение подчиняется некоторым аксиомам.
Так, над целыми числами могут выполняться операции сложения (+), вычитания (-) и ум-
ножения (*). Существуют две различные операции, связанные с делением и не выводящие за гра-
ницы множества целых чисел: 1) определение целой части от деления одного числа на другое; 2)
определение остатка от деления одного числа на другое.
Целые числа, используемые компьютером, имеют те же свойства (подчиняются тем же ак-
сиомам), что и целые числа в арифметике. Все вычисления с ними выполняются абсолютно точно
(не приближенно). Имеется только одно отличие в свойствах компьютерных целых чисел от тех,
которыми оперирует абстрактная математика, а именно ограниченность диапазона: для каждой
компьютерной системы имеется самое большое допустимое в ней целое число
М
+∞
(и самое малое,
отрицательное
М
-∞
). Обычно выполняется соотношение
М
+∞
+ 1 = М
-∞
(М
-∞
- 1 = М
+∞
),
т. е. прибавив единицу к самому большому допустимому положительному числу, мы получим мо-
дуль самого малого допустимого отрицательного. Это свойство компьютерных чисел связано с
особенностями их кодирования в ячейках памяти компьютера.
Над действительными (или вещественными) числами могут быть выполнены операции
сложения (+), вычитания (-), умножения (*) и деления (/), так же, как и над математическими дей-
ствительными числами. Однако, все операции над действительными числами выполняются с точ-
ностью, не превосходящей некоторого фиксированного значения, вследствие того, что представ-
ления чисел в памяти компьютера имеют ограниченную длину (зависящую от конкретного ком-
пьютера и используемой системы программирования). Так, например, в машинной арифметике
может быть 1/3 = 0,33333333, тогда как математически точное десятичное представление дроби
1/3 - бесконечно длинное число.
Главным свойством литерных (символьных) данных является их упорядоченность, т.е.
свойство быть сравнимыми. Обычным признаком значения символьной или текстовой величины
являются кавычки, и справедливо 'а' <
'b', 'b' < 'с', 'с' < 'd'
и т.д. Каждый символ имеет определен-
ный числовой код (например, код символа латинской буквы "А" в большинстве кодировок 63) и
упорядочение происходит в соответствии с этими числовыми кодами. Как правило, имеются
функции, позволяющие получить по символу его код и символ по коду.
Для строчных величин единственной выполнимой операцией является конкатенация («сло-
жение») строк. Например,
'abcd'
+
'efg' = 'abcdefg'.
В конкретных системах обычно определены
функции, определяющие длину строк, вхождение в них тех или иных подстрок, вырезающие из
строк некоторые фрагменты.
К логическим данным, способным принимать значения «истина» («true») или «ложь»
(«false»), применимы основные операции логики высказываний: конъюнкция (логическое «и» -
«and»), дизъюнкция (логическое «или» - «or»), отрицание (логическое «не» - «not»). Иногда можно
использовать операции импликации («если»), эквиваленции («если и только если») и т.п. Эти ло-
гические операции определяются таблицей истинности, табл. 1.9.