Представления алгоритмов

Рассмотрим способы представления алгоритмов на примере алгоритма Евклида (алгоритма нахождения наибольшего общего делителя двух натуральных чисел).

1. Словесное описание.

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

Обозначим наибольший общий делитель двух чисел и через , а остаток от деления на – через .

Данный алгоритм основан на том, что:

• , если ;

• , если .

Например: .

2. Описание в виде таблицы.

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

3. Последовательность шагов.

   1. Найти среди и наибольшее число. Обозначим его .

   2. Разделить на с остатком. Если остаток нулевой, то п.4, иначе п.3.

   3. =остаток от деления на ; := и; п.2.

   4. НОД= .

4. На языке программирования.

Записать алгоритм в виде последовательности операторов некоторого языка программирования.

Запишем алгоритм Евклида на языке программирования

1. Паскаль

Program NOD;

var a,b,buf:integer;

begin

readln(a,b);

if a<b then

begin

buf:=a;

a:=b;

b:=buf;

end;

repeat

buf:=a mod b;

a:=b;

b:=buf;

until b=0;

writeln('NOD=',a);

readln;

end.

2. C++

#include <iostream>

#include <conio.h>

#include <math.h>

using namespace std;

int main()

{ float a,b,buf;

cin >> a;

cin >> b;

if (a<b)

{buf=a;

a=b;

b=buf;}

do { buf = fmod(a,b);

a=b;

b=buf;}

while (b!=0);

cout << "NOD = " << a << endl;

_getch();

return 0;

}

5. Графическое описание (например, в виде блок-схем).

Достоинством именно этого метода является наглядность отображения управления.

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

а )

б )

в )

Рис. 1.1 Виды вершин блок-схем

Из этих трех типов вершин можно составлять различные алгоритмические конструкции.

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

Изобразим с помощью блок-схем эти типы алгоритмических конструкций.

Используя эти типы конструкций, можно составлять блок-схемы любых алгоритмов. Изобразим блок-схему алгоритма Евклида¹.

Блок-схема алгоритма Евклида

Рассмотрим еще один алгоритм, известный из школьного курса математики.

Пример 1.2. Пусть необходимо разработать алгоритм решения квадратного уравнения , т.е. необходимо вычислить корни квадратного уравнения, заданного коэффициентами ( ).

Описание процесса решения задачи (или алгоритм решения задачи) можно осуществить несколькими способами.

Опишем данный алгоритм в виде последовательности действий.

1. Прочитать коэффициенты .

2. Вычислить дискриминант: .

3. Если , вычислить , и написать эти числа; иначе, если , вычислить и написать это число; иначе написать «действительных корней нет».

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

Рис. Блок-схема алгоритма нахождения действительных корней

квадратного уравнения