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

Доказана теорема о структурировании (Бем и Джекопини):

Как бы ни была сложна задача, схема алгоритма соответствующей программы всегда может быть представлена с использованием ограниченного набора базовых структур.

Примером одного из таких наборов базовых структур являются следующие три конструкции:

f THEN g - последовательность:

IF p THEN f ELSE g – выбор (ветвление):

WHILE p DO f – итерации (цикл с предусловием):

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

Наборов базовых структур может быть несколько. Например, если заменить последний элемент набора на

DO f WHILE p - итерации (цикл с постусловием):

то получится еще один набор из трех базовых структур. Эти наборы эквивалентны, т.к. от WHILE p DO f легко перейти к DO f WHILE p и наоборот:

Путем эквивалентных преобразований любую неструктурированную схему алгоритма можно привести к структурированному виду. Например:

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

Для более эффективной разработки программ современные языки программирования кроме минимального набора управляющих структур содержат и их модификации.

4.2. Управляющие структуры и инструкции языка C++

Управляющие структуры используются для управления ходом выполнения программы. В языке C++ имеются три категории управляющих инструкций:

· инструкции выбора (ветвления):

o if - условная инструкция;

o switch – инструкция множественного выбора;

· итерационные (циклические) инструкции:

o while – цикл с предусловием;

o do while - цикл с постусловием;

o for – итерационный цикл;

· инструкции перехода:

o break – прекращение выполнения циклических инструкций и инструкции switch;

o continue – переход к следующей итерации цикла;

o return – прекращение выполнения функции

o goto – переход по метке.

Условная инструкция (if)

Условная инструкция if позволяет выбрать одно из двух направлений выполнения программы.

Имеются две формы записи этой инструкции:

if (<Выражение>)

<Инструкция 1>;

else

<Инструкция 2>;

if (<Выражение>)

<Инструкция>;

Если под термином <Инструкция> понимаются несколько последовательных инструкций, то формат записи будет таким:

Блок инструкций представляет собой последовательность инструкций, каждая из которых заканчивается символом ;. Блок можно рассматривать как одну инструкцию (составную инструкцию).

Термин <Выражение> представляет собой любое выражение C++, значение которого может трактоваться как значение логического типа (bool).

Пример записи:

int K;

cin >> K;

if (K >= 0)

cout << “Вы ввели положительное число.” << endl;

else

cout << “Вы ввели отрицательное число.” << endl;

Здесь в качестве выражения использовано логическое выражение, значение которого равно true или false в зависимости от введенного с клавиатуры значения переменной K.

Еще один пример:

int K;

cin >> K;

if (K) // Здесь использовано арифметическое выражение

cout << “Вы ввели число не равное 0.” << endl;

else

cout << “Вы ввели 0.” << endl;

В этом примере выражение не является логическим, однако его значение может трактоваться как логическое (помним, что любое числовое значение, отличное от 0, соответствует значению true, а числовое значение 0 – логическому значению false). Этот пример можно было бы переписать так (эквивалент предыдущего примера):

int K;

cin >> K;

if (K != 0) // Здесь использовано логическое выражение

cout << “Вы ввели число не равное 0.” << endl;

else

cout << “Вы ввели 0.” << endl;

Способ записи выражения во втором (из последних двух) примере следует считать менее эффективным и с точки зрения написания текста, и с точки зрения использования ресурсов (расхода памяти и быстродействия).

А вот пример с использованием блока инструкций:

int Max, Min, B;

cin >> Max >> Min;

if (Min > Max)

{

B = Max;

Max = Min;

Min = B;

}

В этом примере используется “укороченная” (без ветви else) форма инструкции if, и в случае, когда переменная Min содержит значение большее, чем переменная Max, выполняется последовательность инструкций (блок), осуществляющих перераспределение значений этих переменных так, что переменная Max будет содержать большее значение, а переменная Min - меньшее.

Выполняемые внутри оператора if инструкции могут быть любыми инструкциями языка C++, в том числе и другими инструкциями if. То есть, другими словами, инструкции if могут вкладываться друг в друга. Количество уровней вложения if – инструкций в языке C++ ограничено 256 уровнями.

Рассмотрим несколько примеров вложений if - инструкций.

При анализе текстов подобных программ используют следующее правило:

Слово else относится к ближайшему сверху слову if, находящемуся в том же блоке инструкций, но еще не связанному ни с каким другим словом else.

Между словами if и else должна находиться хотя бы одна инструкция. Поэтому в первой реализации последнего примера мы вынуждены были использовать так называемую “пустую инструкцию”, которая не имеет никакого изображения и располагается между записью выражения (p) и разделителем ;. Вторая реализация этой схемы алгоритмы, основанная на инвертировании выражения p, является более корректной и эффективной.

В первой реализации последнего примера мы также использовали “пустую инструкцию”, так как после слова else (как и после слова if) также должна находиться хотя бы одна инструкция или блок инструкций. Если в первой реализации не записать слово else и пустую инструкцию вложенной инструкции if, а во второй реализации не оформить эту вложенную инструкцию if в виде блока, то будет реализована схема совершенно другого алгоритма:

В программах очень часто используется многоуровневое вложение if – инструкции так называемой “лесенкой”, схема алгоритма которой выглядит так:

Подобные схемы можно использовать для множественного выбора, однако для реализации такой схемы более подходит инструкция, рассмотренная в следующем параграфе.

Инструкция множественного выбора (switch)

Эта инструкция служит для ветвления программы во многих направлениях.

Ее синтаксис:

switch (<Выражение>)

{

case <Константа 1>:

<Последовательность инструкций 1>

break;

case <Константа 2>:

<Последовательность инструкций 2>

break;

……….

case <Константа N>:

<Последовательность инструкций N>

break;

default:

<Последовательность инструкций>

}

При совпадении значения выражения со значением одной из констант 1 – N будет выполнена соответствующая этой ветви последовательность инструкций. Инструкция break осуществляет прерывание выполнения инструкции switch и управление передается следующему за switch-инструкцией оператору. Если значение выражения не совпадет ни с одной из констант, то будут выполнены инструкции ветви default.

Ветвь default не обязательна. В случае отсутствия ветви default при несовпадении значения выражения ни с одной из констант не будет выполнена ни одна из инструкций оператора switch.

Значение выражения в инструкции switch обязательно должно быть либо целого, либо символьного типа (в принципе тип выражения может быть и логическим, но в этом случае выгоднее пользоваться if-инструкцией) – вещественные значения не допускаются.

Пример записи инструкции:

unsigned i;

cin >> i;

switch ( i )

{

case 0:

cout << "ноль\n";

break;

case 1:

cout << "один\n ";

break;

case 2:

cout << "два\n ";

break;

default:

cout << "много\n ";

}

Если в выбранной ветви будет отсутствовать инструкция break, то после выполнения инструкций этой ветви начнут выполняться инструкции следующей ветви до тех пор, пока не встретится инструкция break или не будет достигнут конец оператора switch. Например:

unsigned i;

cin >> i;

switch ( i )

{

case 0: cout << 0;

case 1: cout << 1;

case 2: cout << 2;

case 3: cout << 3;

case 4: cout << 4;

case 5: cout << 5;

}

В этом примере на экран будет выведена последовательность цифр, начинающаяся с цифры, введенной с клавиатуры.

Инструкция switch более эффективна, чем структура “лесенка”, реализованная с помощью вложенных инструкций if.

Цикл с предусловием (while)

Формат записи этой инструкции:

Или, если тело цикла представляет собой одиночную инструкцию:

И тому и другому варианту соответствует следующая схема алгоритма:

Выражение в этой инструкции может быть любого типа, значения которого можно трактовать как значения логического типа данных (bool). Это выражение определяет условие продолжения выполнения тела цикла, то есть, если значение этого выражения истинно (true или не равно 0), то тело цикла выполняется вновь, если же ложно (false или 0) , то цикл заканчивается и управление передается следующей за циклом инструкции.

Очевидно, что тело цикла в этой инструкции может не выполниться ни разу, если при входе в цикл значение выражения будет соответствовать значению false или 0.

Для того чтобы цикл начал выполняться, необходимо перед началом цикла выполнить инициализацию его параметров так, чтобы значение выражения соответствовало значению true или было не равно 0.

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

Рассмотрим некоторые примеры.

Пример 1. Необходимо в виде строки вывести на экран цифры от 0 до 9.

int k = 0; // На экран выведено k цифр

while (k <= 9) // Здесь используется логическое выражение

{

cout << k;

++k;

}

// На экран выведено k = 10 цифр: 0123456789

Формулировка условия продолжения цикла в этом примере может быть и другой:

k < 10 или k != 9

Поскольку на каждом шаге цикла параметр цикла k увеличивает свое значение на 1 (начиная с 0), то после выполнения 10 шагов условие выполнения цикла (при любой формулировке из перечисленных) обязательно перестанет выполняться и цикл закончится.

Но вот, если в теле цикла не предусмотреть наращивание параметра k, то получим бесконечный цикл, в котором на экран будут выводиться одни нули:

int k = 0;

while (k <= 9)

{

cout << k;

}

Для остановки его нам придется принудительно прервать выполнение программы.

Причиной зацикливания может быть и неправильная формулировка условия продолжения цикла.

Пример 2. Необходимо в виде строки вывести на экран только нечетные числа из первого десятка.

int k = 1;

while (k != 10)

{

cout << k << “\t”;

k += 2;

}

В этом примере выражение k != 10 никогда не станет ложным, так как параметр цикла k при его увеличении на каждом шаге цикла на 2 будет иметь только нечетные значения. Правильной формулировкой условия является, например, такая: k < 10.

Пример 3. Для принудительного (досрочного) прекращения цикла можно использовать инструкцию break. Например:

while (<Выражение>)

{

<Инструкция 1>;

if (<Ошибка>)

break;

<Инструкция 2>;

}

<Инструкция 3>;

Если при выполнении <Инструкции 1> возникает ошибка (о чем свидетельствует значение true выражения <Ошибка>), после которой выполнение цикла должно быть прекращено, выполняется инструкция break. При выполнении инструкции break цикл прекращается (<Инструкция 2> выполнена не будет), и управление передается <Инструкции 3>, следующей за оператором цикла.

Пример 4. Если в предыдущем примере при возникновении ошибки требуется только пропустить выполнение <Инструкции 2), а затем продолжить выполнение цикла, следует использовать инструкцию continue:

while (<Выражение>)

{

<Инструкция 1>;

if (<Ошибка>)

continue;

<Инструкция 2>;

}

При выполнении инструкции continue <Инструкция 2> выполнена не будет, но цикл перейдет к выполнению следующей итерации (шага).

Инструкция continue на практике используется достаточно редко, так как обойтись без нее очень просто:

while (<Выражение>)

{

<Инструкция 1>;

if (!<Ошибка>)

{

<Инструкция 2>;

}

}

Надо только не забыть инвертировать выражение <Ошибка>.

Цикл с постусловием (do while)

Формат записи этой инструкции:

Или, если тело цикла представляет собой одиночную инструкцию:

И тому и другому варианту соответствует следующая схема алгоритма:

Так же, как и в предыдущем цикле, выражение в этой инструкции может быть любого типа, значения которого можно трактовать как значения логического типа данных (bool). Это выражение определяет условие продолжения выполнения тела цикла, то есть, если значение этого выражения истинно (true или не равно 0), то тело цикла выполняется вновь, если же ложно (false или 0), то цикл заканчивается и управление передается следующей за циклом инструкции.

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

Использование этого цикла проиллюстрировано следующим примером:

Пример 1. Необходимо в виде строки вывести на экран цифры от 0 до 9.

int k = 0; // На экран выведено k цифр

do

{

cout << k;

++k;

}

while (k <= 9); // Здесь используется логическое выражение

// На экран выведено k = 10 цифр: 0123456789

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

Итерационный цикл (for)

Формат записи этой инструкции:

Или, если тело цикла представляет собой одиночную инструкцию:

И тому и другому варианту соответствует следующая схема алгоритма:

При запуске цикла однократно выполняется Инициализация параметра (параметров) цикла, после чего осуществляется проверка Условия, определяющего необходимость выполнения тела цикла. После окончания выполнения инструкций тела цикла, на каждой итерации выполняется Модификация параметра (параметров) цикла и снова проверяется Условие. Так продолжается до тех пор, пока Условие не станет ложным (false).

Разделы Инициализации, Условия и Модификации в заголовке цикла разделяются символом ‘;’.

Пример записи (пример из предыдущего параграфа):

int k;

for (k = 0; k <= 9; ++k)

cout << k;

Если параметр k цикла используется только внутри цикла (после выхода из цикла переменная k больше не нужна), эту переменную можно (и лучше) определить непосредственно в разделе Инициализации цикла:

for (int k = 0; k <= 9; ++k)

cout << k;

В разделах Инициализации и Модификации можно управлять сразу несколькими параметрами цикла:

for (int k = 1, n = 10; k <= 10; ++k, --n)

cout << k << “ * ” << n << “ = ” << k * n << endl;

На экран будет выведено:

1 * 10 = 10

2 * 9 = 18

3 * 8 = 24

4 * 7 = 28

5 * 6 = 30

6 * 5 = 30

7 * 4 = 28

8 * 3 = 24

9 * 2 = 18

10 * 1 = 10

Отдельные элементы разделов Инициализации и Модификации отделяются друг от друга символом ‘,’.

Любой раздел заголовка цикла может отсутствовать. Раздел Инициализации, например, может отсутствовать, когда начальные значения параметров цикла устанавливаются вне цикла, перед его началом. Модификация значений параметров цикла может осуществляться внутри тела цикла, а не в его заголовке. При отсутствии Условия продолжения выполнения цикла, цикл становится бесконечным и для выхода из него придется использовать инструкцию break. Однако, какой бы из разделов ни отсутствовал, соответствующие разделительные символы ‘;’ в заголовке цикла должны обязательно присутствовать:

#include <conio.h>

……..

cout << “Для продолжения работы нажмите любую клавишу…” << endl;

for ( ; ! kbhit(); );

……..

В этом примере цикл, в заголовке которого отсутствуют разделы Инициализации и Модификации, используется для приостановки выполнения программы до нажатия на клавиатуре любой клавиши (функция kbhit() возвращает значение false, если на клавиатуре не нажата никакая клавиша, и значение true, если клавиша была нажата – для использования этой функции необходимо включить заголовочный файл conio.h).

Замечание. Приостановку работы программы значительно проще (без использования циклов) можно выполнить с помощью функции getch(), которая ожидает нажатия клавиши на клавиатуре и возвращает символ этой клавиши без отображения этого символа на экране (необходим заголовочный файл conio.h):

#include <conio.h>

……..

cout << “Для продолжения работы нажмите любую клавишу…” << endl;

getch();

……..

Принудительный выход из цикла for осуществляется с помощью инструкции break, а принудительный переход к следующей итерации (шагу цикла) – с помощью инструкции continue.

Тела циклов могут содержать любые инструкции языка C++, в том числе и другие циклы. Подобные конструкции называются вложенными циклами. Использование вложенных циклов является весьма распространенным приемом программирования при решении очень многих задач.

Инструкции перехода

Использование инструкций break и continue было рассмотрено при изучении инструкции switch и циклических операторов. По поводу инструкции break следует напомнить, что при вложенных циклах она обеспечивает прекращение того цикла, в теле которого она непосредственно расположена.

Инструкция return, служащая для завершения выполнения функций и для возвращения из функций некоторых значений, будет подробно рассмотрена позже, при изучении функций.

В этом параграфе остается рассмотреть инструкцию безусловного перехода goto.

Характеризуя инструкции break (ее использование в циклах), continue и goto в целом, следует сказать, что их применение противоречит принципам структурного программирования и приводит к затруднению понимания алгоритмов программ, их отладки и дальнейшей модификации. Однако, несмотря на это, их использование в ряде случаев бывает оправдано. В принципе, как бы ни был сложен алгоритм программы, его всегда можно реализовать без использования этих инструкций. В основном это достигается за счет введения дополнительных логических переменных (флажков) и некоторого усложнения условий продолжения циклов. Однако в некоторых случаях эти “накладные расходы” оказываются чрезмерными и тогда выгоднее все-таки использовать эти инструкции перехода. Как поступать в тех или иных ситуациях во многом зависит от конкретного алгоритма и от внутренних предпочтений программиста. Но, все же, злоупотреблять использованием этих инструкций не следует.

Инструкция goto обеспечивает переход на выполнение инструкции отмеченной с помощью метки.

Формат записи: goto <Метка>;

Метка представляет собой некоторый идентификатор, за которым следует символ’:’. Меткой может быть помечена любая инструкция, находящаяся в той же функции, в которой находится оператор goto.

Пример использования:

…….

M1: <Инструкция>;

…….

if (<Условие>)

goto M1;

…….

Наиболее часто обоснованное использование инструкции goto связано с выходом из глубоко вложенных циклов:

Использование в этом случае инструкции break вместо оператора goto привело бы к прерыванию только внутреннего цикла. Для прерывания выполнения всех циклов с помощью инструкции break потребовались бы существенные усилия.

5. Приемы программирования циклов

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

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

Существует много различных типовых схем вычислений, основанных на использовании циклов. Одной из них является схема рекуррентных вычислений.

5.1. Рекуррентные вычисления

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

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

Пусть в некоторой последовательности известны первые n значений:

Тогда элемент при определяется так:

Или, иными словами:

Простейшим примером рекуррентного соотношения является вычисление факториала числа:

Программная реализация вычисления факториала:

unsigned Factorial (unsigned n)

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; // Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

F *= i; // F = F * i - текущее значение i!

}

return F; // Возвращаем значение n!

}

Недостатком этой реализации является то, что с помощью этой функции можно вычислить n! только для n от 0 до 12. Значение 13! уже выходит за верхнюю границу диапазона значений типа unsigned и функция начинает возвращать неверные значения факториала. Для предотвращения получения неверных значений факториалов модифицируем функцию следующим образом:

unsigned Factorial (unsigned n)

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; // Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

if (0xffffffffu / i < F ) // 0xffffffffu – максимальное значение типа unsigned

{

F = 0;

break;

}

F *= i; // F = F * i - текущее значение i!

}

return F; // Возвращаем значение n!

}

Добавленная проверка обнаруживает ситуацию, когда умножение предыдущего значения факториала на следующее значение i приведет к выходу полученного значения произведения за верхнюю границу диапазона значений типа unsigned. В этом случае значению факториала присваивается значение 0 (факториал любого числа всегда больше 0), и с помощью инструкции break выполнение цикла прерывается. В этом случае функция вернет значение 0.

При такой реализации функцию Factorial в программе можно использовать, например, так:

unsigned F, n;

…..

if (F = Factorial (n))

….. // Используем вычисленное значение факториала F

else

cout << “Ошибка. Факториал числа ” << n << “ не может быть вычислен! \n”;

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

Еще один пример. Требуется подсчитать сумму первых n элементов следующего степенного ряда:

Если подойти к решению этой задачи “в лоб”, то получится следующая весьма неэффективная программа:

int n = 20; // Количество суммируемых элементов ряда

double x = 2.5; // Значение аргумента x

double S = 0; // Начальное значение суммы ряда

int i = 0; // Начальное значение индекса элемента ряда

while (i < n)

{

S = S + pow(x, i) / Factorial (i);

++ i;

}

cout << “Сумма первых ” << i << “ элементов ряда равна ” << S << endl;

Неэффективность этого варианта реализации объясняется двумя причинами. Во-первых, поскольку функция вычисления факториала представляет собой цикл, общее количество операций будет быстро расти с увеличением n. Во-вторых, нам вообще не удастся подсчитать сумму более чем 13 элементов этого ряда, так как при i = 13, функция вычисления факториала возвратит значение 0, и наша программа аварийно завершится с ошибкой “Деление на 0”. Избежать аварийного завершения программы можно, как это было описано выше – путем проверки значения факториала на 0 и прерывания цикла, однако более 13 элементов ряда все равно просуммировать не удастся.

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

Несложно заметить, что откуда следует, что при .

Тогда можно предложить следующий вариант реализации:

int n = 20; // Количество суммируемых элементов ряда

double x = 2.5; // Значение аргумента x

double a = 1; // Значение первого элемента ряда

double S = 1; // Начальное значение суммы ряда при i = 0

int i = 1; // Начальное значение индекса элемента ряда

while (i < n)

{

a = a * x / i ;

S = S + a;

++ i;

}

cout << “Сумма первых ” << i << “ элементов ряда равна ” << S << endl;

В этой реализации недостатки предыдущего варианта программы отсутствуют. Удалось избавиться и от вычисления факториала, и от возведения в степень аргумента x. Теперь количество операций на каждой итерации постоянно и равно 4. Программа позволяет находить сумму практически любого количества элементов ряда.

Более сложный вариант рекуррентного соотношения. Требуется написать функцию для получения значения многочлена Чебышева первого рода степени n >= 0 , задающегося следующим рекуррентным соотношением:

Реализация:

double Cheb_1 (double x, int n)

{

double Tn, Tn_1 = x, Tn_2 = 1;

switch (n)

{

case 0: return Tn_2;

case 1: return Tn_1;

default:

int i = 2;

while (i < = n)

{

Tn = 2 * x * Tn_1 - Tn_2;

Tn_2 = Tn_1;

Tn_1 = Tn;

++ i;

}

return Tn;

}

}

При выполнении рекуррентных вычислений с вещественными значениями беспокоиться о переполнении значений вещественного диапазона приходится очень редко (особенно при использовании типа double). Но и здесь встречаются некоторые “подводные камни”.

Предостережение № 1. При определении условия продолжения цикла никогда не используйте проверку на точное равенство вещественных значений с помощью операции == (впрочем, и в других условиях тоже). Например:

double a = 1.1, b = 0;

while ( ! (b == a) )

{

b = b + 0.1;

}

Такой цикл никогда не закончится, так как из-за погрешностей вычислений и представления вещественных значений точного равенства a и b при выбранных значениях никогда не будет (так, по крайней мере, происходит для этого примера в MS Visual C++ 2010). Лучше сделать так:

double a = 1.11, b = 0;

while ( b <= a )

{

b = b + 0.1;

}

Здесь цикл закончится гарантированно, и последнее значение b будет очень близко к 1.1.

Предостережение № 2. Остерегайтесь складывать (вычитать) очень большие и относительно малые вещественные значения. Например:

double a = 1e20, b = a, d = 1000;

int i = 1;

for ( int i = 1; i <= 1000000; ++ i)

{

b = b + d;

}

cout << b – a << endl;

Ожидается, что значение b после окончания цикла будет больше a на 1 000 000 000, однако разность между b и a оказывается равной 0. Это происходит, потому что величина d = 1 000 по отношению к значению a = 1e20 оказывается пренебрежимо малой из-за дискретности представления вещественных значений.

Если увеличить значение d и сделать его равным 10 000, то разность b – a окажется равной приблизительно 1.64e10, а не 1e10 как это следует из арифметики – достаточно грубая ошибка.

Для того, чтобы избавиться от этой неприятности, можно поступить так:

double a = 1e20, b = a, d = 1000, s = 0;

int i = 1;

for ( int i = 1; i <= 1000000; ++ i)

{

s = s + d;

}

b = b + s;

cout << b – a << endl;

Вот теперь мы увидим то, что ожидалось (или очень близкое к тому) и в первом и во втором случаях. Здесь мы сначала накопили отдельно сумму s относительно малых величин d, а затем уже относительно большое значение s добавили к b.

5.2. Инвариант цикла

Инвариантом называется логическое выражение, истинное перед началом выполнения цикла и после каждого прохода тела цикла, зависящее от переменных, изменяющихся в теле цикла.

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

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

1. Доказывается, что выражение инварианта истинно перед началом цикла сразу после инициализации параметров цикла.
2. Доказывается, что выражение инварианта сохраняет свою истинность до и после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении цикла инвариант будет выполняться.
3. Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
4. Доказывается, что цикл завершится, то есть условие завершения рано или поздно будет выполнено.
5. Истинность утверждений, доказанных на предыдущих этапах, однозначно свидетельствует о том, что цикл выполнится за конечное время и даст желаемый результат.

Инварианты используют не только для доказательства корректности циклов, но и при проектировании и оптимизации циклических алгоритмов.

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

Постановка задачи. Требуется найти наибольший общий делитель d двух целых чисел n и m: d = НОД(n, m).

Сформулируем инвариант цикла для нахождения НОД(n, m) следующим образом: пусть имеется пара чисел a и b таких, что НОД(a, b) = НОД(n, m). На каждом шаге цикла будем переходить к другой паре чисел a и b таких, что НОД(a, b) = НОД(n, m). И так будем продолжать до тех пор, пока значение НОД не станет очевидным. Таким образом, инвариант цикла сформулируем так: НОД(a, b) = НОД(n, m). Теперь стоит задача: как найти очередную пару чисел a и b, при которых значение инварианта не изменится.

Из математики (теория чисел) известно, что если d = НОД(n, m), то это же значение d является и НОД(m, r), где r – остаток от деления n на m, то есть НОД(n, m) = НОД(m, r).

Например: НОД(126, 12) = НОД(12, 6) = НОД(6, 0) = 6

Алгоритм решения задачи можно представить так:

1. Начальная инициализация: пусть a = n, b = m. Очевидно, что НОД(a, b) = НОД(n, m).

2. Находим r и делаем a = b и b = r. При этом выражение НОД(a, b) = НОД(n, m) остается справедливым.

3. Как только b станет равно 0, тогда НОД(a, 0) = НОД(n, m) = a.

Программа, реализующая этот алгоритм:

int r, a = n, b = m;

// Инвариант: НОД(a, b) = НОД(n, m)

// Цикл заканчивается при b = 0, тогда НОД(a, 0) = a

while (b)

{

// Инвариант: НОД(a, b) = НОД(n, m) выполняется

r = a % b;

a = b;

b = r;

// Инвариант: НОД(a, b) = НОД(n, m) выполняется

}

// Инвариант: НОД(a, b) = НОД(n, m) выполняется

cout << “НОД (“ << n << “, ” << m << “) = ” << a << endl;

Можно предложить еще один алгоритм решения этой задачи, основанный на том же инварианте, но использующий другой способ нахождения следующей пары a и b: известно, что НОД(n, m) = НОД(n - m, m) при n > m и НОД(n, m) = НОД(n, m - n) при m > n. Например: НОД(126, 12) = НОД(114, 12) = НОД(102, 12) = … = НОД(18, 12) = НОД(6, 12) = НОД(6, 6) = 6. Но этот алгоритм является более затратным по сравнению с предыдущим.

Еще одним наглядным примером использования инварианта для проектирования цикла является реализация быстрого возведения чисел в целую положительную степень. Пример его реализации приведен в Приложении. Предлагается разобрать его самостоятельно.

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

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

6. Массивы и указатели

Массивы. Индексирование. Объявление массивов. Двумерные и многомерные массивы. Ввод-вывод массивов. Строки и тексты как массивы символов. Массивы и указатели. Арифметика указателей. Правила сложных объявлений. Использование функций при работе с массивами. Управление памятью.

6.1. Понятие массива

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

Аналогом одномерного массива из математики может служить последовательность некоторых элементов с одним индексом: при i = 0, 1, 2, … n – одномерный вектор. Каждый элемент такой последовательности представляет собой некоторое значение определенного типа данных. Наглядно одномерный массив можно представить как набор пронумерованных ячеек, в каждой из которых содержится определенное значение:

Это пример одномерного массива из 6 элементов, каждый из которых представляет собой некоторое вещественное значение и каждое из этих значений имеет индекс от 0 до 5.

А вот пример одномерного массива из десяти элементов, представляющих собой одиночные символы:

Каждый элемент в этих массивах определяется значением индекса элемента. Например, в последнем массиве элемент с индексом 5 равен символу ‘2’.

Двумерный массив – это последовательность некоторых элементов с двумя индексами: при i = 0, 1, 2, … n и j = 0, 1, 2, … m – двумерная матрица. Например, при n = 3 и m = 4:

Эта матрица из 3-х строк и 4-х столбцов содержит 3 * 4 = 12 целых значений. Здесь уже каждый элемент определяется значениями двух индексов. Например, элемент с индексом i = 2 и индексом j = 1 равен целому значению 15.

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

6.2. Объявление массивов

Объявление одномерных массивов

Объявление в программах одномерных массивов выполняется в соответствии со следующим правилом:

<Базовый тип элементов> <Идентификатор массива> [<Количество элементов>]

Например:

int ArrInt [10], A1 [20];

double D [100];

char Chars [50];

bool B [200];

Значения индексов элементов массивов всегда начинается с 0. Поэтому максимальное значение индекса элемента в массиве всегда на единицу меньше количества элементов в массиве.

Обращение к определенному элементу массива осуществляется с помощью указания значения индекса этого элемента:

A1 [8] = -2000;

cout << A1[8]; // На экран выведено -2000

В этом примере, обратившись к элементу массива A1 с индексом 8, мы, фактически, обратились к его 9-му элементу.

При обращении к конкретному элементу массива этот элемент можно рассматривать как обычную переменную, тип которой соответствует базовому типу элементов массива, и осуществлять со значением этого элемента любые операции, которые характерны для базового типа. Например, поскольку базовым типом массива A1 является тип данных int, с любым элементом этого массива можно выполнять любые операции, которые можно выполнять над значениями типа int.

При объявлении массива его можно инициализировать определенными значениями:

short S[5] = {1, 4, 9, 16, 25}

Эта инициализация будет эквивалентна следующим операциям присваивания:

S[0] = 1;

S[1] = 4;

S[2] = 9;

S[3] = 16;

S[4] = 25;

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

Значения всех элементов массива в памяти располагаются в непрерывной области одно за другим. Общий объем памяти, выделяемый компилятором для массива, определяется как произведение объема одного элемента массива на количество элементов в массиве и равно:

sizeof( <Базовый тип> ) * <Количество элементов>

Для предыдущего примера объем массива S будет равен sizeof( short) * 5 = 2 * 5 = 10 байтам.

Поскольку все элементы массивов располагаются в памяти один за другим без разрывов, обращение к элементам массива по их индексам (какой бы длины не был этот массив) осуществляется очень эффективно путем вычисления адреса нужного элемента. Пусть, например, адрес памяти, где начинается массив S, равен 100, тогда адрес элемента этого массива с индексом 3 будет равен 100 + sizeof( short) * 3 = 100 + 2 * 3 = 106. Обращаемся по этому адресу и считываем 2 байта. Это и будет значением элемента с индексом 3 массива S.

В языке C++ не осуществляется проверка выхода за границы массивов. То есть, вполне корректно (с точки зрения компилятора) будет обращение к элементу массива S, индекс которого равен 10. Это может привести к возникновению весьма серьезных отрицательных последствий. Например, если выполнить присвоение S[10] = 1000 будут изменены данные, находящиеся за пределами массива, а это может быть значение какой-нибудь другой переменной программы. После этого предсказать поведение программы будет невозможно. Единственный выход – быть предельно внимательным при работе с индексами элементов массивов.

Объявление многомерных массивов

Многомерные массивы определяются аналогично одномерным массивам. Количество элементов по каждому измерению указывается отдельно в квадратных скобках:

int A1 [5] [3]; // Двумерный массив, элементами которого являются

// значения типа int

double D [10] [15] [3]; // Трехмерный массив, элементами которого являются

// значения типа double

Здесь массив A1 представляет собой обычную двумерную матрицу из 5-ти строк и 3–х столбцов.

Массив D – трехмерный массив, который можно представить как трехмерный параллелограмм, навранный из 3-х двумерных матриц.

Общее число элементов в многомерном массиве определяется как произведение количества элементов по каждому измерению. Так, например, массив D содержит 10 * 15 * 3 = 450 элементов типа double, а объем памяти, требующийся для этого массива, будет равен 450 * 4 = 1800 байтам.

Массивы с большим, чем 3, количеством измерений используются достаточно редко. Одной из причин этого является быстрый рост объема памяти, необходимой для размещения таких массивов.

В следующей таблице показана схема размещения элементов массива A1 в памяти:

Так же как и в одномерном массиве, элементы многомерных массивов располагаются друг за другом в непрерывном участке памяти.

При определении многомерные массивы могут инициализироваться определенными значениями. Для получения массива A1 с теми значениями элементов, которые приведены в таблице, можно инициализировать массив следующим образом:

int A1 [5] [3] =

{

1, 1, 1,

2, 4, 8,

3, 9, 27,

4, 16, 64,

5, 25, 125

};

Для доступа к определенному элементу многомерного массива необходимо указать в квадратных скобках конкретные значения всех индексов этого элемента. Например:

cout << A1 [1] [2]; // На экран выведено значение 8

6.3. Ввод-вывод массивов

Ранее были рассмотрены приемы ввода-вывода простых предопределенных типов данных (int, double, char и bool) с помощью потоков ввода и вывода. Стандартные потоки ввода и вывода не “умеют” работать с массивами, поэтому ввод и вывод массивов необходимо реализовывать самостоятельно, обрабатывая массивы поэлементно.

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

Начнем с рассмотрения операций вывода значений элементов массивов на экран.

Простейший циклический алгоритм вывода значений элементов некоторого одномерного массива выглядит так:

const int n = 10;

short A[n];

…

// Для использования setw() необходимо включить #include <iomanip>

for (int i = 0; i < n; ++i)

cout << setw(8) << left << A[i];

cout << endl;

На каждом шаге этого цикла в поток вывода отправляется очередной i-й элемент массива, при этом устанавливается ширина поля вывода, равная 8 позициям, выравнивание по левому краю. После окончания цикла вывода всех n элементов массива осуществляется переход на следующую строку экрана.

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

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

const int n = 10, m = 10;

short A [n] [m];

…

for (int i = 0; i < n; ++i)

// Выводим i-ю строку массива

{

for (int j = 0; j < m; ++j)

// Выводим j-й элемент i-й строки массива

cout << setw(7) << right << A [i] [j];

cout << endl;

}

Здесь используются вложенные циклы. Обратите внимание, что внутренний (вложенный) цикл практически идентичен циклу, реализующему вывод элементов одномерного массива.

6.4. Текстовые строки как массивы символов

6.5. Массивы и указатели

7. Разработка программ при работе с массивами

Картинки массивов при записи предусловий, постусловий и инвариантов. Примеры: задачи разделения и слияния массивов, перестановка сегментов массива (циклический сдвиг) и т.п. Линейный и бинарный поиск в массиве. Оптимальность алгоритмов поиска. Оптимизация программ. Простые алгоритмы сортировки (выбором, вставками, обменами). Работа с двумерными и многомерными массивами.

8. Функции и структура программы

Создание и использование функций. Вызов функции (аргументы функции) и возврат значения. Передача параметров по значению, по ссылке. Глобальные и локальные переменные. Классы памяти и область действия. Автоматические переменные. Внешние переменные. Статические переменные. Внешние статические переменные. Регистровые переменные. Указатели. Функции с переменным количеством аргументов. Представление программы в виде набора функций. Многофайловая структура программы. Использование функции как параметра другой функции; пример применения - итерационные методы решения нелинейных уравнений.

9. Организация ввода/вывода и работа с файлами

Последовательность (как модель файла) и файл. Потоки и работа с файлами. Базовые операции с файлами. Типовые действия с файлами: генерация, чтение, копирование. Форматирование ввода и вывода. Схема однопроходных алгоритмов обработки файлов (вычисление функций на последовательностях). Примеры.

Заключение

Основные тенденции и направления развития методов и языков программирования. Связь с учебной дисциплиной по программированию (дополнительные главы) следующего семестра.

Приложение. Некоторые полезные примеры и иллюстрации к разделам конспекта

Все программы, приведенные в этом разделе, реализованы в среде MS Visual C++ 2010.

Примеры к разделу 5

Вычисление факториала числа

// Факториал.cpp: определяет точку входа для консольного приложения.

// Различные реализации функций для вычисления факториала числа

#include "stdafx.h"

#include <iostream>

#include <iomanip> // для манипулятора setw()

#include <limits.h> // для ULONG_MAX - максимальное значение типа unsigned long

using namespace std;

unsigned Factorial_Err(unsigned n)

// При n > 12 значение n! превышает максимальное значение ULONG_MAX типа unsigned

// и функция возвращает неправильные значения

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; // Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

F *= i; // F = F * i - Текущее значение i!

}

return F; // Возвращаем значение n!

}

unsigned Factorial(unsigned n)

// При переполнении возвращает 0 с сообщением об ошибке

// Реализация с помощью цикла while

{

unsigned i = 0; // Текущее значение i

unsigned F = 1; // Текущее значение i!

while (i < n)

{

++ i; // i = i + 1

if (ULONG_MAX / i < F)

{

F = 0;

cout << "Ошибка. При вычислении n! максимальное "

"значение n не может превышать " << --i << endl;

break;

}

F *= i; // F = F * i - Текущее значение i!

}

return F; // Возвращаем значение n!

}

unsigned Factorial_1(unsigned n)

// При переполнении возвращает 0 с сообщением об ошибке

// Реализация с помощью цикла for

{

unsigned F = 1; // Значение 0!

for (unsigned i = 1; i < n; ++i, F *= i)

if (ULONG_MAX / i < F)

{

F = 0;

cout << "Ошибка. При вычислении n! максимальное "

"значение n не может превышать " << --i << endl;

break;

}

return F; // Возвращаем значение n!

}

unsigned Factorial_2(unsigned n)

// При переполнении возвращает 0 без сообщения об ошибке

// Реализация с помощью цикла for

{

unsigned F = 1; // Значение 0!

for (unsigned i = 1; (i < n) && F; ++i, F = (ULONG_MAX / i < F) ? 0 : F * i);

return F; // Возвращаем значение n!

}

int main()

// Для проверки работы одного из вариантов необходимо

// снять комментарии с соответствующей строки цикла for

// и закомментировать остальные

{

for (int i = 0; i <= 13; ++ i)

{

cout << setw(2) << right << i << "! = " << Factorial_Err(i) << endl;

// cout << setw(2) << right << i << "! = " << Factorial(i) << endl;

// cout << setw(2) << right << i << "! = " << Factorial_1(i) << endl;

// cout << setw(2) << right << i << "! = " << Factorial_2(i) << endl;

}

system ("Pause");

return 0;

}

Быстрое возведение чисел в целую степень

// ЦелаяСтепень.cpp: определяет точку входа для консольного приложения.

//

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

double IntPow(double b, int k, int &Count)

{

// Инвариант: (b ^ k) * p = a ^ n

// Цикл заканчивается при k = 0, тогда p = a ^ n

double p = 1;

Count = 0;

while (k != 0)

{

if (k & 1) // k не четно

{

-- k; // k = k - 1

p *= b; // p = p * b

}

else

{

k /= 2; // k = k / 2

b *= b; // b = b * b

}

++ Count;

}

return p;

}

double IntPow1(double a, int n, int &Count)

{

double p = 1;

double b = a;

for (int i = n, Count = 0; i; (i % 2) ? (p *= b, --i) : (b *= b, i /= 2),

++ Count);

return p;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(0, "");

cout << " Алгоритм быстрого возведения числа в целую степень.\n";

cout << " ---------------------------------------------------\n";

for (char b = '1'; b != 27; cout << "\n\t\t\tПродолжим? (нет - Esc) ",

b = _getch(), cout << endl)

{

double a;

int n, N;

cout << "\nОснование степени: ";

cin >> a;

cout << "Целая степень: ";

cin >> n;

cout << '\n' << a << " в степени " << n << " равно " << fixed

<< IntPow(a, n, N) << ".\n";

cout << "Количество шагов: " << N << endl;

cout << '\n' << a << " в степени " << n << " равно " << fixed

<< IntPow1(a, n, N) << ".\n";

cout << "Количество шагов: " << N << endl;

}

return 0;

}

Нахождение наибольшего общего делителя (алгоритм Евклида)

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

int NOD_1(int n, int m, int &Count)

// Известно, что: НОД(n, m) = НОД(n - m, m) при n > m и

// НОД(n, m) = НОД(n, m - n) при n < m.

{

int r, a = n, b = m;

Count = 0;

// Инвариант: НОД(a, b) = НОД(n, m)

// Цикл заканчивается при a = b, тогда НОД(n, m) = НОД(a, a) = a

while (a != b)

{

if (a > b)

a = a - b;

else

b = b - a;

++ Count;

}

return a;

}

int NOD_2(int n, int m, int &Count)

// Известно, что: НОД(n, m) = НОД(m, r), где r - остаток от деления n на m.

{

int r, a = n, b = m;

Count = 0;

// Инвариант: НОД(a, b) = НОД(n, m)

// Цикл заканчивается при b = 0, тогда НОД(n, m) = НОД(a, 0) = a

while (b)

{

r = a % b;

a = b;

b = r;

++ Count;

}

return a;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(0, "");

cout << " Алгоритм Евклида для нахождения наибольшего общего делителя.\n";

cout << " ------------------------------------------------------------\n";

for (char b = '1'; b != 27; cout << "\n\t\t\tПродолжим? (нет - Esc) ",

b = _getch(), cout << endl)

{

int Count;

int n, m;

cout << "\n Введите два целых числа больших 0: ";

cin >> n >> m;

cout << "\n Значение НОД чисел " << n << " и " << m << " равно "

<< NOD_1 (n, m, Count) << endl;

cout << "Число итераций: " << Count << endl;

cout << "\n Значение НОД чисел " << n << " и " << m << " равно "

<< NOD_2 (n, m, Count) << endl;

cout << "Число итераций: " << Count << endl;

}

return 0;

}