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

 

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

 

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

 

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

 

#include < iostream.h> int main () { int n; cout < < " Введите количество элементов "; cin > > n; int i, ineg; float sum, *a = new float [n]; // 1 cout < < " Введите элементы массива "; for (i = 0; i < n; i++) cin» a[i]; for (i = 0; i < n; i++) cout «a[i] «' '; // 2 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. Выделяется столько памяти, сколько необходимо для хранения n элементов вещественного типа, и адрес начала этого участка заносится в указатель а.

 

 

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

 

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

 

Теперь перейдем к самому интересному — к критическому анализу нашей первой попытки решения задачи. Для массивов, содержащих отрицательные элементы, эта программа работает верно, но при их отсутствии, как правило, завершается аварийно. Это связано с тем, что если в массиве нет ни одного отрицательного элемента, переменной ineg значение не присваивается. Поэтому в операторе for (оператор 4) будет использовано значение ineg, ниспосланное Богом. Обычно всевышний таких ошибок не прощает, и программа незамедлительно «вылетает». Поэтому в программу необходимо внести проверку, есть ли в массиве хотя бы один отрицательный элемент. Для этого переменной ineg присваивается начальное значение, не входящее в множество допустимых индексов массива (например, -1). После цикла поиска номера отрицательного элемента выполняется проверка, сохранилось ли начальное значение ineg неизменным. Если это так, это означает, что условие a[i ] < 0 в операторе 3 не выполнилось ни разу, и отрицательных элементов в массиве нет:

 

#include < iostream.h> int main () { int n; cout < < " Введите количество элементов "; cin > > n; float sum, *a = new float [n]; // 1 int i; cout < < " Введите элементы массива: "; for (i = 0; i < n; i++) cin > > a[i]; int ineg = -1; for (i = 0; i < n; i++) if (a[i] < 0) ineg = i; // 3 if (ineg! = -1) { for (sum = 0, i = ineg + 1; i < n; i++) sum += a[i]; cout < < " \nСумма " < < sum < < endl; } else cout < < " \nОтрицательных элементов нет" < < endl; return 0; }

 

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

 

#include < iostream.h> int main () { int n; cout < < " Введите количество элементов: "; cin > > n; float *a = new float [n]; int i; cout < < " Введите элементы массива: "; for (i = 0: i < n; i++) cin > > a[i]; bool flag_neg = false; float sum = 0; for (i = n - 1; i > = 0; i--) { if (a[i] < 0) { flag_neg = true; break; } sum += a[i]; } if (flag_neg) cout < < " \n Сумма" < < sum; else cout < < " \n Отрицательных элементов нет"; return 0; }

 

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

 

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

 

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

 

Мы рассмотрели примеры задач поиска и вычисления в массиве. Другой распространенной задачей является сортировка массива, то есть упорядочивание его элементов в соответствии с каким-либо критерием — чаще всего по возрастанию или по убыванию элементов. Существует множество методов сортировки, различающихся по поведению, быстродействию, требуемому объему памяти, а также ограничениям, накладываемым на исходные данные. В Учебнике (см. с. 59) рассмотрен один из наиболее простых методов — сортировка выбором. Он характеризуется квадратичной зависимостью времени сортировки t от количества элементов:

 

 

где а и b — константы, зависящие от программной реализации алгоритма. Иными словами, для сортировки массив требуется просмотреть порядка N раз. Существуют алгоритмы и с лучшими характеристиками1, самый известный из которых предложен Ч. Э. Р. Хоаром и называется «быстрая сортировка». Для него зависимость имеет вид:

 

 

Давайте ради любопытства посмотрим, за счет чего достигается экономия.