Запись алгоритма

 Запись алгоритма

Эта современная запись алгоритма нахождения НОД – весьма уп- рощенная. Запись, данная первоначально Евклидом, заполняет целую страницу текста, причем последовательность элементарных действий там значительно сложней.

Представление алгоритма в форме блок-схемы реализуется в ви- де набора геометрических элементов (блоков), соединенных стрелка- ми. Каждый блок – это «шаг» алгоритма, его отдельное действие. На- правление стрелок между блоками задает последовательность дейст- вий. В табл. 4 представлены основные стандартные элементы блок- схем.

Табл. 4

Элементы блок-схемы различаются по своему внешнему виду и на- значению. Так, элементы, содержащие инструкции по каким-либо преоб- разованиям величин, обозначаются прямоугольниками, а элементы, со- держащие проверку условий, – ромбами. Операции ввода-вывода дан- ных обозначаются параллелограммами. Начало и конец алгоритма обо- значаются прямоугольниками с двумя скругленными противоположными сторонами, внутри которых пишут: «начало» или «конец» соответственно. Из прямоугольника выходит единственная стрелка, входить в него может несколько стрелок. Из обеих острых вершин ромба выходят стрелки: одна из них помечается словом «да», другая – словом «нет», они задают дальнейшее направление вычислений в случае, соответст- венно, выполнения или невыполнения записанного внутри ромба усло-

вия.

Назначение и правила использования всех типов блоков приведены в табл. 4 в графах Название элемента и Пояснение. С использованием приведенных в табл. 4 стандартных элементов вышеуказанный алго- ритм нахождения НОД двух положительных целых чисел m и n примет

вид блок-схемы на рис. 6. Внутри блоков в ней знаком := обозначена операция присваивания переменной величине, указанной слева от зна- ка, ее значения, вычисляемого по формуле, стоящей справа от знака.

Рис. 6. Блок-схема алгоритма нахождения НОД

Представление алгоритма в форме псевдокода основано на описании этапов решения задачи с помощью ограниченного набора стандартных синтаксических конструкций. В псевдокоде, в частности, могут использо- ваться отдельные инструкции формальных алгоритмических языков про- граммирования. Например, возведение X в степень A обозначается как X**A, извлечение квадратного корня из X обозначается как Sqrt (X).

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

В качестве ключевых могут использоваться также соответствующие английские слова-аналоги: else вместо иначе, then вместо то.

В самом общем виде запись алгоритма в форме псевдокода выгля- дит следующим образом:

алг название алгоритма (аргументы – входные параметры и пара- метры – результаты работы алгоритма)

дано | условия применимости алгоритма

надо | цель выполнения алгоритма

нач описание промежуточных (внутренних) величин алгоритма команда 1;

команда 2;

…

команда N

кон

Здесь часть записи от слова алг до слова нач называется заголов- ком алгоритма, а часть, заключенная между словами нач и кон, – его телом. Внутри тела также могут встречаться слова нач и кон, группа ко- манд между ними образует свой отдельный блок команд. Команды от- деляются друг от друга символом «;».

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

В конце любой строки в текст псевдокода после знака «|» можно вставлять комментарий, облегчающий понимание алгоритма.

Разделы «дано» и «надо» в записи алгоритма не являются обяза- тельными.

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

Команда ввода: ключевое слово ввод, за которым указываются имена переменных, для которых вводятся значения. Например, команда ввод a,b,c означает ввод значений соответственно для переменных a,b,c.

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

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

менная" := "выражение", где знак ":=" означает команду замены преж- него значения переменной, стоящей в левой части, на вычисленное зна- чение выражения, стоящего в правой части.

Табл. 5

Например, команда x := y + z означает присваивание переменной x значения суммы величин y и z, а команда k := k+1 означает увеличение текущего значения переменной k на единицу.

Команда перехода: ключевые слова идти к, после которых указы- вается номер той строки, команда которой должна выполняться сле- дующей. Таким образом, команда перехода изменяет естественную по- следовательность выполнения команд по возрастанию номеров строк. Например, записанная в 5-й строке команда идти к 10 означает, что да- лее должна выполняться команда, записанная в 10-й строке, а не ко- манда, записанная в следующей 6-й строке.

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

С использованием псевдокода вышеуказанный алгоритм нахожде- ния НОД двух положительных целых чисел m и n примет следующий вид:

1.                алг Наибольший Общий Делитель (арг цел m, n, рез цел nod)

2.                        дано | положительные целые числа m, n

3.                        надо | nod – наибольший общий делитель чисел m, n

4.               нач

5.                        ввод m, n;

6.                        если m = n то идти к 9 все;

7.                        если m > n то m := m – n иначе n := n – m все;

8.                        идти к 6;

9.                        nod := m;

10.                   вывод “Значение НОД равно”, nod

11.          кон

Эта форма представления облегчает запись алгоритма на стадии его проектирования и дает возможность в дальнейшем легко перевести алгоритм в более широкий набор команд формального языка програм- мирования.

Скачано с www.znanio.ru