Тема 5. Управляющие структуры и основные конструкции языков программирования

Тема 4. Алгоритмы

Понятие алгоритма

Любая программа является реализацией некоторого алгоритма. Понятие алгоритма является одними из фундаментальных понятий информатики, появившимся задолго до появления ЭВМ. В древнем мире алгоритмом называлось правило выполнения арифметических действий. До 50-х годов 20 века под алгоритмом понималась совокупность математических операций, выполняемых в определенном порядке. Дадим интуитивное понятие алгоритма. Алгоритм - понятное и точное сформулированное на определенном языке предписание исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи. Алгоритм формируется в расчете на конкретного исполнителя (человека или ЭВМ). Каждый алгоритм имеет некоторое множество входных и выходных величин. Причем размерность входного множества может быть равна нулю.

Свойства алгоритма:

- Массовость. Для алгоритма можно брать различные наборы входных данных, то есть в общем случае можно применять один и тот же алгоритм для решения целого класса задач. Хотя существуют алгоритмы, применяемые только к единственному набору входных данных (без входа).

- Дискретность - алгоритм может быть представлен в качестве последовательности шагов, поэтому его исполнение расчленяется на выполнение этих отдельных шагов.

- Конечность - выполнение алгоритма заканчивается после выполнения конечного числа шагов.

- Определенность - алгоритм рассчитан на чисто механическое исполнение, то есть действия, которые необходимо произвести должны быть строго и недвусмысленно определены в каждом возможном случае. Это означает, что один алгоритм будут выполнять разные исполнители, то они прейдут к одному результату.

- Эффективность- алгоритм должен быть выполнен не просто за конечное, а за разумное конечное время.

Существуют более формальные описания алгоритма, предложенные Постом, Тьюрингом, Марковым. На практике они друг другу эквивалентны друг другу и этому интуитивному понятию.

Способы описания алгоритма

1. Словесно- формульный – алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий;

2. Структурный или блок-схемный. При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными линиями со стрелками (отражающими последовательность действий). В блоках записывается описания действий. Процесс, что есть выполнение операции или группы операций, в результате которых меняется значение, форма представления или расположение данных обозначается на блок-схеме алгоритма прямоугольником. Ввод - вывод данных, то есть преобразование данных в форму пригодную для обработки или отображения результатов обработки изображается параллелограммом. Решение, то есть выбор направления алгоритма в зависимости от некоторых переменных условий изображается ромбом. Пункт-останов, то есть начало конец, прерывание процесса обработки обозначаются овалом.

С помощью языка программирования.

Тема 5. Управляющие структуры и основные конструкции языков программирования

Размещенная в памяти компьютера программа в момент выполнения занимает определенную область памяти. В каждый момент времени состояние программы характеризуется двумя типами сведений:

- состоянием некоторых ячеек памяти, понимаемых нами как переменные;

- активной точкой программы, то есть той командой программы, которая выполняется данный момент.

Следовательно, можно выделить и два основных класса действий, которые может выполнять вычислительная система:

- действия, выделяющие область памяти под переменные программы (описания).

- действия, меняющие точку выполнения программы (операторы, инструкции, конструкции).

Различные совокупности действий второго класса также называют управляющими структурами.

В теории программирования доказано, что программу для решения задачи любой сложности можно составить их трех структур, называемых следованием (цепочкой), ветвлением и циклом. Этот результат установлен Бойном и Якопини в 1966 г. путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций. Каждая из этих управляющих структур реализована в языке программирования набором соответствующих конструкций.

Структура следования (естественная фундаментальная структура) реализует линейный вычислительный процесс, то есть процесс, в котором действия выполняются последовательно, в порядке их записи. Каждое действие является самостоятельным, независимым от каких-либо условий. В языках программирования цепочки реализуются так называемым составной конструкцией следующим образом.

{

оператор 1;

оператор 2;

….

оператор n;

}

На блок-схеме блоки, отображающие эти операции, располагаются в линейной последовательности.

Каждый оператор будет выполняться только тогда, когда закончит выполняться предыдущий. Оператор ; - называют оператором следования. Составные операторы заключены в инструктивные скобки. В языке С++ инструктивные скобки записываются как { }. В Паскале –begin end. Составные операторы также называют блоком кода, инструктивным блоком, блоком. Тело любой функции в С++ является блоком.

Пример структуры следования (цепочки)

{

int a=10,b,c;

scanf(“%d”,&b);

c=a+b;

printf(”a+b =%d”,c);

}

Структура ветвленияреализует ветвящийся вычислительный процесс, то есть процесс, для реализации которого предусмотрено несколько направлений (ветвей). Ветвление в программе – это выбор одной из нескольких последовательностей операторов при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным данным или конечным результатам. Хотя на схеме алгоритма должны быть показаны все возможные направления вычислений в зависимости от выполнения определенного условия (или условий), при однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, по которой осуществляется вычисления, должна приводить к завершению вычислительного процесса.

В языках программирования структура ветвления реализуется условными и селективными констркуциями. Условные конструкции в общем случае имеют форму

если выражение то действие1 иначе действие2;

и следующей смысл: если выражение верно то выполняется действие1, иначе выполняется действие2.

Кроме того, используется и усеченная форма условной конструкции

если выражение то действие1;

На блок-схеме ветвление и усеченное ветвление изображаются следующим образом:

В С++ синтаксис условной конструкции

if (выражение) опрератор1; else оператор2;

if (выражение) опрератор1;

Выражение должно быть скалярным и иметь арифметический тип или тип указателя. В операторе if оператор1 выполняется в том случае, если выражение ненулевое, иначе выполняется оператор2 или не выполняются никакие действия, если оператор2 не задан, то есть отсутствует else. В частности, если a целое, то if (a) эквивалентно if (a!= 0).

Оператор1 и оператор2 могут представлять собой один оператор или блок операторов, но не могут быть описаниями.

if (a==b) printf(”Введенные значения равны”); else printf(”Введенные значения не равны”);

В соответствии неписаными правилами хорошего стиля программирования в условных инструкциях логическое выражение необходимо составлять таким образом, чтобы чаще всего оно было истинным.

scanf(“%d%d”,&a, &b);

if (a) {c=b/a; printf(“%d”,c);

else printf (”Ошибка ввода”);

Часто используются в условиях логические операции &&, ||, !. Операции && и || не будут вычислять второй аргумент, если это не нужно. Например, if (p && r) … вначале проверяет, является ли p не нулем, и только, если это так, то проверяет r.

Еслинекоторое действие выполняется при выполнении двух условий желательно записывать их в виде одного выражения.

Можно записать

if (a>0)

if (b>0) c=a*b;

но лучше if (a>0 && b>0) c=a*b;

Селективные инструкции используются для реализации мультиветвления и в общем случае имеют вид:

если (выражение)

{имеет значение1 то действие1,

имеет значение2 то действие2

….

имеет значениеn то действиеn

иначе действиеN+1

}

На блок-схеме мультиветление изображается следующим образом:

В С++ существует конструкция мультиветвления (переключатель). Синтаксис переключателя:

switch (переключающее_выражение)

{case константное_выражение1: оператор1;

case константное_выражение2: оператор2;

. . .

case константное_выражениеn: операторn;

default:оператор;

}

Если не предусмотрены переходы и выходы из переключателя, то в нем последовательно выполняются все операторы, начиная с той метки, на которую передано управление. Для выхода из переключателя обычно используют оператор break.