1.4.2. Примеры алгоритмов. Способы, используемые при записи алгоритмов: ре­курсия, итерация, разбор случаев, ие­рархическое построе­ние

Приведем некоторые примеры алгоритмов, сформулированных весь­ма неформально (на "разговорном языке").

(А) Запись алгоритма вычисления значения дроби (a+b)/(a-b).

Сначала вычисляем (используя алгоритмы сложения и вычи­та­ния) значения выражений a+b и a-b (все равно, последова­тельно или парал­лельно), а потом образуем частное от деле­ния получен­ных результатов (используя алгоритм деления).

Пример выполнения алгоритма для пары чисел 2/3 и 5/7.

Исходные значения: a равно 2/3, b равно 5/7.

Выражение a+b равно 29/21. (Процесс вычисления суммы 2/3 и 5/7 здесь для краткости не показан).

Выражение a-b равно -1/21. (Процесс вычисления разности 2/3 и 5/7 здесь для краткости не показан).

Результат - частное (a+b)/(a-b) равно -29. (Процесс деления 29/21 на ‑1/21 здесь для краткости не показан).

(Б) Запись алгоритма разложения натурального числа на про­стые множите­ли.

Нужно последовательно пытаться делить нацело без остатка за­данное число на на­тураль­ные числа 2,3,4,5,6,7,... до тех пор, пока не останется 1. Последовательность получающихся в конечном счете делите­лей даст требуемое разложение на про­стые множи­те­ли.

Пример выполнения алгоритма для числа 105.

Исходное разложение (105).

(105) на 2 без остатка не делится.

(105) на 3 делится. Частное - 35.

(35·3) на 4 без остатка не делится.

(35·3) на 5 делится. Частное - (7·3).

(7·3·5) на 6 без остатка не делится.

(7·3·5) на 7 делится. Частное - (1·3·5).

Выполнение завер­шено. Результат - разложение (3·5·7).

(В) Запись алгоритма вставки карточки в упорядоченную карто­теку.

В случае пустой картотеки вставка карточки тривиальна.

В про­тивном случае раскроем картотеку в произвольном месте и срав­ним открыв­шуюся карточку с вставляемой по признаку, ко­торый упорядочивает картотеку. После сравнения становится яс­ным, в какую из частей картотеки нужно вставить карточку: в пе­реднюю стопку или заднюю стопку карточек.

Для вставки карточки в необходимую стопку будем действовать тем же самым способом.

Процесс за­канчивается, когда карточку нужно вставлять в пустое множе­ство карт.

В примере (А) мы имеем наиболее простой случай: количество эле­мен­тарных тактов обработки постоянно и не зависит от чисел a и b. Иначе обстоит дело в других примерах: в случае (Б) это количество зависит от ве­личины разла­гаемого на множители числа, в случае (В) - от размера карто­теки. Хотя описание алгоритма конечно и по­стоянно, коли­чество фак­тиче­ски выполняе­мых тактов - величина пе­ременная: это ока­зывается воз­мож­ным благодаря ис­пользованию приема, сводящего об­щую задачу к "более простой" задаче того же класса.

Этот прием называ­ют рекурсией. В примере (В) наличие ре­курсии очевидно из самого словесного описания алгоритма. В при­мере (Б) мы имеем специальный случай рекурсии - повторительную рекурсию (итерацию). При сло­весном описании ее часто записывают в форме: "Пока выполнено опре­деленное условие, по­вторяй...".

Наряду с рекурсией и повторением в алгоритмах встречается разбор слу­чаев. Без разбора возможных случаев, в частности, было бы невоз­можно окон­чание алгоритмов (Б) и (В).

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

1) из исходного алгоритма выделяются некоторые его части - также яв­ляющиеся алгоритмами. Они именуются вспомогательными алгорит­мами по отношению к исходному алгоритму;

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

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

Так, в примере алгоритм (А) использует как вспомогательные алго­рит­мы умножения, суммы, деления чисел, хотя их описание и не приво­дится. Предпо­лагается, что они заданы или будут заданы в дру­гом месте.