Алгоритм и его свойства. Запись алгоритмов. Виды алгоритмов
В 1983 году отмечалось 1200-летие со дня рождения величайшего средневекового ученого Средней Азии Мухамеда ибн Мусы аль-Хорезми. С именем этого ученого связано понятие алгоритма.
Алгоритм – точное, понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Итак, алгоритм - это определённая последовательность действий, которые необходимо выполнить, чтобы получить результат. Алгоритм может представлять собой некоторую последовательность вычислений, а может - последовательность действий нематематического характера. Для любого алгоритма справедливы общие закономерности - свойства алгоритма.
Свойства алгоритма
Дискретность. Конечность и понятность Детерминированность Массовость РезультативностьДискретность - это свойство алгоритма, когда алгоритм разбивается на конечное число элементарных действий (шагов).
Конечность и понятность - свойство алгоритма, при котором каждое из этих элементарных действий (шагов) являются законченными и понятными.
Детерминированность (определенность) - свойство, когда каждое действие (операция. указание. шаг. требование) должно пониматься в строго определённом смысле, чтобы не оставалась места произвольному толкованию. чтобы каждый, прочитавший указание, понимал его однозначно.
Массовость - свойство, когда по данному алгоритму должна решаться не одна, а целый класс подобных задач.
Результативность – свойство, при котором любой алгоритм в процессе выполнения должен приводить к определённому результату. Отрицательный результат также является результатом.
Способы задания алгоритмов.
Словесное описание (на языке исполнителя).Словесная запись алгоритма представляет собой последовательность этапов обработки данных и задается в произвольном изложении на естественном языке. Ориентирована на исполнителя-человека
Табличное описание.ФИО | 1.Кол-во дней | 2.Дневная тарифн. ставка | 3. З/пл= 1*2 |
Иванов | 25 | 100 | 2500 |
Алгоритм изображается в виде последовательности, связанных между собой функциональных блоков, каждому из которых соответствует выполнение одного или нескольких действий (операторов).
Приняты определенные стандарты графических изображений функциональных блоков.
НАЧАЛО | - начало алгоритма |
| - конец алгоритма |
| - ввод/вывод |
КОНЕЦ
| - оператор действия |
| - проверка условия |
Внутри блока запись не формализована
Псевдокод - представляет собой систему обозначений и правил для единообразной записи алгоритма. Псевдокод занимает промежуточное положение между словесной записью алгоритма и алгоритмическим языком. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущих формальным языкам. Вводятся понятия служебных слов, смысл которых определён раз и навсегда. Служебные слова выделяются в печатном тексте жирным шрифтом.Рассмотрим запись алгоритма Евклида на псевдокоде:
Алг алгоритм Евклида
Арг N, M
Рез НОД
Нач
Пока N ¹M
Н. ц.
Если M > N
То M: = M-N
Иначе N: = N-M
Всё
К. ц.
НОД: = M
Кон
На алгоритмическом языке (программа).Алгоритмический язык ориентирован на исполнителя ЭВМ, полностью формализованная запись алгоритма.
Рассмотрим запись алгоритма Евклида на языке программирования Pascal:
Program NOD;
Var n, m:word;
Begin
Writeln(‘Input m, n);
Readln(m, n);
While m<>n do
If m>n then m:=m-n
else n:=n-m;
Writeln(‘nod=’,m)
End.
Типы алгоритмических структур.
Существует три алгоритмические структуры. Из них составляются алгоритмы любой сложности.
1) СЛЕДОВАНИЕ
|
2) ВЕТВЛЕНИЕ
a) полное
| Если условие выполняется, то оператор 1, а если оно не выполняется, то оператор 2. |
b) неполное
| Если условие выполняется, то оператор выполняется, а если нет, то ни чего не происходит (просто пролетает). |
3) ЦИКЛ
a) с предусловием
| Если условие истинно, то выполняется оператор, а если ложно, то выходит из цикла. |
b) с постусловием
| Пока условие ложно, мы в цепи, а когда истинно, то мы вне цепи. |
Каждая последовательность имеет вход и выход
