Некоторые формы описания алгоритмов

Некоторые формы описания алгоритмов.

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

1. Словесная запись алгоритмов

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

1. Графические схемы алгоритмов

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

• Ввод-вывод— преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод):

• Процесс—выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных:

• Решение—выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий:

• Пуск— начало выполнения программы:

• Останов— конец выполнения программы:

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

1. Псевдокод

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

Пример записи на псевдокоде алгоритма Евклида для нахождения наибольшего общего делителя двух натуральных чисел:

Алгоритм ЕВКЛИД;

начало

пока первое число не равно второму числу

начало

если первое число больше второго числа

то заменить первое число на разность первого и

второго чисел

иначе заменить второе число на разность второго

и первого чисел

все

взять первое число в качестве ответа;

конец

конец

Структуры алгоритмов

1. Простые команды

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

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

:=

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

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

ввод (x, y ,z)

означает получение исполнителем от внешнего источника трех значений, которые должны быть присвоены переменным x, y и z.

Аналогичная команда

вывод (m, n)

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

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

Команда

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

   1. Команда следования

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

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

начало ; ; … ; конец,

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

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

команда1 команда 2 … команда N

1. Команда ветвления

Простейшая форма ветвления — это альтернатива, где есть два возможных пути, и выбор зависит от того, верно или неверно некоторое условие:

если

то

иначе

все

или при использовании графических схем:

да условие нет

команда 1 команда 2

Это так называемая полная условная конструкция. Может использоваться команда ветвления и в сокращенной форме —неполная условная конструкция (коррекция), когда в случае невыполнения указанного в команде условия никакое действие не выполняется:

если

то

все

или на языке графических схем:

да условие нет

команда

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

выбрать

: ;

: ;

…

:

иначе

;

Этот порядок предусматривает, что выполняется команда i, если соответствующее условие i—верно; или, если ни одно из условий i(i= 1, 2, … ,N) неверно, выполняется команда0(при наличии ветви иначе). При использовании многозначного ветвления следует учитывать тот факт, что либо никакие два из условий не являются верными одновременно, либо несколько условий являются верными одновременно.

1. Команда повторения (цикла)

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

1. Бесконечный цикл

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

повторять

;

команда

Бесконечный цикл играет фундаментальную роль в области процессов реального времени, операционных систем и т.д.

1. Команда повторения с предусловием (цикл–пока )

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

пока повторять

;

условие ложь

истина

команда

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

Главная проблема, которая возникает в связи с использованием цикла – пока, это проблема его окончания: как можно гарантировать, что цикл завершится после некоторого числа итераций, для некоторого класса данных? Эта проблема не имеет решения в общем случае; на практике, однако, часто возможно найти свойства условия и команды, обеспечивающие окончание циклического процесса.

1. Команда цикла с постусловием (цикл – до)

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

повторять

до;

команда

истина

условие

ложь

1. Цикл с параметром

Значительный интерес с практической точки зрения представляет базовая конструкция — цикл с параметром, которая может использоваться в различных модификациях:

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

;

Для х принадлежащего М покаповторять

;

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

;

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

;

1. КОМПОЗИЦИИ БАЗОВЫХ СТРУКТУР

В соответствии с так называемой «структурной теоремой», изложенной в классической работе итальянских математиков К.Бома и Г.Джакопини (1965 г.),всякая программа(алгоритм) может быть построена с использованием только трех управляющих конструкций(структур):следование, развилка и цикл. Каждая из этих конструкций имеет один вход и один выход. В силу этого развилка или цикл могут рассматриваться как обобщенный функциональный блок, т.е. «черный ящик» с одним входом и одним выходом. Таким образом, в конструкциях цикл и развилка функциональные блоки сами могут быть конструкциями такого же типа, поэтому возможны вложенные конструкции. При этом какова бы ни была глубина вложенности, важно, что любая конструкция в конечном итоге имеет один вход и один выход.

Также можно утверждать, что конструкций следование и цикл-пока принципиально достаточны, чтобы описать действие любой программы (алгоритма). Не пытаясь доказать этот общий результат, посмотрим, например, как можно обойтись без альтернативы: если … то … иначе:

если

то

иначе

все;

Пусть лог1 и лог2 – логические переменные. Тогда конструкция

лог1 : = ;

лог2 : = ~ ;

покалог1повторять

начало

;

лог1 : = ложь

конец;

покалог2повторять

начало

;

лог2 : = ложь

конец;

эквивалентна предыдущей конструкции.