Студенты-Программеры

Алгоритм – это последовательность действий приводящая конкретному результату за конечное число шагов.

Способы представления:

Словесное описание;

Табличное (в виде таблице);

Аналитическое (формулой);

Графическое (блок схема алгоритма).

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

- определенность - однозначная определенность результатов выполнения каждого шага алгоритма;

- конечность - однозначная определенность результатов выполнения каждого шага алгоритма за конечное время;

- результативность - получение конечного результата за конечное время;

- массовость - возможность использования алгоритма для некоторого класса исходных данных;

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

Кроме переменных в алгоритмах используются массивы переменных - наиболее широко известная структура данных. Массив - область памяти, где могут размещаться совокупности данных определенного типа (целого, вещественного и т.д.). Все компоненты массива имеют одинаковый тип и являются одинаково доступными. Для обращения к отдельной компоненте используется имя массива с индексом, определяющим ее местоположение в массиве. Таким образом, массив характеризуется фиксированным именем, фиксированным типом и фиксированной размерностью. Например, последовательность чисел -1, 25, 13, 18, 8 можно рассматривать как массив целого типа с именем Vector, который содержит 5 элементов. К любому элементу этого массива можно обратиться следующим образом:

Vector[1], где I может принимать значения в диапазоне от 1 до 5. Vector[2] = 25;

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

- графический способ (схемы алгоритмов, диаграммы Насси - Шнейдермана );

- словесный способ ( специальный язык проектирования программ - псевдокод и программа).

Следуя принципам структурного программирования, задачу необходимо представить как набор последовательных шагов (действий), избегая непоследовательных переходов. Этому требованию в полной мере отвечают диаграммы Насси - Шнейдермана и псевдокод.

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

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

Алгоритм:

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход.

Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:

Program BubbleSort;

Uses Crt;

Const

N=20; {длина массива}

Type

TVector = array [1..n] of Real;

Var

Vector:TVector;

B : Real;

I, k : integer;

Begin

ClrScr;

Writeln (‘Введите элементы массива’);

For I: = 1 to n do Read (Vector[i]); Readln;

{——————————————————}

For k: =n downto 2 do

{“Всплывание”очередного максимального элемента}

{на k-ую позицию}

For I: = 1 to k-1 do

If Vector [i]>Vector [i+1] then

Begin

B: =Vector[i];

Vector[i]: =Vector [i+1];

Vector [i+1]:=B

End;

{——————————————————}

Writeln (‘Отсортированный массив’);

For i: = 1 to n do Write (Vector[i]:8:2);

Writeln;

End.

Сравнение прямых методов сортировки.

Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька»).