Программные средства информатики

Тема 1. Алгоритмы.

1.1. Основные понятия.

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

Алгоритм – это основа создания и использования программных средств.

(07.11.2012 г.)

Во множестве алгоритмов могут быть такие, которые используются как часть других алгоритмов. В связи с этим каждый алгоритм снабжается именем. Это позволяет в одних алгоритмах указать ссылки на другие алгоритмы. Алгоритм состоит из шагов (этапов), каждый шаг – это именованное описание последовательности действий (операций). Имя шага состоит из имени алгоритма и порядкового номера шага.

Например:

Если имя А, то имена шагов – А1, А2….. и т.д.

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

= – равенство

ß – замещение

ßà – взаимный обмен

Знак “ = “ используется для записи логических выражений.

Знак “ ß” означает очень важную операцию замещение, которое представляет собой обобщение двух операций: присваивание и подстановка. Конкретная реализация этой операции зависит от выбранного программного средства. Запись m ß n означает, что значение m должно быть заменено (замещено) текущим значением n. Запись: переменная ß формула означает, что в соответствии с данной формулой должны быть произведены вычисления при текущих значениях, входящих в неё переменных, после чего значение переменной, стоящей слева от знака замещения, следует заменить полученным значением.

Например:

В результате выполнения действия n ß n+1 в переменной n будет помещено значение на 1 больше, чем предыдущее значение. Т.е. значение n увеличится на единицу.

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

Например:

Если переменные m и n надо заместить значением r можно записать mßnßr

Знак “ßà” означает операцию взаимного обмена значениями двух переменных и записывается: m ßà n.

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

1.2. Словесно-формульное описание алгоритма.

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

Например:

Алгоритм Евклида

Имя: Алгоритм Е [Алгоритм Евклида]

Даны два положительных целых числа m и n. Требуется найти их наибольший общий делитель, т.е. наибольшее целое число, которое нацело делит как m, так и n.

Е 1 [Нахождение остатка] r ß остаток от m/n (r>=0; r<n; 0<=r<n)

Е 2 [Это ноль?] Если r=0, алгоритм заканчивается; в n – искомое число.

Е 3 [Замещение] m ß n; n ß r; возвращаемся к Е 1.

1.3. Структурное описание алгоритма.

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

Основные вершины в блок-схеме:

– начало, окончание. У вершины начала нет входящих дуг, и есть лишь одна исходящая, направленная к вершине, с которой начинается алгоритм. У вершины окончания нет исходящих дуг, и может быть несколько входящих.

– действие. Они соответствуют шагам, в которых выполняются действия. Каждая такая вершина может иметь несколько входящих дуг и только одну исходящую.

– условие. Они соответствуют шагам, в которых проверяются условия. Каждая

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

– ввод, вывод. Они соответствуют шагам, в которых выполняются ввод или вывод

данных. Каждая вершина может иметь несколько входящих дуг и только одну исходящую.

– много. Если у вершины несколько входящих дуг, то для их объединения

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

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

Например:

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

Например:

Для алгоритма Евклида