- •Тема 11. Основы алгоритмизации и программирования
- •11.1 Алгоритмы. Алгоритмизация. Алгоритмические языки
- •11.1.1. Понятие алгоритма
- •11.1.2. Базовые алгоритмические структуры
- •11.1.3. Итерационные циклы
- •11.1.4. Вложенные циклы
- •11.1.5. Простейшие структуры данных
- •11.2. Примеры разработки алгоритмов
- •11.2.1. Линейные алгоритмы
- •11.2.2. Разветвляющиеся алгоритмы
- •11.2.3. Циклические алгоритмы
- •11.2.4. Алгоритмы со структурами вложенных циклов
- •11.2.5. Вспомогательные алгоритмы
- •11.2.6. Декомпозиция алгоритма
- •11.3. Технология подготовки и решения задач с помощью компьютера
- •11.4. Языки программирования
- •11.4.1. Алгоритмические языки
- •11.4.2. Принципы построения трансляторов
11.1.2. Базовые алгоритмические структуры
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов и простейший псевдокод.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
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 то y := sin(x) все |
|
если a > b то a := 2*a; b := 1 иначе b := 2*b все |
|
выбор при n = 1: y := sin(x) при n = 2: y := cos(x) при n = 3: y := 0 все |
|
выбор при a > 5: i := i+1 при a = 0: j := j+1 иначе i := 10; j:=0 все |
|
3. Базовая структура "цикл" (повторение). Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:
Псевдокод |
Язык блок–схем |
Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. |
|
нц пока условие тело цикла (последовательность действий) кц |
|
Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. |
|
нц для i от i1 до i2 тело цикла (последовательность действий) кц |
|
Для того чтобы понять, как функционирует не только этот, а и любой другой цикл, обратимся к рис. 11.1, 11.8. На них показана общая структура цикла и его важнейшие параметры. Как видно из рис. 11.1, цикл состоит из заголовка и тела. Всякий цикл обязательно имеет свой счетчик.
На рис. 11.2, где показана структура и параметры заголовка цикла, роль такого счетчика выполняет переменная i. Внутри заголовка после счетчика и символа "=" через запятую указывает начальное и конечное значения счетчика и шаг его изменения (на рис. 11.2 их роль выполняют переменные j, k, l соответственно). Если значение шага l = l, то его можно не указывать.
Сначала производится вход в цикл. После этого начинается его выполнение.
|
|
Рис. 11.1. Структура цикла |
Рис. 11.2. Структура заголовка цикла |
Внутри заголовка счетчику первоначально присваивается значение i = j. Затем выполняется блоки, образующие тело цикла. Обработка блоков внутри цикла производится по часовой стрелке. В результате после первого выполнения тела цикла управление вновь передается заголовку. Здесь к текущему значению счетчика добавится шаг. Теперь, если новое значение счетчика не вышло за свои пределы (т.е. не стало больше своего конечного значения при положительном шаге или меньше конечного значения – при отрицательном шаге), то снова выполняется тело цикла, вновь после возврата к заголовку к счетчику добавляется шаг. Так цикл будет выполняться до тех пор, пока значение счетчика однажды не выйдет за предписанный предел. Как только такой предел будет преодолен, произойдет выход из цикла и управление будет передано блоку, который следует сразу за циклом.
Примеры структуры цикл
Псевдокод |
Язык блок–схем |
нц пока i <= 5 S := S+A[i] i := i+1 кц |
|
нц для i от 1 до 5 X[i] := i*i*i Y[i] := X[i]/2 кц |
|