Для данного массива элементы имеют номера от О до 9. Номер элемента указывается после его имени в квадратных скобках, например, а[0]. а[3].

Задача 3.1. Количество элементов между минимумом и максимумом

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

Запишем алгоритм в самом общем виде.

1. Определить, где в массиве расположены его максимальный и минимальный элементы, то есть найти их индексы.

2. Просмотреть все элементы, расположенные между ними. Если элемент массива больше нуля, увеличить счетчик элементов на единицу.

Перед написанием программы полезно составить тестовый пример, чтобы более наглядно представить себе алгоритм решения задачи. Ниже представлен пример массива из 10 чисел и обозначены искомые величины:

6 -8 15 9 -1 3 5 -10 12 2

макс

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

1. Определить, где в массиве расположены его максимальный и минимальный элементы:

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

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

2. Определить границы просмотра массива для поиска положительных элементов, находящихся между его максимальным и минимальным элементами:

Если максимум расположен в массиве раньше, чем минимум, принять левую границу просмотра равной индексу максимума, иначе - индексу минимума.

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

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

Для экономии времени при отладке значения элементов массива задаются путем инициализации.

#include <iostream.h> int mainOI const int n = 10:

int a[n] - {1. 3. -5. 1. -2. 1. -1. 3. 8. 4}:

int i. imax. imin. count:

for (i - imax - imin 0: i < n: i++) {

if (a[i] > a[imax]) imax i:

if (a[i] < aCimin]) imin i:

cout \n\t max= a[imax] min= a[imin]; отладка

int ibeg = imax < imin ? imax : imin: int iend = imax < imin ? imin : imax:

cout \n\t ibeg- ibeg iend iend: отладка

for (count - 0. i - ibeg + 1: i < iend: i++) if (a[i] > 0) count++:

cout Количество положительных: count endl; return 0:

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

СОВЕТ -

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

Массив просматривается, начиная с элемента, следующего за максимальным (минимальным), до элемента, предшествующего минимальному (максимальному). Индексы границ просмотра хранятся в переменных ibeg и iend. В приведенной выше программе для определения их значений используется тернарная условная операция (см. с. 36). Можно поступить и по-другому: просматривать массив всегда от максимума к минимуму, а индекс при просмотре увеличивать или уменьшать в зависимости от их взаимного расположения.

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

#include <iostream.h> int main(){

const int n = 10:

int a[n]:

int i. imax. imin. kol:

cout Введите п целых чисел: endl: for (i = 0: i < n: i++) cin a[i]: for (i = 0: i < n: i++) cout a[i] : for (i = imax = imin = 0: i < n: i++) {

if (a[i] > a[imax]) imax = i:

if (a[i] < a[imin]) imin = i:

int d = 0:

if (imax < imin) d = 1: else if (imax > imin) d - -1:

for (kol - 0. i - imax + d; i !- imin: i +- d) if (a[i] > 0) kol++: cout \n Количество положительных: kol endl: return 0:

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

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

1) aCimin] расположен левее a[imax];

2) a[imin] расположен правее a[imax];

3) a[imin]Ha[imax] совпадают.

Последняя ситуация имеет место, когда в массиве все элементы имеют одно и то же значение. Кстати, во втором варианте программы третий случай корректно обрабатывается благодаря значению d О для этой ситуации. Желательно также проверить, как работает программа, если a[imin] и a[imax] расположены рядом, а также в начале и в конце массива (граничные случаи). Элементы массива нужно задавать как положительные, так и отрицательные.

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

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

#include <iostream.h>

int main(){

const int n - 1000: int a[n]: int i. kol a:

cout Введите количество элементов : cin kol a: if (kol a > n ) {

cout Превышение размеров массива endl: return 1:} for (i - 0: i < kol a: i++) cin a[i]: for (i 0: i < kol a: i++) cout a[i] : cout endl: return 0:

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

Динамические массивы

Если до начала работы программы неизвестно, сколько в массиве элементов, в программе следует использовать динамические массивы. Память под них выделяется с помощью операции new или функции mal 1ос в динамической области памяти во время выполнения программы. Адрес начала массива хранится в переменной, называемой указателем. Например:

int п = 10:

int *а - new int[n]:

double *b = (double *)malloc(n * sizeof (double)):

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

В третьей строке для выделения памяти под п элементов типа doubl е используется функция mall ос, унаследованная из библиотеки С. Этот способ устарел, поэтому мы им пользоваться не будем.

ВНИМАНИЕ -----

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

Обращение к элементу динамического массива осуществляется так же, как и к элементу обычного - например а[3]. Можно обратиться к элементу массива и другим способом - *(а + 3). В этом случае мы явно задаем те же действия, что выполняются при обращении к элементу массива обычным образом. Рассмотрим их под-

Семинар 3. Одномерные массивы и указатели

Задача 3.2. Сумма элементов правее последнего отрицательного

робнее. В переменной-указателе а хранится адрес начала массива*. Для получения адреса третьего элемента к этому адресу прибавляется смещение 3. Операция сложения с константой для указателей учитывает размер адресуемых элементов, то есть на самом деле индекс умножается на длину элемента массива: а + 3 * sizeof(int). Затем с помощью операции * (разадресации) выполняется выборка значения из указанной области памяти.

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

Размерность массива при этом не указывается.

ВНИМАНИЕ -----

Квадратные скобки в операции delete [] при освобождении памяти из-под массива обязательны. Их отсутствие может привести к неопределенному поведению программы. Память, выделенную с помощью та! 1ос, следует освобождать посредством функции free (см. Учебник, с. 55, с. 422).

-/Таким образом, время жизни динамического массива, как и любой динамической переменной, - с момента вьщеления памяти до момента ее освобождения. Область действия зависит от места описания указателя, через который производится работа с массивом. Область действия и время жизни указателей подчиняются общим правилам, рассмотренным на первом семинаре. Как вы помните, локальная переменная при выходе из блока, в котором она описана, теряется . Если эта переменная является указателем и в ней хранится адрес выделенной динамической памяти, при выходе из блока эта память перестает быть доступной, однако не помечается как свободная, поэтому не может быть использована в дальнейщем. Это называется утечкой памяти и является распространенной ошибкой: { пример утечки памяти

int п: cin п:

int *pmas = new int[n];

после выхода из блока указатель pmas недоступен

Задача 3.2. Сумма элементов правее последнего отрицательного

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

Имя статического массива также является указателем на его первый элемент, только константным (то есть ему нельзя присвоить новое значение).

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

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

finclude <iostream.h> int main(){ int n:

cout Введите количество элементов : cin n: int i, ineg:

float sum, *a - new float [n]: III

cout Введите элементы массива : for (i = 0: i < n: i++) cin a[i]:

for (i = 0: i < n: i++) cout a[i] ; /12

for (i = 0: i < n: i-н-) if (a[i] < 0) ineg = i: 3

for (sum - 0. i - ineg + 1: i < n: i++) sum +- a[i]: 4

cout Сунна sum: return 0:

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

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

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

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