Представление алгоритма и псевдокод

Алгоритм является абстракцией и поэтому один и тот же алгоритм можно представить многими способами. Если с алго­ритмом работает человек, то это может быть традиционный язык (русский, английский), язык картинок и пиктограмм, а также мате­матические формулы.

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

Каждый примитив состоит из двух частей: синтаксической и семантической. Синтаксис относится к символьному представле­нию примитива, а семантика - к смысловому значению примитива.

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

Псевдокод - это система обозначений, предназначенная для не­формального представления идей в процессе разработки алгоритмов.

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

Альтернатива выражается на псевдокоде следующей структурой: if (условие) then (действие) else (действие)

Сокращенный синтаксис этого конструкта когда не предусмот­рено действие для варианта else выглядит так:

if (условие) then (действие)

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

Эта инструкция предписывает проверить условие и, если оно верно, выполнить действие, а затем вновь проверить условие. Если при очередной проверке условие оказывается неверным, следует перейти к инструкции, следующей за данной структурой.

while (условие) do (действие)

Цикл-do на псевдокоде имеет следующий вид: repeat (действие) until (условие)

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

assign имя the value выражение

здесь параметр имя - это описательное имя, а параметр выражение описывает значение, связываемое с этим именем. Например: assign Итог the value Цена + Налог

При ее выполнении результат суммирования значений пере­менных Цена и Налог будет связан с именем Итог.

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

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

здесь имя — это конкретное название, присвоенное данному блоку. Ниже следуют инструкции, определяющие выполняемые в этом блоке действия.

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

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

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

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

АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА

Этот алгоритм решает задачу поиска в списке некоторо­го заданного значения. Он позволяет установить, есть ли заданное значение в списке. Если это значение в списке присутствует, поиск будет считаться успешным, в противном случае - неудачным.

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

procedure Поиск (<список>, <искомое значение>) if (список пуст)

then (объявить поиск неудачным)

else

(выбрать как <проверяемое значение> первый

элемент списка)

while (<искомое значение> > <проверяемое значение> и есть непроверенные элементы) do (выбрать следующий элемент списка как <проверяемое значение>) if (<искомое значение> = <проверяемое значение>)

then (объявить поиск успешным) else (объявить поиск неудачным)

По окончании выполнения структуры while искомое значение либо будет найдено, либо выяснится, что его нет в списке. В любом случае успешность поиска можно установить, сравнивая искомое значение с проверяемым. Если они эквивалентны, поиск объявля­ется успешным. Для полной уверенности в правильности програм­мы она помещается в предложение else инструкции if.

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

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

АЛГОРИТМ ДВОИЧНОГО ПОИСКА

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

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

procedure Search (<список>, <искомое_значение>) if (<список> пуст)

then (Объявить поиск неудачным)

else

(Выбрать "средний" элемент в <список> в качестве

<проверяемый_элемент>)

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

Case 1: <искомое_значение> = <проверяемый_элемент> (Объявить поиск успешным)

Case 2: <искомое_значение> < <проверяемый_элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, предшествующей элементу <проверяемый элемент>, элемент <искомое_значение>, и if (тот поиск успешен

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным) Case 3: <искомое_значение> > <проверяемый__элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, следующей за элементом <проверяемый_элемент>, элемент <искомое_значение> и if (тот поиск успешен)

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным)

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

При выполнении этой процедуры и при достижении инструкции <Применить процедуру Search, чтобы...>, будет применяться этот же метод поиска к меньшему списку, который является частью исходного списка. Если этот вторичный поиск завершится успешно, то осуществляется возврат в исходную процедуру, чтобы объявить выполняемый в ней поиск успешным. Если же вторичный поиск окончится неудачей, то объявляется неудачным и исходный поиск.

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

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