Добавлен: 04.04.2023
Просмотров: 217
Скачиваний: 2
Рисунок 3 – Циклическая структура с предусловием
Рисунок 4 – Циклическая структура с постусловием
Цикл с предусловием можно прочитать следующим образом:
пока проверка условия дает результат «да», выполнять действие.
Если при очередной проверке условия будет получено результат «нет», повторное выполнение действия будет прекращено и произойдет выход из цикла.[13]
Например, для подсчета остатка от деления целого числа t на целое число n с помощью вычитания можно воспользоваться циклом:
пока t> n, уменьшить t на n.
В цикле с постусловием (рисунок 4) условие цикла формулируется противоположным образом: если очередная проверка условия дает результат "да", происходит выход из цикла. Цикл с постусловием можно сокращенно прочитать так:[7]
повторять действие до получения результата «да» при проверке условия.
Например, подсчет остатка от деления целого числа t на целое число n (t> n) можно реализовать с помощью цикла:[9]
повторять уменьшить t на n до t <n.
Стоит обратить внимание на то, что является общим для обоих типов цикла:
– обе базовые структуры цикла являются замкнутыми;
– количество повторений цикла определяется его условием;
– выход из цикла происходит только через проверку условия цикла.
Наиболее существенная разница между типами циклов заключается в том, что тело цикла с постусловием обязательно выполняется хотя бы один раз – до первой проверки условия, а цикл с предусловием может не выполнятся ни разу, если при первой же проверке условия имеем результат «нет». Поэтому рассмотренные типы циклов не являются взаимозаменяемыми: цикл с постусловием можно заменить циклом с предусловием, а наоборот – нет.[12]
В первом разделе рассмотрены теоретические основы алгоритмизации, поскольку алгоритмы сортировки являются нетривиальными алгоритмами, которые содержат и вложенные циклы, и проверку условий, и линейные части алгоритмов.
2. Массивы данных и их сортировка
2.1. Реализация циклических алгоритмов на языке программирования С++
Поскольку алгоритмы сортировки будут рассматриваться на примере массивов данных и циклических алгоритмов, рассмотрим основные методы реализации работы с ними.[4]
Рассмотрим реализацию циклических алгоритмов на языке С++, в котором существую три разновидности операторов цикла:[1]
– оператор цикла for;
– оператор цикла с предусловием while;
– оператор цикла с постусловием do ... while.
Все операторы цикла непременно содержат следующие составные части:
– присваивания исходных значений (инициализация);
– условие продолжения цикла;
– тело цикла;
– изменение параметра (счетчика) цикла.
Оператор for обычно используется, когда есть заранее известное количество повторений или когда условие продолжения выполнения цикла записывается кратким выражением. Примерами использования данного оператора являются вычисления сумм заданного количества слагаемых, поиск минимального (максимального) элемента последовательности чисел, сортировки элементов массива по возрастанию (убыванию) и т.д.[7]
Синтаксис оператора следующий:
for (<инициализация>; <условие>; <модификации>)
{
<тело цикла>;
}
Конструкция этого оператора состоит из трех основных блоков, размещенных в круглых скобках и отделенных друг от друга точкой с запятой (;) и команд (тела цикла), которые могут многократно повторятся. В начале выполнения оператора цикла, однократно, в блоке инициализации задаются начальные значения переменных, которые управляют циклом. Затем проверяется условие и, если оно выполняется, то управление переходит к выполнению тела цикла. Блок модификации меняет параметры цикла и, в случае истинности условия, выполнение цикла продолжается. Если условие не выполняется (false или равно нулю), то цикл прерывается и управление передается на оператор, следующий за оператором for. Существенным является то, что проверка условия выполняется в начале цикла. Это значит, что тело цикла может не выполниться ни разу, если условие сначала ошибочное. Каждое повторение (шаг) цикла называется итерацией.[10]
Простой пример для вычисления суммы проиллюстрирует использования оператора for:
int s = 0;
for (int i = 1; i<= 10; i ++)
s + = i;
Этот оператор цикла можно прочитать так: "выполнить команду s + = i 10 раз (для значений i от 1 до 10 включительно, где i при каждой итерации увеличивается на 1)". В этом примере есть два присваивания начальных значений: s = 0 и i = 1, условие продолжения цикла: (i <= 10) и изменение параметра: i ++. Телом цикла является команда s + = i.[8]
Порядок выполнения этого цикла компьютером такой:
1) присваиваются начальные значения (s = 0, i = 1);
2) проверяется условие (i <= 10);
3) если условие истинное (true), выполняется команда (или команды) тела цикла: к сумме, полученной на предыдущей итерации, добавляется новое число;
4) параметр цикла увеличивается на 1.
Далее возвращаемся к пункту 2. Если условие в пункте 2 не будет выполнено (false), произойдет выход из цикла.[5]
В операторе возможные конструкции, когда отсутствует тот или иной блок: инициализация может отсутствовать, если начальное значение задать предварительно; условие – если предполагается, что условие всегда истинно, то есть следует непременно выполнять тело цикла, пока не встретится оператор break; а модификации – если прирост параметра осуществлять в теле цикла. В этих случаях само выражение блока упускается, но точку с запятой обязательно нужно оставить. [7]
Для заблаговременного выхода из цикла применяют операторы break (выход из конструкции) или return (выход из текущей функции). [9]
Некоторые варианты применения оператора for повышают его гибкость за счет возможности использования нескольких переменных-параметров цикла.
Циклы могут быть вложены друг в друга. При использовании вложенных циклов надо составлять программу таким образом, чтобы внутренний цикл полностью укладывался в тело внешнего цикла, то есть циклы не должны пересекаться. В свою очередь, внутренний цикл может содержать собственные вложенные циклы. Имена параметров внешнего и внутреннего циклов должны быть разными. Допускаются следующие конструкции:[5]
fог(k = 1; k <= 10; k ++)
{
fог (i = 1; i<= 10; i ++)
{
fог (t = 1; t <= 10; t ++)
{
...
}
}
}
Вложенные циклы используются для выполнения сортировок различными методами.
Операторы с предусловием и постусловием используются для организации циклов и являются альтернативными к оператору for. Обычно цикл с предусловием используется, если количество повторений заранее неизвестно, а для многократного повторения тела цикла известно условие, при истинности которого цикл продолжает выполнение. Это условие следует проверять каждый раз перед очередной итерацией. Например, при считывании данных из файла условием цикла является наличие данных непосредственно в файле, то есть повторять чтение данных следует до тех пор, пока указатель не будет указывать на конец файла.[13]
Синтаксис цикла с предусловием следующий:
while (<условие>)
{
<тело цикла>
};
Последовательность операторов (тело цикла) выполняется пока условие является истинным, а выход из цикла осуществляется, когда условие станет ложным. Если условие является ошибочным при вхождении в цикл, то последовательность операторов ни разу не выполнится, а управление будет передаваться к следующему оператору программы.
Цикл с постусловием используется, если есть необходимость проверять истинность условия каждый раз после очередной итерации. Как отмечалось выше, отличие цикла с предусловием от цикла с постусловием заключается в первой итерации: цикл с постусловием всегда выполняется по крайней мере один раз независимо от условия.[7]
Синтаксис цикла с постусловием следующий:[1]
do
{
<тело цикла>
}
while (<условие>);
Последовательность операторов (тело цикла) выполняется один или несколько раз, пока условие станет ложным. Оператор цикла do ... while используется в тех случаях, когда есть необходимость выполнить тело цикла хотя бы один раз, поскольку проверка условия осуществляется после выполнения операторов.[4]
Если тело цикла состоит из одного оператора, то операторные скобки {} не является обязательны.
Операторы while и do ... while могут преждевременного завершиться при выполнении операторов break и return внутри тела цикла.
2.2. Использование и обработка массивов с помощью операторов цикла
Поскольку алгоритмы сортировки принято использовать в обработке массивов, рассмотрим основные понятия о них.[3]
Часто, в процессе разработки программы, возникает потребность хранить большое количество однотипных значений, которые должны поддаваться одинаковым методам обработки. Например, экзаменационные оценки студентов, следует вводить, выводить, анализировать (сравнение с "2" или "5"), изменять при необходимости и тому подобное. Такие однотипные значения имеет смысл хранить в одной переменной, перенумеровать их внутри этой переменной, предоставить доступ к этим значениям по индексу и обрабатывать эти значения в цикле (номер индекса должен совпадать с значением параметра цикла).[9]
Массив – это упорядоченная совокупность однотипных элементов. Массивы широко применяются для хранения и обработки однородной информации, например таблиц, векторов, матриц, коэффициентов уравнений и т.д. [1]
Каждый элемент массива однозначно можно определить по имени массива и индексе. Имя массива (идентификатор) подбирают по тем же правилам, что и для переменных. Индексы определяют местонахождение элемента в массиве. К примеру, элементы вектора имеют один индекс – номер по порядку; элементы матриц или таблиц имеют по два индекса: первый означает номер строки, второй – номер столбца. Количество индексов определяет размерность массива. Например, векторы в программах – это одномерные массивы, матрицы – двумерные.[3]
Индексами могут быть только переменные, константы или выражения целого типа. Значения индексов записывают после имени массива в квадратных скобках. При объявлении массивов в квадратных скобках указывается количество элементов, а нумерация элементов всегда начинается с нуля.
Различия массива от обычных переменных следующие:[14]
– общее имя для всех значений;
– доступ к конкретному значению по его номеру (индексу)
– возможность обработки в цикле.
Одномерный массив объявляется в программе следующим образом:
<тип данных><имя_массива> [<размер массива>];
Тип данных задает тип элементов массива. Элементами массива не могут быть функции и элементы типа void. Размер массива в квадратных скобках задает количество элементов массива. В отличие от других языков, в C++ не проверяется выход за пределы массива, поэтому, чтобы избежать ошибок в программе, следует следить за размерностью объявленных массивов. Значение размера массива при объявлении может быть не указано в следующих случаях:[15]
– при объявлении массив инициализируется;
– массив объявлен как формальный параметр функции;
– массив объявлен как ссылка на массив, явно определенный в другом модуле.
Используя имя массива и индекс, можно обращаться к элементам массива:
<имя_массива> [<значение_ индекса>]
Значения индексов должны находиться в диапазоне от нуля до величины, на единицу меньше размера массива, который определен при его объявлении, поскольку в C ++ нумерация индексов начинается с нуля.[12]
Например,
intA[10];
объявляет массив с именем А, содержащий 10 целых чисел; при этом выделяет и закрепляет за этим массивом оперативную память для всех 10-ти элементов соответствующего типа (int – 4 байта), то есть 40 байтов, следующим образом (рисунок 5):
|
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
A[5] |
A[6] |
A[7] |
A[8] |
A[9] |
Рисунок 5 Изображение одномерного массива
Следовательно, при объявлении массива выделяется память, необходимая для размещения всех его элементов. Элементы массива с первого до последнего запоминаются в последовательно возрастающих адресах памяти. Между элементами массива в памяти промежутков нет. Элементы массива записываются один за другим поэлементно.[13]
Для получения доступа к i-му элементу массива А, можно написать А[і], где i – переменная цикла (счетчик цикла), которая может принимать значения от 0 до 9. При этом величина i умножается на размер типа int и представляет собой адрес i-го элемента массива А от его начала, после чего осуществляется выбор элемента массива А по сложившейся адресу.[2]