Алгоритм и его свойства

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

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

Пример.

Пусть имеется последовательность из N чисел (например результаты измерения средней дневной температуры за определенный период). Надо подсчитать сколько отрицательных чисел в этой последовательности. Число ноль будем считать положительным.

Можно использовать следующий способ.

Последовательно просматриваем числа, начиная с первого и когда очередное число < 0 прибавляем к счетчику отрицательных чисел единицу.

Это идея алгоритма, ее надо уточнить и представить в виде последовательности шагов.

Во-первых счет начинаем с нуля, поэтому счетчик (KN) надо сначала установить на ноль.

Во-вторых надо просматривать N чисел, поэтому нужен счетчик чисел (М), причем этот счетчик надо установить на 1 (М = 1), а при переходе к следующему числу этот счетчик надо увеличивать на 1.

В-третьих последовательность может быть пустой (N = 0), поэтому надо сначала надо сравнивать М с N и проверять очередное число если М <= N.

Алгоритм.

1. Записать в KN ноль, в М 1.

2. Проверить, если M <= N, то идти к шагу 3, иначе идти к шагу 6.

3. Проверить, если число < 0, то увеличить счетчик KN на 1.

4. Увеличить счетчик М на единицу.

5. Перейти к шагу 2.

6. Взять число находящееся в счетчике KN в качестве результата. Стоп.

3.2.1. Свойства алгоритма.

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

Массовость - означает, что алгоритм применим ко множеству наборов исходных данных (можно решать класс задач).

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

3.2.2. Требования к алгоритму

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

Требования:

1. Алгоритм должен правильно решать задачу.

2. Затраты времени и усилий на разработку алгоритма и отладку программы должны быть минимальными.

3. Затраты времени на выполнение алгоритма и требуемый объем памяти должны быть минимальными.

4. Реализация алгоритма должна быть легка для понимания, проста для доказательства и удобна для модификации в случае изменения задания.

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