Алгоритмы

 

1.1 Основные определения: алгоритм, вход, результат; понятие правильного и неправильного алгоритма; псевдокод

 

 

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

 

1) Быть простым для понимания, перевода в программный код и отладки;

2) Эффективно использовать вычислительные ресурсы.

 

Алгоритм считают правильным (correct), если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solve) данную вычислительную задачу. Неправильный алгоритм для некоторого входа может вообще не остановиться или дать неправильный результат. Алгоритм может быть описан различными способами, в том числе и при помощи псевдокода, принадлежащего более высокому уровню абстракции по сравнению с языками программирования высокого уровня (C#, Pascal, Basic и т.д.). В математическом пакете MathCAD при написании кода функций, определяемых пользователем, используется нотация, напоминающая описываемый ниже псевдокод.

 

Таблица 1.1 - Соглашения, лежащие в основе псевдокода

№	Описание
	Отступ от левого поля указывает на уровень вложенности (это позволяет отказаться от применения begin и end)
	Комментарий обозначается символом “►”.
	Циклы while, for, repeat и условные конструкции имеют тот же смысл, что и в языке Pascal.
	Символ “¬” имеет смысл оператора присваивания.
	Запись i ¬ j ¬ e обозначает j ¬ e; i ¬ j или i ¬ e.
	Переменная, обозначающая массив или объект, считается указателем на составляющие его данные.
	Все переменные (по-умолчанию) – локальные.
	Оператор доступа к элементу массива пишется в квадратных скобках [].
	Запись “A[1..j]” обозначает A[1], A[2], A[3]..A[j].
	Доступ к полю (field) объекта (object): field[object].
	Параметры в подпрограмму передаются по-значению (by value), но при передаче объекта его свойства копируются в виде указателей. Т.е. если в качестве параметра передается объект x, то присваивание x ¬ y снаружи заметить нельзя, а f [x] ¬ 5 можно.

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

 

 

Листинг 1.1 – Псевдокод алгоритма сортировки вставками

 

procedure InsertSort(n: integer;

var A: array[1..n] of integer);

var

i, j, Tmp: integer;

begin

for i := 2 to n do begin

{Сохраняем текущий элемент}

Tmp := A[i];

{Сдвигаем элементы, большие, чем текущий}

j := i-1;

while (A[j] > Tmp) and (j > 1) do begin

A[j+1] := A[j];

j := j-1;

end;

{Вставляем текущий элемент}

A[j+1] := Tmp;

end;

end;

 

 

Листинг 1.2 – Сортировка вставками