2. Метод поиска наименьшего (наибольшего)

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

На рис.2.7 приведен алгоритм сортировки чисел по возрастанию. Блок – схема представлена двумя вложенными циклами. Внешний цикл с параметром цикла k осуществляет назначение каждый раз числа на роль минимального a_min в рассматриваемом ряде чисел и одновременно отсекает уже выставленное вперед число после предыдущего цикла.

Вложенный цикл с параметром цикла i представляет собой типовой алгоритм определения наименьшего числа из ряда чисел. Здесь роль наименьшего числа играет число , которое изменяется последовательно от a₁ до a_n-1. Вложенный цикл рассматривает ряд чисел, начиная с соседнего с , то есть с числа . За пределами вложенного цикла производится обмен числами, наименьшего и первого в рассматриваемом ряде. Здесь роль переменной , используемой в методе смежных пар, играет переменная .

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

Сортировка по убыванию осуществляется аналогично. При этом в рассмотренной блок-схеме идентификатор необходимо заменить идентификатором , что вызывает правильные ассоциации, а операцию сравнения " < " – на операцию " > ".

_

+

Рис. 2.7 Блок – схема сортировки чисел по возрастанию методом

определения наименьшего числа

2.2.8. Алгоритмы решения задач с использованием матриц

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

На рис.2.8 приведен алгоритм вычисления суммы элементов матрицы a(m*n). Внешний цикл предназначен для установления текущего адреса i строки матрицы, а внутренний (вложенный) – текущего адреса j ее столбца.

Рис. 2.8 Блок – схема вычисления суммы элементов матрицы

Вычисление произведения Р элементов матрицы осуществляется по аналогичной блок – схеме, в которой следует заменить символ S на P, операцию S = 0 на операцию P = 1, а операцию S = S + a_{i j} - на операцию P =P*a_{i j}.

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

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

Пример 1. В заданной матрице a(m*n) определить наибольшие элементы строк. Алгоритм решения этой задачи представлен на рис.2.9.

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

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

_

+

Рис. 2.9 Блок-схема определения максимального элемента

в строке матрицы

Пример 2. В заданной матрице a(m*n) определить наибольший элемент в каждом столбце. Алгоритм решения этой задачи приведен на рис.2.10.

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

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

_

+

Рис. 2.10 Блок-схема определения максимального элемента

в столбце матрицы

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

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

3. КРАТКИЕ СВЕДЕНИЯ ОБ АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ С++

Алгоритмический язык С++ – объектно-ориентированный язык, который унаследовал все основные свойства структурно-ориентированного языка С (Си) и дополнил его новым видом переменных – объектами (переменными типа класс). Это дополнение придало языку новые качества, существенно расширяющие возможности языка.

Язык С++ основан на трех основных концепциях:

• инкапсуляции (закрытости);

• полиморфизме (использование единого интерфейса в сходных задачах);

• наследовании (использование имеющихся разработок).

Автором языка С++ является Бьярн Страуструп, сотрудник научно-исследовательского центра AT & T Bell Laboratories (нью-Джерси, США). Годом создания языка считается 1979 год.

Язык С++ претерпел две существенные модернизации в 1985 и в 1990 гг. Последняя, третья модернизация связана с процессом стандартизации языка С++. В настоящее время существует стандарт языка, разработанный комитетом по стандартизации ANSI (American National Standards Institute) и международной организацией по стандартам ISO (International Standard Organization).

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

В силу того, что появляется все больше пакетов прикладных программ для решения самых разнообразных задач, доля «ручного» программирования для рядового пользователя заметно сокращается. Об этом говорилось ранее. Поэтому в дисциплине «Введение в информатику» излагаются только основные сведения о языке С++, позволяющие составлять простейшие программы вычислений.

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