Лабораторная работа № 19
Основы алгоритмизации
Теоретическая часть
Алгоритм — это предписание некоторому исполнителю выполнить конечную последовательность действий, приводящую к некоторому результату.
В программировании алгоритм является фундаментом программы, а основным исполнителем — компьютер. На стадии тестирования алгоритма исполнителем может быть сам программист.
Алгоритм может быть записан с помощью блок-схемы, текстовым предписанием, с помощью рисунков, таблично или на специальном алгоритмическом языке. Наиболее популярны блок-схемы и предписания. Преимущество блок-схем — в наглядности алгоритма.
Основными свойствами алгоритма являются:
· дискретность — представление алгоритма в виде последовательности шагов;
· массовость — применимость алгоритма к некоторому множеству исходных данных;
· определенность — за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие;
· однозначность — при повторном применении алгоритма к тем же исходным данным должен быть получен тот же результат.
|
|
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
В зависимости от применяемых базовых структур различают следующие типы алгоритмов:
· линейные (базовая структура "следование"),
· разветвляющиеся (базовая структура "ветвление"),
· циклические (базовая структура "цикл").
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. Их можно соединять друг с другом в любой последовательности. В качестве действия может использоваться любая из перечисленных структур, что обеспечивает возможность вложенности одних структур в другие. Возврат назад выполняется только в циклах.
1. Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим:
Алгоритмический язык | Язык блок-схем |
действие 1 действие 2......... действие n |
2. Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Структура ветвление существует в четырех основных вариантах:
· | если—то; |
· | если—то—иначе; |
· | выбор; |
· | выбор—иначе. |
Алгоритмический язык | Язык блок-схем |
1. если—то | |
если условие то действия все | |
2. если—то—иначе | |
если условие то действия 1 иначе действия 2 все | |
3. выбор | |
выбор при условие 1: действия 1 при условие 2: действия 2 ............ при условие N: действия N все | |
4. выбор—иначе | |
выбор при условие 1: действия 1 при условие 2: действия 2 ............ при условие N: действия N иначедействия N+1 все |
Примеры структуры ветвление
|
|
Алгоритмический язык | Язык блок-схем |
если X < 0 то X:= -X все | |
если a > =0 то y:= 1/a иначе y:= 4 все | |
выбор при x < 7: y:= 2-x при x >= 0: y:= 6 при x > 0: y:= x-10 все | |
выбор при x <=a: y:= sin(x) при x>=b: y:=tg(x) иначе y:=cos(x) все |
3. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Основные разновидности циклов представлены в таблице:
Алгоритмический язык | Язык блок-схем | |
Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. | ||
нц пока условие тело цикла (последовательность действий) кц | ||
Цикл типа до. Предписывает выполнять тело цикла до тех пор, пока значение условия не станет истинным. | ||
нц тело цикла (последовательность действий) до условие кц | ||
Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. | ||
нц для i от i1до i2 тело цикла (последовательность действий) кц | ||
Примеры структуры цикл
Алгоритмический язык | Язык блок-схем |
нц пока i <= 5 S:= S+A[i] i:= i+1 кц | |
нц N:=10*M M:=M-1 до M=0 кц | |
нц для i от 1 до 5 X[i]:= i Y[i]:= X[i]/2 кц |