Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Построение алгоритмов вычислительных процессов).pdf

Считается, что цикл forявляется самым легким для понимания, поскольку все элементы, контролирующие его выполнение, собраны в одном месте. Цикл for организовывает выполнение фрагмента программы фиксированное количество раз. Синтаксис оператора for изображен на рис 2.1.

Рисунок 2.1. – Синтаксис оператора for

Использование оператора forрассмотрим на примере вывода на экран дисплея в ряд чисел от 1 до 10. Алгоритм решения изображен на рисунке 2.2, а приведенная на рис 2.3. программа демонстрирует применение оператора for.

Рисунок 2.2. – Схема применения оператора for

Рисунок 2.3. Код программы

В рядке 4 программы записан оператор цикла for. Цикл forначинается с ключевого слова for, набранного маленькими буквами, за которым стоит три аргумента в скобках. Каждый аргумент отделен точкой с запятой. Аргументами для for соответственно являются инициализация, завершение и прирост. Они определяют длительность рабочего цикла. Первый аргумент объявляет переменную chislo как переменную целого типа и присваивает ей значение 1:

for (intchislo = 1; chislo<= 10; chislo++)

В этом выражении необычно то, что переменная chisloобъявлена и инициализирована в середине оператора for. Иногда такую переменную называют переменной управления циклом. Она является обычной переменной и объявляется как переменная целого типа. Переменной управления циклом можно давать любые имена. Исторически сложилось так, что таким переменным дают однобуквенные имена, такие как i, j, k, хотя можно давать имена, указывающие на происходящий процесс, как это и происходит в нашем случае.

Как видим, объявление переменной и присвоение ей начального значения сделано в первом аргументе. Этот аргумент соответствует блоку 2 приведенного алгоритма (Рис 2.2).

Второй аргумент называется аргументом завершения. Он является выражением, которое проверяется для завершения цикла, и отвечает блоку 5 алгоритма (Рис 2.2). В данном случае, говоря на языке С++, пока значение переменной управления циклом chisloменьше 10, следует продолжать выполнять операторы, находящиеся в теле цикла.

Важно понять, что в цикле for тело цикла не будет исполняться ни разу, пока не будет вычислено значения проверяемого выражения. Пока это выражение возвращает значение true, то тело цикла будет выполняться. Когда выражение приобретёт значение false, исполнение перейдет к оператору, следующему за телом цикла.

Третий аргумент в операторе forявляется аргументом прироста (блок 4). Он говорит, что к переменной, управляющей циклом надо прибавить 1. В исследуемой программе ми использовали операцию инкремента (++) для того, чтобы прибавлять единицу к значению переменной каждый раз, когда происходит оценка выражения. Если б третьего аргумента б не было, то значение chislo всегда б равнялось 1, и проверяемое выражение всегда было б меньше 10. В таком случае цикл продолжался б бесконечно, то есть получился б бесконечный цикл или, как говорят программисты, программа б зациклилась. Бесконечный цикл – это цикл, который продолжает выполняться потому, что программист забыл принять меры для его завершения.

В данном примере цикл будет выполнятся ровно 10 раз. Тело цикла составляет вывод чисел на экран (блок 3) (Рис 2.4)

Рисунок 2.4. – Результат работы программы

Рассмотрим пошагово, что происходит в программе. Когда цикл выполняется первый раз, то переменной chisloприсваивается значение 1. После этого впервые происходит оценка выражения. Поскольку сейчас значение переменной chisloменьше 10 (1 меньше 10), то выполняется тело цикла и на консоль выводится число 1. Потом (важно понять эту последовательность) происходит прирост значения переменной chislo при помощи операции инкремента (++). Это означает, что переменной chisloприрост присваивается уже после того, как тело цикла выполнилось.

Когда переменная chisloприобретет значение 10, выражение снова будет равняться true, поэтому цикл снова выполнится, после чего значение переменной опять увеличится на единицу и достигнет значения 11. Хотя значение переменной chisloравняется 11, выражение должно быть оценено еще раз. В этом случае выражение вернет значение false, поскольку 11 не меньше 10, поэтому произойдет выход из цикла ы программа будет выполнятся начиная с рядка кода, стоящего за телом оператора for. Если в теле цикла forнеобходимо выполнить больше одного оператора, следует использовать фигурные скобки, чтобы сформировать блок (Рис 2.5)

Рисунок 2.5. – Блок внутри цикла

2.3. Цикл while

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

Структура цикла whileпозволяет много раз использовать фрагменты кода, но момент завершения кода цикла whileне так определен как в цикле for. Там мы определяли эту точку, записав аргумент завершения. В цикле whileнет встроенной переменной управления циклом. Вместо этого, в операторе whileнеобходимо указать выражение, характеризирующее условие выхода из цикла, подобно проверяемому выражению в операторе for. Новички, столкнувшись с оператором while, неправильно пишут это выражение для цикла while, что приводит к бесконечному циклу.

Цикл while – это такой тип цикла, в котором оценка выражения происходит раньше, чем тело цикла выполняется хотя бы один раз.

Синтаксис оператора цикла whileприведен на рисунке 2.6.

Рисунок 2.6. – Синтаксис оператора цикла while

Цикл whileначинается со слова while, после которого в круглых скобках пишется выражение, которое необходимо проверить. Пока выражение будет равно true, тело цикла будет выполняться. Поэтому программист должен сам быть уверен том, что выражение когда-либо станет равным false, и это следует записать с помощью кода в теле цикла. В операторе while выражение оценивается до того, как выполняется тело цикла.

Рассмотри пример. Модифицируем нашу предыдущую программу следующим образом. В гостинице этажи нумеруются со 2-го по 20-й. Мы хотим написать программу, которая будет выводить на дисплей номера этажей, на которых останавливается лифт, используя цикл while.

Рисунок 2.7. – Код программы

Сохраним, скомпилируем, исполним, получим:

Рисунок 2.8. – Окно программы

Как видим, в операторе whileнет аргумента инициализации. Поэтому перед тем, как писать структуру цикла, следует позаботится об этом и записать перед рядком цикла:

intet = 2;

После этого идет цикл whileи наше выражение, которое берётся в круглые скобки. Говоря языком С++: выполнять тело цикла пока значение переменной etменьше 21, и выводить это значение на экран:

while (et< 21)

{

cout<<et<<endl;

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

et++;

}

Новички же, при роботе с циклом whileдопускают два вида ошибок:

1. инициализируют значение переменной, используемой в выражении в теле цикла;
2. увеличивают значение этой переменной за пределами цикла

В первом случае каждый раз при использовании тела цикла значение переменной et вновь равняется 2. Во втором случае, если мы увеличиваем значение переменной вне тела цикла, значение в теле вновь равняется 2. В итоге выражение (et<21) всегда равно trueи цикл никогда не завершится. В обоих случаях мы имеем бесконечный цикл.

2.4. Цикл do-while

В цикле whileусловие продолжения выполнения цикла находится, как мы уже рассмотрели, в начале цикла. Это означает, что в случае невыполнения условия при первой проверке тело цикла вообще не выполняется. Иногда это может быть целесообразным, но возможны ситуации, когда необходимо выполнить тело цикла хотя бы один раз в независимости от правдивости выражения, которое проверяется. В таком случае необходимо использовать цикл do-while, в котором условие продолжения цикла находится аж после тела цикла.

Рисунок 2.9. – Синтаксис цикла do-while

Тут все, что размещено между словами doи while, считается телом цикла.

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

Подадим пример вывода номеров этажей гостиницы черезоператор цикла do-while(Рис 2.10).

Рисунок 2.10 – Код программы

Ключевое слово do означает начало цикла. Дальше идет тело цикла, которое необходимо взять в фигурные скобки. Завершает цикл условие продолжение цикла, взятое в круглые скобки, которое задается с помощью ключевого слова while. Это условие похоже на условие цикла while, однако имеет два отличия: во-первых оно размещается в конце цикла, а во-вторых, заканчивается точкой с запятой (;).

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

ГЛАВА 3. ИСПОЛЬЗОВАНИЕ АЛГОРИТМОВ ДЛЯ ПРОГРАММИРОВАНИЯ МАССИВОВ

3.1. Общие понятия про массивы

В языках программирования, в том числе и С++, при работе с данными одинакового типа их группируют. Основным механизмом для этого является массив. Массив может содержать от нескольких единиц данных до нескольких миллионов. Данные, группируемые в массиве, могут быть как основных типов, таких, например, как int, float, и т.д., так и типов, определенных пользователем.

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

(3.1)

а в случае многомерного массива, например двухмерного – как матрицу вида:

(3.2)

Как видим, элементы массива содержат одинаковые имена и отличаются индексами. Индексы показывают месторасположение элементов в массиве. В одномерном массиве индекс i характеризует порядковый номер элемента, а в двумерном массиве индекс i задает номер рядка, а индекс j – номер столбца. Обращение к элементам массива осуществляется по индексам с присвоением им целочисленных значений. Например, взять первый элемент одномерного массива – означает задать , а двумерного – задать и .

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

3.2. Типичные алгоритмы при работе с массивами

Рассмотрим основные алгоритмы при работе с массивами на примере простых задач.

Пример 1. Ввести одномерный массив вида в память компьютера.

Логика решения задачи следующая:

1. задать начало вычислительного процесса;
2. выделить в памяти компьютера место для размещения элементов массива;
3. последовательно, начиная с первого элемента, загрузить с клавиатуры в память элементы ;
4. перейти к организации нового вычислительного процесса.

На рисунке 3.1. представлено схему алгоритма решения этой задачи. Блок 1 задает начало вычислительного процесса. В блоке 2 отображено действие выделения памяти компьютера под размещение элементов массива. Обращение к первому элементу массива происходит в блоке 3, где индексу присваивается значение единицы, то есть