Раздел 2. Программные средства информатики.

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

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

Алгоритм – это конечная последовательность правил (шагов, этапов), позволяющая решать любую задачу из класса однотипных при условии, что исходные данные для решения могут изменяться в заданных пределах. Алгоритм – основа создания и использования программных средств. Это форма представления процедурных знаний, т.е. знаний, представленных в виде последовательности процедур, действий, операция и т.п. Во множестве алгоритмов могут быть такие, которые используются как часть других алгоритмов. В связи с этим каждый алгоритм снабжается именем. Это позволяет в одних алгоритмах указывать ссылки на другие алгоритмы. Алгоритм состоит из шагов. Каждый шаг – это именованное описание последовательности действий (операций). Имя шага состоит из имени алгоритма и порядкового номера этого шага. Например, если имя алгоритма А, то имена его шагов А1, А2 и т.д. При описании действий используются специальные знаки, например «=», «←» (замещение), «» (взаимный обмен). Знак равенства используется для записи логических выражений, знак «←» означает очень важную операцию замещения, которая представляет собой обобщение двух операций: присваивание и подстановка. Конкретная реализация этой операции зависит от выбранного программного средства. «m←n» означает, что значение переменной n должно быть замещено текущим значением m. «переменная←формула» означает, что в соответствии с данной формулой должны быть произведены вычисления при текущих значениях входящих в нее переменных, после чего значение переменной, указанной слева от знака замещения надо заместить полученным значением. Например, n←n+1 означает увеличение значения n на единицу. Если несколько переменных надо заместить одним и тем же значением можно использовать сокращенную запись. Например, если переменные m и n надо заместить значением переменной r, то можно записать «m←n←r». Следует иметь в виду, что между знаками равенства и замещения есть существенные различия: «=» означает сравнении и используется в условиях, которые необходимо проверить, а «←» означает действие, которое следует произвести. В настоящее время используются различные способы описания алгоритмов, основными из которых являются:

• словесно-формульный (пошаговый)

• структурный (в виде блок-схемы)

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

При этом способе алгоритм записывается в виде текста по шагам, в определенной последовательности действий. Сначала указывается имя алгоритма, вслед за которым записываются ограничения, накладываемые на исходные данные, и что является результатом выполнения этого алгоритма. Каждый шаг начинается с его имени, после которого в квадратных скобках записывается фраза, как можно короче резюмирующая суть этого шага, затем следует подробное описание тех действий, которые должны быть выполнены. При этом порядок действий указывается слева направо. Далее, если необходимо записать комментарии к шагу, комментарии заключаются в круглые скобки. Комментарии – это дополнительная информация о шаге, они указывают на какие-либо характеристики переменных, особенности действий и т.п. Они приводятся лишь для удобства чтения, чтобы облегчить понимание сути шага. Рассмотрим пример алгоритма нахождения наибольшего общего делителя двух целых положительных чисел Эвклида. Алгоритм Е [алгоритм Эвклида]:

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

Е1 [нахождение остатка] r←остаток от (r≥0, r<n)

Е2 [это нуль?] если r<0, алгоритм заканчивается в n-искомое число

Е3 [замещение] m←n, n←r, возвратиться к шагу E1