Алгоритм — это точное предписание, которое определяет
процесс, ведущий от исходных данных к требуемому конечному результату. Слово
алгоритм происходит от арабского имени хорезмийского математика IX века
аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII
веке познакомились с позиционной системой счисления, и в средневековой Европе
алгоритмом называлась десятичная позиционная система счисления и правила счета
в ней.
Применительно к ЭВМ алгоритм определяет вычислительный
процесс (ВП), начинающийся с обработки совокупности исходных данных и
направленный на получение определенных результатов. Для обеспечения возможности
реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то
есть на языке программирования.
Таким образом, можно дать следующее определение программы:
программа для ЭВМ представляет собой описание алгоритма и данных на некотором
языке программирования, предназначенное для последующего автоматического
выполнения.
Свойства алгоритма
Результативность
Означает возможность получения результата после выполнения
конечного количества операций.
Определенность
Определенность состоит в совпадении получаемых результатов
независимо от пользователя и применяемых технических средств.
Массовость
Массовость заключается в возможности применения алгоритма к
целому классу однотипных задач, различающихся конкретными значениями исходных
данных.
Дискретность
Возможность расчленения процесса вычислений, предписанных
алгоритмом, на отдельные этапы, возможность выделения участков программы с
определенной структурой.
Правила описания
Для задания алгоритма необходимо описать следующие его
элементы:
- набор объектов, составляющих совокупность возможных
исходных данных, промежуточных и конечных результатов;
- правило начала;
- правило непосредственной переработки информации (описание
последовательности действий);
- правило окончания;
- правило извлечения результатов.
Способы описания алгоритмов
Наиболее распрастраненными способами описания алгоритмов
являются словесно-формульный и структурный (блок-схемный).
Словесно-формульный
При словесно-формульном способе алгоритм записывается в виде
текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо
найти значение следующего выражения:
у = 2а – (х+6).
Алгоритм решения этой
задачи может быть записан в следующем виде:
1. Начало
2. Ввести значения а и х.
3. Сложить х и 6.
4. Умножить a на 2.
5. Вычесть из 2а сумму
(х+6).
6. Вывести у как результат
вычисления выражения.
7. Конец
Блок-схемный
При блок-схемном описании алгоритм изображается
геометрическими фигурами (блоками), связанными по управлению линиями
(направлениями потока) со стрелками. В блоках записывается последовательность
действий.
Данный способ по сравнению с другими способами записи
алгоритма имеет ряд преимуществ. Он наиболее нагляден: каждая операция
вычислительного процесса изображается отдельной геометрической фигурой. Кроме
того, графическое изображение алгоритма наглядно показывает разветвления путей
решения задачи в зависимости от различных условий, повторение отдельных этапов
вычислительного процесса и другие детали.
В настоящее время действует единая система программной
документации (ЕСПД), которая устанавливает правила разработки, оформления
программ и программной документации.
В пределах одной схемы рекомендуется изображать блоки
одинаковых размеров. Все блоки нумеруются. Линии, соединяющие блоки и
указывающие последовательность связей между ними, должны проводится параллельно
линиям рамки. Стрелка в конце линии может не ставиться, если линия направлена
слева направо или сверху вниз. В блок может входить несколько линий, то есть
блок может являться преемником любого числа блоков. Из блока (кроме
логического) может выходить только одна линия. Логический блок может иметь в
качестве продолжения один из двух блоков, и из него выходят две линии. Если на
схеме имеет место слияние линий, то место пересечения выделяется точкой. В
случае, когда одна линия подходит к другой и слияние их явно выражено, точку
можно не ставить.
Виды и назначение основных блоков
Структурные схемы алгоритмов
Можно выделить и наглядно представить графически три
простейшие структуры:
1/ последовательность двух или более операций - линейные ВП;
2/ выбор направления - ветвящиеся ВП;
3/ повторение - циклические ВП.
Любой вычислительный процесс может быть представлен как
комбинация этих элементарных алгоритмических структур.
Линейный ВП
Линейным принято называть вычислительный процесс, в котором
операции выполняются последовательно, в порядке их записи. Каждая операция
является самостоятельной, независимой от каких-либо условий. На схеме блоки,
отображающие эти операции, располагаются в линейной последовательности.
y = (b2-ac)/(a+c)
Ветвящийся процесс
Вычислительный процесс называется ветвящимся, если для его
реализации предусмотрено несколько направлений. Направление ветвления
выбирается логической проверкой, в результате которой возможны два ответа: «да»
— условие выполнено и «нет» — условие не выполнено. В зависимости от выполнения
условия процесс реализуется только по одной ветви, а остальные исключаются.
Любая ветвь, по которой осуществляются вычисления, должна приводить к
завершению вычислительного процесса.
Ветвящийся процесс, включающий в себя две ветви, называется
простым, более двух ветвей — сложным. Сложный ветвящийся процесс можно
представить с помощью простых ветвящихся процессов.
Y
= (а+b), если Х <0;
Y
=с/b, если Х >0.
Циклический ВП
Циклический ВП содержит цикл - многократно повторяемый
участок программы.
В организации цикла можно выделить следующие этапы:
·подготовка
(инициализация) цикла: задание начальных значений переменным цикла перед первым
его выполнением
·тело
цикла: выполнение вычислений цикла;
·модификация:
изменение значения переменной цикла (той переменной, которая проверяется в
условии)
·управление
цикла: проверка условия окончания цикла; если выполняется условие продолжения
цикла, происходит переход в начало тела цикла; если выполняется условие
окончания цикла - выход из него, т.е. передача управления оператору, следующему
за циклом.
В зависимости от расположения проверки условия окончания
цикла различают циклы с нижним и верхним окончаниями.
Для цикла с нижним окончанием (с послеусловием) тело цикла
выполняется как минимум один раз, так как сначала производятся вычисления, а
затем проверяется условие выхода из цикла.
В случае цикла с верхним окончанием (с преусловием) тело
цикла может не выполниться ни разу в случае, если сразу соблюдается условие
выхода.
Цикл называется детерминированным,
если число повторений тела цикла заранее известно или определено. Такой цикл
называется также циклом со счетчиком, т.к число повторений подсчитывается с
помощью специальной переменной, для которой заданы начальное и конечное
значение, а также шаг изменения. Переменную-счетчик называют параметром цикла,
а сам цикл - циклом с параметром.
Цикл называется итерационным,
если число повторений тела цикла заранее неизвестно, а зависит от значений
параметров (некоторых переменных), участвующих в вычислениях. В процессе
повторения цикла образуется последовательность значений у1, у2, ..., уn, ..., сходящаяся к некоторому пределу а
Каждое новое значение уn в
такой последовательности определяется с учетом предыдущего уn-1
и является по сравнению с ним более точным приближением к искомому результату
(пределу) а. Каждое такое приближение
называется итерацией.
