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

Интуитивное понятие алгоритма.

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

а) подготовиться к уроку по математике;

б) приготовить раствор для проявления фотопленки;

в) избавиться от лишнего веса.

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

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

Для разъяснения интуитивного понятия алгоритма рассмотрим несколько примеров.

В качестве первого примера рассмотрим один из самых древних и самых известных математических алгоритмов - алгоритм нахождения наибольшего общего делителя двух натуральных чисел. Этот алгоритм еще в III веке до нашей эры изложил (в геометрической форме) греческий ученый Евклид в теоретическом трактате по математике "Начала". Поэтому он носит название алгоритма Евклида. Алгоритм Евклида обсуждается практически в каждой книге по программированию.

Пример 1.1. Вычисление наибольшего общего делителя двух натуральных чисел m и n.

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

1. Поместить в участок памяти с именем x число m; перейти к выполнению пункта 2.

2. Поместить в участок памяти с именем y число n; перейти к выполнению пункта 3.

З. Если выполняется условие , то перейти к выполнению пункта 5, иначе перейти к выполнению пункта 4.

4. Поместить в участок памяти с именем НОД значение из блока памяти x; перейти к выполнению пункта 8.

5. Если выполняется условие x > y, то перейти к выполнению пункта 6, иначе перейти к выполнению пункта 7;

6. Поместить в участок памяти с именем x значение выражения x - y; перейти к выполнению пункта 3.

7. Поместить в участок памяти с именем y значение выражения y - x; перейти к выполнению пункта 3.

8. Закончить работу.

Внимательное рассмотрение алгоритма Евклида показывает, что запись алгоритма распадается на отдельные команды. Каждая команда снабжена номером и представляет собой указание исполнителю выполнить некоторое законченное действие. Исполнение алгоритма начинается с команды, имеющей номер 1. Далее команды выполняются в соответствии с указаниями, сопровождающими каждую команду алгоритма.

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

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

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

Дата добавления: 2014-01-06