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

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

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

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

#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 неизменным. Если это так, это означает, что усло­вие а[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:

}

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

#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;

}

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

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

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

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

t = a*N² + b*N*lgN,

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

t = a*N*lgN + b*N.

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

Дата добавления: 2015-07-11