Линейные и разветвляющиеся структуры; циклические структуры, типы циклов.
Доказано, что любую программу можно написать с использованием трех управляющих структур:
- следования, или последовательности операторов;
- ветвления, или условного оператора;
- повторения, или оператора цикла.
Программа, составленная из канонических структур, будет называться регулярной программой, т.е. иметь 1 вход и 1 выход, каждый оператор в программе может быть достигнут при входе через ее начало (нет недостижимых операторов и бесконечных циклов). Управление в такой программе передается сверху-вниз. Снабженные комментариями, такие программы хорошо читабельны.
Следование
Образуется последовательностью действий, следующих одно за другим:
|
|
Действия А и В могут быть: - отдельным оператором; - вызовом с возвратом некоторой процедуры; - другой управляющей структурой.
|
Ветвление
Выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
«если – то - иначе»
Проверка P представляется предикатом, т.е. функцией, задающей логическое выражение или условие, значением которого может быть истина или ложь. Эта структура может быть неполной, когда отсутствует действие, выполняемое при ложном значении логического выражения. Тогда структура будет следующая:
«если - то»
Повторение
Практически все алгоритмы решения задач содержат циклически повторяемые участки. Цикл – это одно из фундаментальных понятий программирования.
Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов:
Цикл типа «пока». Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
Цикл типа «для». Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
Предопределенные процессы. Рекрусия.
Предопределенными процессами называются процессы, определенные в системе заранее. Для языка С таким процессом является функция, имеющая прототип, то есть определенная и несущая сведения о своем существовании в систему до начала работы самой системы.
Рекурсия – это способ организации вычислительного процесса, при котором подпрограмма в ходе производит вызов из раздела операторов самой себя. Рекурсивным называется обьект частично состоящий или определяемый с помощью самого себя. Рекурсия, как правило, применяется в тех случаях, когда основную задачу можно разбить на подзадачи той же структуры, что и первоначальная задача.
Прямой рекурсией является вызов функции внутри тела этой функции.
Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.
Особое внимание необходимо уделить корректному выходу из рекурсивной подпрограммы. Рекурсивный вызов подпрограммы должен управляться некоторым условием, которое в определенный момент перестает выполняться. Пока условие истинно, рекурсия повторяется, но как только условие становится ложным, начинается последовательный рекурсивный возврат из всех созданных копий подпрограммы. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
По месторасположению условия входа из всех созданных копий рекурсивных подпрограмм:
Тип 1 – с выполнением действий на рекурсивном спуске;
Тип 2 – c выполнением действий на рекурсивном возврате;
Тип 3 - с выполнением действий на рекурсивном спуске и возрате.
Рекурсивные алгоритмы особенно подходят для задач, где обабатываемые данные определяются в терминах рекурсии. Однако это не означает, что рекурсивное определение данных гарантирует эффективность использования рекурсивных алгоритмов для решения таких задач.