Тема 1.3.Основные управляющие структуры программирования Понятие алгоритма
Любая программа является реализацией некоторого алгоритма. Понятие алгоритма является одними из фундаментальных понятий информатики, появившимся задолго до появления ЭВМ. В древнем мире алгоритмом называлось правило выполнения арифметических действий. До 50-х годов 20 века под алгоритмом понималась совокупность математических операций, выполняемых в определенном порядке. Дадим интуитивное понятие алгоритма. Алгоритм — понятное и точное сформулированное на определенном языке предписание исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи. Алгоритм формируется в расчете на конкретного исполнителя (человека или ЭВМ). Каждый алгоритм имеет некоторое множество входных и выходных величин. Причем размерность входного множества может быть равна нулю.
Свойства алгоритма:
- Массовость. Для алгоритма можно брать различные наборы входных данных, то есть в общем случае можно применять один и тот же алгоритм для решения целого класса задач. Хотя существуют алгоритмы, применяемые только к единственному набору входных данных (без входа).
- Дискретность — алгоритм может быть представлен в качестве последовательности шагов, поэтому его исполнение расчленяется на выполнение этих отдельных шагов.
- Конечность — выполнение алгоритма заканчивается после выполнения конечного числа шагов.
- Определенность — алгоритм рассчитан на чисто механическое исполнение, то есть действия, которые необходимо произвести должны быть строго и недвусмысленно определены в каждом возможном случае. Это означает, что один алгоритм будут выполнять разные исполнители, то они прейдут к одному результату.
- Эффективность- алгоритм должен быть выполнен не просто за конечное, а за разумное конечное время.
Существуют более формальные описания алгоритма, предложенные Постом, Тьюрингом, Марковым. На практике они друг другу эквивалентны друг другу и этому интуитивному понятию.
Способы описания алгоритма
- Словесно- формульный – алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий;
2. Структурный или блок-схемный. При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными линиями со стрелками (отражающими последовательность действий). В блоках записывается описания действий. Процесс, что есть выполнение операции или группы операций, в результате которых меняется значение, форма представления или расположение данных обозначается на блок-схеме алгоритма прямоугольником. Ввод — вывод данных, то есть преобразование данных в форму пригодную для обработки или отображения результатов обработки изображается параллелограммом. Решение, то есть выбор направления алгоритма в зависимости от некоторых переменных условий изображается ромбом. Пункт-останов, то есть начало конец, прерывание процесса обработки обозначаются овалом.
С помощью языка программирования. Управляющие структуры и основные конструкции языков программирования
Размещенная в памяти компьютера программа в момент выполнения занимает определенную область памяти. В каждый момент времени состояние программы характеризуется двумя типами сведений:
- состоянием некоторых ячеек памяти, понимаемых нами как переменные;
- активной точкой программы, то есть той командой программы, которая выполняется данный момент.
Следовательно, можно выделить и два основных класса действий, которые может выполнять вычислительная система:
- действия, выделяющие область памяти под переменные программы (описания).
- действия, меняющие точку выполнения программы (операторы, инструкции, конструкции).
Различные совокупности действий второго класса также называют управляющими структурами.
В теории программирования доказано, что программу для решения задачи любой сложности можно составить их трех структур, называемых следованием (цепочкой), ветвлением и циклом. Этот результат установлен Бойном и Якопини в 1966 г. путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций. Каждая из этих управляющих структур реализована в языке программирования набором соответствующих конструкций.
Структура следования (естественная фундаментальная структура) реализует линейный вычислительный процесс, то есть процесс, в котором действия выполняются последовательно, в порядке их записи. Каждое действие является самостоятельным, независимым от каких-либо условий. В языках программирования цепочки реализуются так называемым составной конструкцией следующим образом.
На блок-схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
К аждый оператор будет выполняться только тогда, когда закончит выполняться предыдущий. Оператор ; — называют оператором следования. Составные операторы заключены в инструктивные скобки. В языке С++ инструктивные скобки записываются как < >. В Паскале –begin end. Составные операторы также называют блоком кода, инструктивным блоком, блоком. Тело любой функции в С++ является блоком.
Пример структуры следования (цепочки)
Структура ветвления реализует ветвящийся вычислительный процесс, то есть процесс, для реализации которого предусмотрено несколько направлений (ветвей). Ветвление в программе – это выбор одной из нескольких последовательностей операторов при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным данным или конечным результатам. Хотя на схеме алгоритма должны быть показаны все возможные направления вычислений в зависимости от выполнения определенного условия (или условий), при однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, по которой осуществляется вычисления, должна приводить к завершению вычислительного процесса.
В языках программирования структура ветвления реализуется условными и селективными констркуциями. Условные конструкции в общем случае имеют форму
если выражение то действие1 иначе действие2;
и следующей смысл: если выражение верно то выполняется действие1, иначе выполняется действие2.
Кроме того, используется и усеченная форма условной конструкции
если выражение то действие1;
На блок-схеме ветвление и усеченное ветвление изображаются следующим образом:
В С++ синтаксис условной конструкции
if (выражение) опрератор1; else оператор2;
Выражение должно быть скалярным и иметь арифметический тип или тип указателя. В операторе if оператор1 выполняется в том случае, если выражение ненулевое, иначе выполняется оператор2 или не выполняются никакие действия, если оператор2 не задан, то есть отсутствует else. В частности, если a целое, то if (a) эквивалентно if (a!= 0).
Оператор1 и оператор2 могут представлять собой один оператор или блок операторов, но не могут быть описаниями.
В соответствии неписаными правилами хорошего стиля программирования в условных инструкциях логическое выражение необходимо составлять таким образом, чтобы чаще всего оно было истинным.
Часто используются в условиях логические операции &&, ||, !. Операции && и || не будут вычислять второй аргумент, если это не нужно. Например, if (p && r) … вначале проверяет, является ли p не нулем, и только, если это так, то проверяет r.
Если некоторое действие выполняется при выполнении двух условий желательно записывать их в виде одного выражения.
Селективные инструкции используются для реализации мультиветвления и в общем случае имеют вид:
имеет значение2 то действие2
имеет значениеn то действиеn
Н а блок-схеме мультиветление изображается следующим образом:
В С++ существует конструкция мультиветвления (переключатель). Синтаксис переключателя:
case константное_выражение2: оператор2;
case константное_выражениеn: операторn;
Если не предусмотрены переходы и выходы из переключателя, то в нем последовательно выполняются все операторы, начиная с той метки, на которую передано управление. Для выхода из переключателя обычно используют оператор break.
Примеры смотри в пособии.
Структура цикла реализует циклический вычислительный процесс, то есть процесс, включающий в себя повторяемую последовательность действий — цикл. В организации цикла можно выделить следующие этапы:
- подготовка (инициализация параметров цикла);
- выполнение вычислений цикла (тело цикла);
- модификация параметров (которая фактически является частью тела цикла);
- проверка условия окончания (или условия продолжения) цикла.
Порядок выполнения этих этапов может и меняться. Если условие проверяется до выполнения тела цикл, то говорят о цикле с предусловием. Если – после, то о цикле с постусловием. Главное отличие- цикл с постусловием обязательно выполнится хотя бы один раз.
На блок схеме циклы изображаются следующим образом
Цикл называется детерминированным, если число повторений цикла заранее определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значения параметров, участвующих в вычислениях.
В С++ существует три конструкции цикла.
for (инициализация_цикла; выражение_условие; список_выражений)
Тело_цикла не может быть описанием, это либо один (может быть и пустой) оператор, который всегда завершается точкой с запятой, либо блок операторов, заключенных в скобки <>. Выражение_условие – это выражение, определяющее условие продолжения итераций. Операторы тела цикла выполняются, пока условие истинно (не равно нулю). Инициализация_цикла в цикле for — это последовательность определений и выражений, разделяемых запятыми. Даже если она пустая, точка с запятой должна присутствовать. Чаще всего здесь устанавливается начальные значения счетчиков и параметров цикла. Выражения из списка_выражений выполняются после выполнения операторов тела цикла и до следующей проверки выражения_условия.
Примеры смотри в пособии.
Конструкцию for чаще применяют для организации детерминированных циклов. А конструкции do и while чаще применяют для итерационных циклов. Хотя такое функциональное разделение довольно условно.
Два примера использования конструкции цикла для построения индуктивной последовательности, то есть последовательности,где каждый следующий член получается путем вычисления определенной формулы над предыдущими челнами.
Примером индуктивной последовательности являются числа Фибоначчи, которые вычисляются по следующей формуле:
То есть последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, ….
Пример детерминированного цикла
// Вычисление k-го числа Фибоначчи
Тема 7. Представление основных управляющих структур программирования
Оператор присваивания записывается в виде: <переменная>= ; Значение выражения из правой части присваивается переменной из левой части оператора присваивания. При присваивании необходимо обеспечивать совместимость типов (иногда говорят – совместимость по присваиванию), т.е. тип, полученный при вычислении выражения, должен быть совместим с типом переменной, которой это значение должно быть присвоено. Значение типа T1 является совместимым по присваиванию с типом T2 (то есть, допустим, оператор T1=T2), если выполняется одно из следующих условий: ∙ T1 и T2 имеют тождественные типы, и ни один из них не является файловым типом или структурным типом, содержащим компонент с файловым типом на одном из своих уровней.
∙ T1 и T2 являются совместимыми порядковыми типами, и значения типа T2 попадают в диапазон возможных значений T1. ∙ T1 и T2 являются вещественными типами, и значения типа T2 попадают в диапазон возможных значений T1. ∙ T1 является вещественным типом, а T2 является целочисленным типом. ∙ T1 и T2 являются строковыми типами. ∙ T1 является строковым типом, а T2 является символьным типом (Char). ∙ T1 и T2 являются совместимыми множественными типами, и все члены значения типа T2 попадают в диапазон возможных значений T1. ∙ T1 и T2 являются совместимыми типами указателей. ∙ T1 и T2 являются совместимыми процедурными типами. ∙ T1 представляет собой процедурный тип, а T2 – процедура или функция с идентичным типом результата, идентичным числом параметров и соответствием между типами параметров. На этапе компиляции и выполнения программы выдается сообщение об ошибке, если совместимость по присваиванию необходима, а ни одно из условий предыдущего списка не выполнено.
Составной оператор
Синтаксис оператора < <операторы>> Здесь «операторы» – один или несколько любых операторов языка Си, разделенных точкой с запятой. Составной оператор предназначен для объединения нескольких операторов в один, что имеет решающее значение там, где синтаксис языка Си допускает использование только одного оператора.