Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования ( Три ключевых структуры алгоритма ).pdf

В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (серий). В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, команда ветвления состоит из условия и двух последовательностей команд. Команда ветвления, как и любая другая, может быть: • записана на естественном языке; • изображена в виде блок-схемы; • записана на алгоритмическом языке; • закодирована на языке программирования. Рассмотрим в качестве примера разветвляющийся алгоритм, изображенный в виде блок-схемы. Аргументами этого алгоритма являются две переменные А, В, а результатом — переменная X. Если условие А >= В истинно, то выполняется команда Х:=А*В, в противном случае выполняется команда Х:=А+В. В результате печатается то значение переменной X, которое она получает в результате выполнения одной из серий команд. Запишем теперь этот алгоритм на алгоритмическом языке и на языке программирования ^[10]Бейсик. 

1.3 Циклический алгоритм

Циклический алгоритм описывает вычислительный процесс, этапы которого повторяются многократно. Различают простые циклы, не содержащие внутри себя других циклов, и сложные(вложенные), содержащие несколько циклов. В зависимости от ограничения числа повторений и циклы, число повторений которых заранее неизвестно. ^[11]

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

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

Рисунок 9 – Блок-схема цикла с параметром

На рисунке приняты следующие сокращения:

ИП – имя ячейки памяти, в которую заносится значение параметра;

---

НЗ – начальное значение параметра;

КЗ – конечное значение параметра;

ШАГ – величина приращения параметра после каждого выполнения тела цикла.

Выполняется циклический алгоритм так: сначала проверяется условие, если условие верно (истина), то выполняется тело цикла (действия или группа операторов) и, далее, изменяются значения параметра цикла и снова проверятся условие и т.д. На каком-то шаге условие не выполняется (ложь) и тогда происходит выход из цикла и продолжается выполнение программы.^[12]

Тело цикла представляет собой линейный вычислительный процесс и выполняется столько раз, сколько разных значений примет параметр в заданных пределах от НЗ до КЗ. Цикл с параметром относится к циклу с явно выраженным числом повторений (число повторений известно заранее). Для таких циклов характерным является то, что задаются:

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

цикл с предусловием и цикл с постусловием относятся к так называемым итерационным циклам. В таких циклических вычислительных процессах число повторений тела цикла заранее не известно. Выход из цикла осуществляется не после того, как цикл повторится заданное число раз, а при выполнении определенного условия, связанного с проверкой значения монотонно изменяющейся в теле цикла величины. Блок-схема цикла с предусловием представлена на рис. 10, а блок-схема цикла с постусловием – на рис. 11.

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

В цикле с постусловием тело цикла выполняется не менее одного раза. При этом действия, предусмотренные в теле цикла, выполняются до тех пор, пока не выполнится заданное условие.^[13]

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

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

Рассмотренные блок-схемы циклов позволяют описать простые циклические вычислительные процессы. При решении сложных задач может возникнуть необходимость внутри одного цикла организовать дополнительно один или несколько других циклов. Такие циклы называются вложенными. При этом цикл, внутри которого создается другой цикл, называется внешним, а цикл, создаваемый внутри другого –внутренним. Правила организации как внешнего, так и внутреннего циклов те же, что и для простых циклов. Параметры внешнего и внутреннего циклов должны быть разными.^[14]

---

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

Fortran (Фортран). Это первый компилируемый язык, созданный Джимом Бэкусом в 50-е годы. Программисты, разрабатывавшие программы исключительно на ассем­блере, выражали серьезное сомнение в возможности появления высокопроизво­дительного языка высокого уровня, поэтому основным критерием при разработке компиляторов Фортрана являлась эффективность исполняемого кода. Хотя в Фортране впервые был реализован ряд важнейших понятий программирования, удобство создания программ было принесено в жертву возможности получения эффективного машинного кода. Однако для этого языка было создано огромное количество библиотек, начиная от статистических комплексов и заканчивая пакетами управления спутниками, поэтому Фортран продолжает активно использоваться во многих организациях.^[15]

А1gо1 (Алгол). Компилируемый язык, созданный в 1960 году. Он был призван заме­нить Фортран, но из-за более сложной структуры не получил широкого распростра­нения. В 1968 году была создана версия Алгол 68, по своим возможностям и сегодня опережающая многие языки программирования, однако из-за отсутствия доста­точно эффективных компьютеров для нее не удалось своевременно создать хорошие компиляторы. Язык Алгол сыграл большую роль в теории, но для практического программирования сейчас почти не используется.

Cobol (Кобол). Это компилируемый язык для применения в экономической области и решения бизнес-задач, разработанный в начале 60-х годов. Он отличается большой "многословностью" – его операторы иногда выглядят как обычные английские фразы. В Коболе были реализованы очень мощные средства работы с большими объемами данных, хранящимися на различных внешних носителях. На этом языке создано очень много приложений, которые активно эксплуатируются и сегодня. Достаточно сказать, что наибольшую зарплату в США получают программисты на Коболе.

Pascal (Паскаль). Язык Паскаль, созданный в конце 70-х годов основоположником множества идей современного программирования Никлаусом Виртом и названный в честь ученого Блеза Паскаля, во многом напоминает Алгол, но в нем ужесточен ряд требований к структуре программы и имеются возможности, позволяющие успешно применять его при создании крупных программных проектов. Изначально Паскаль был задуман как язык программирования для студентов. Он и сейчас является основным языком программирования, используемым в качестве учебного, во многих высших учебных заведениях. На базе языка Паскаль созданы несколько более мощных языков (Модула, Ада, Дельфи).^[16]

---

BASIC (Бейсик). Для этого языка имеются и компиляторы, и интерпретаторы, а по популярности он занимает первое место в мире. Бейсик был создан в 1964 г. Томасом Куртом и Джоном Кемени как язык для начинающих программистов, облегчающий написание простых программ. В настоящее время разработано несколько различных версий языка Бейсик, таких как GWBASIC, QBASIC, Pro-BASIC, Turbo-BASIC, Visual-BASIC и др.

С (Си). Данный язык был создан в лаборатории Ве11 и первоначально не рассматри­вался как массовый. Он планировался для замены ассемблера, чтобы иметь возмож­ность создавать столь же эффективные и компактные программы, и в то же время не зависеть от конкретного типа процессора.

Си во многом похож на Паскаль и имеет дополнительные средства для прямой работы с памятью (указатели). На этом языке в 70-е годы написано множество при­кладных и системных программ и ряд известных операционных систем (например, Unix). В настоящее время Си широко используется при создании системного программного обеспечения.

PL/1 (ПЛ/1). В середине 60-х годов компания 1ВМ решила взять все лучшее из языков Фортран, Кобол и Алгол и воплотить в одном языке программирования. В результате в 1964 году на свет появился новый компилируемый язык программирования, который получил название Programming Language One. В этом языке было реализовано множество уникальных решений, полезность которых удается оценить только спустя 33 года, в эпоху крупных про­граммных систем. По своим возможностям ПЛ/1 значительно мощнее многих других языков (Си, Паскаля). Например, в ПЛ/1 присутствует уникальная возможность указания точности вычислений – ее нет даже у Си++ и Явы. В настоящее время язык ПЛ/1 почти не используется.

Ada (Ада). Назван по имени леди Огасты Ады Лавлейс, дочери английского поэта Байрона и его отдаленной родственницы Анабеллы Милбэнк. В 1979 году сотни экспертов Министерства обороны США отобрали из 17 вариантов именно этот язык, разработанный небольшой группой под руководством Жана Ихбиа. Он удовле­творил на то время все требования Пентагона, а к сегодняшнему дню в его развитие вложены десятки миллиардов долларов. Структура самого языка похожа на Паскаль. В нем имеются средства строгого разграничения доступа к различным уровням спецификаций, доведена до предела мощность управляющих конструкций.^[17]

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

---

– выделении классов объектов;

– установлении характерных свойств объектов и методов их обработки;

– создании иерархии классов, наследовании свойств объектов и методов их обработки.

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

Из языков объектного программирования, популярных среди профессионалов, следует назвать прежде всего:

С++ (Си++). Си++ - это объектно-ориентированное расширение языка Си, создан­ное Бьярном Страуструпом в 1980 году. Множество новых мощных возможностей, позволивших резко повысить производительность работы программистов, наложилось на унаследованную от языка Си определенную низкоуровневость, в результате чего создание сложных и надежных программ потребовало от разработчиков высокого уровня профессиональной подготовки;^[18]

Java (Джава). Этот язык был создан компанией Sun в начале 90-х годов на основе Си++. Он призван упростить разработку приложений на основе Си++ путем исключения из него всех низкоуровневых возможностей. Но главная особенность этого языка – компиляция не в машинный код, а в платформно-независимый байт-код (каждая команда занимает один байт). Этот байт-код может выполняться с помощью интерпретатора – виртуальной Java-машины, версии которой созданы сегодня для любых платформ. Благодаря наличию мно­жества Java-машин программы на Джава можно переносить не только на уровне исход­ных текстов, но и на уровне двоичного байт-кода, поэтому по популярности язык Джава сегодня занимает второе место в мире после Бейсика. Язык Джава чрезвычайно эффективен для создания интерактивных Web-страниц;^[19]

Smalltalk (Смолток). Работа над этим языком началась в 1970 году в исследова­тельской лаборатории корпорации XEROX, а закончились спустя 10 лет, вопло­тившись в окончательном варианте интерпретатора SMALLTALK-80. Данный язык оригинален тем, что его синтаксис очень компактен и базируется исключительно на понятии объекта. В этом языке не существует операторов или данных. Все, что входит в Смолток, является объектами, а сами объекты общаются друг с другом исключи­тельно с помощью сообщений (например, появление выражения I+1 вызывает посыл­ку объекту I сообщения "+", то есть "прибавить", с параметром 1, который считается не числом-константой, а тоже объектом). Больше никаких управляющих структур, за исключением "оператора" ветвления (на самом деле функции, принадлежащей стандартному объекту), в языке нет, хотя их можно очень просто смоделировать. Сегодня версия VisualAge for Smalltalk активно развивается компанией IВМ;

---