Основные свойства алгоритма

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

1) Конечность – любой алгоритм должен заканчиваться после выполнения конечного (т.е. не бесконечного) числа шагов.

Если алгоритм содержит цикл, т.е. повторяющуюся группу команд, то в алгоритме должно присутствовать некое условие, при выполнении которого следует прерывание цикла.

Например, еще древние греки знали метод приближенного извлечения квадратного корня из произвольного числа а > 0. Пусть х⁽⁰⁾ – некоторое начальное приближение к . Для вычисления каждого следующего приближения построим рекуррентную формулу:

, k = 0, 1, … (2.1)

называемую алгоритмом Герона.

Вычислим с его помощью , взяв х⁽⁰⁾ = 1.5. Последовательно получим х⁽¹⁾ = 1.4166667; х⁽²⁾ = 1.4142157; х⁽³⁾ = 1.4142136; х⁽⁴⁾ = 1.4142136. Теоретически эти вычисления можно продолжать бесконечно, получая все более точный результат, поэтому формула (2.1), строго говоря, алгоритмом не является.

Для того, чтобы ее с полным правом можно было назвать алгоритмом, надо указать условие окончания вычислений. Например, можно таким условием считать совпадение определенного количества N цифр в двух последовательных значениях х^(k) и х^(k+1). Доказано, что в этом случае при использовании формулы (2.1) у всех последующих приближений первые N цифр будут такими же, как у х^(k+1). В приведенном примере у х⁽³⁾ и х⁽⁴⁾ совпали первые N = 8 цифр. Следовательно, ответ получен с точностью 10^–7, и если она нас устроит, то вычисления можно заканчивать.

2) Определенность – каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола.

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

Например, не является алгоритмом такая инструкция: слегка подогрейте в маленькой кастрюле немного коньяку, добавьте специи по вкусу. Здесь слова “слегка”, “немного” и т.д. носят неопределенный характер, который каждый исполнитель может трактовать по-своему.

3) Эффективность – все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за разумное время с помощью карандаша и бумаги. Например, нельзя считать простой операцией решение алгебраического уравнения 12-й степени. Поэтому, если в инструкции присутствует такая команда: найти решение уравнения х¹² + 5х¹¹ + 15х¹⁰ + 22х⁵ + 15258 = 0, то такая инструкция эффективной не является, а, следовательно, ее нельзя считать алгоритмом.

4) Результативность – любой алгоритм должен после своей работы выдавать какой-нибудь результат.

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

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

2.2. Формы записи алгоритма

На практике наиболее распространены следующие формы представления алгоритмов:

· словесная – запись на естественном (“человеческом”) языке;

· графическая – изображение команд в виде графических символов;

· программная – текст на языке программирования.

Словесный способ записи алгоритмов. Это <TBODY>описание последовательных этапов (шагов) обработки данных. Алгоритм задается в произвольном изложении на естественном языке. </TBODY>

Пример 2.1. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм может быть следующим (алгоритм Евклида):

1. Задать два числа.

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

3. Заменить большее из чисел разностью большего и меньшего из чисел.

4. Повторить алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения по следующим причинам:

· описания не формализованы (нет строгих правил);

· страдают многословностью записей;

· допускают неоднозначность толкования отдельных предписаний.

Графический способ записи алгоритмов. Графический способ представления алгоритмов является более наглядным по сравнению со словесным.

<TBODY>При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.</TBODY> Такое представление называется блок-схемой алгоритма.

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

В таблице 2.1. приведены наиболее часто употребляемые символы.

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

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

Таблица 2.1.
<TBODY>Название символа	Обозначение и пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало или конец алгоритма

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

На рис. 2.1. приведена блок-схема алгоритма решения задачи примера 2.1.

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

Запишем программу алгоритма решения задачи примера 2.1 на языке PASCAL.

var m, n: integer;

begin readln(m, n);

repeat if m = n then

begin writeln(n:5); halt; end;

if m > n then m:= m - n else n:= n - m;

until False;

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