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

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

1. Считать исходные данные в массив.

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

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

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

 

-8

макс

+

-1

+

+

-10 мин

 

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

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

Сформулируем алгоритм поиска максимума:

1. Принять за максимальный первый элемент массива.

2. Просмотреть массив, начиная со второго элемента.

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

Программа поиска максимального элемента:

 

{***************************************************}

{Программа: MAX_ELEM. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program MAX_ELEM;

Const n = 10;

Var a: array [1.. n] of integer; {массив}

i: integer; {номер текущего элемента}

max: integer; {максимальный элемент}

Begin

Writeln(‘Введите ‘, n, ‘ элементов массива’);

For i: =1 to n do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

max: = a[1]; {принять за максимальный первый элемент массива}

For i: = 1 to n do {просмотреть массив, начиная с первого элемента}

if a[i]> max then max: = a[i];

writeln(‘Максимальный элемент: ’, max)

End. { MAX_ELEM }

 

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

 

{***************************************************}

{Программа: INDEX_MAX_ELEM. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program INDEX _ MAX_ELEM;

Const n = 10;

Var a: array [1.. n] of integer; {массив}

i: integer; {номер текущего элемента}

imax: integer; {номер максимального элемента}

Begin

Writeln(‘Введите ‘, n, ‘ элементов массива’);

For i: =1 to n do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

imax: = 1;

For i: = 1 to n do

if a[i]> a[imax] then imax: = i;

writeln(‘Номер максимального элемента: ’, imax);

writeln(‘Максимальный элемент: ’, a[imax])

End. { INDEX_MAX_ELEM }

 

В этой программе в переменной imax запоминается номер максимального из просмотренных элементов. По этому номеру осуществляется выборка элементов из массива.

Запишем уточненный алгоритм решения рассматриваемой задачи:

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

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

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

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

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

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

3. Определить количество положительных элементов в найденном диапазоне:

· обнулить счетчик положительных элементов;

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

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

{***************************************************}

{Программа: NUM_POSITIV. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program NUM_POSITIV;

Const n = 10;

a: array [1.. n] of integer = (1, 3, -5, 1, -2, 1, -1, 3, 8, 4);

Var i: integer; {индекс текущего элемента}

imax: integer; {индекс максимального элемента}

imin: integer; {индекс минимального элемента}

ibeg: integer; {начало интервала}

iend: integer; {конец интервала}

count: integer; {количество положительных элементов}

Begin

For i: =1 to n do writeln(a[i]: 3);

Writeln;

imax: = 1;

imin: = 1;

For i: = 1 to n do

Begin

if a[i]> a[imax] then imax: = i;

if a[i]< a[imin] then imin: = i

end;

writeln(‘max= ’, a[imax]: 3, ‘min= ‘, a[imin]: 3);

if imax < imin then ibeg: = imax

else ibeg: = imin;

if imax < imin then iend: = imin

else iend: = imax;

count: = 0;

for i: = ibeg + 1 to iend – 1 do

if a[i] > 0 then inc(count);

writeln(‘Количество положительных: ’, count: 5)

End. { NUM_POSITIV }

 

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

§ элемент a[imin] расположен левее элемента a[imax];

§ элемент a[imin] расположен правее элемента a[imax];

§ элементы a[imin] и a[imax] совпадают.

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

 

Приложение № 6.

 

СУММА ЭЛЕМЕНТОВ ПРАВЕЕ ПОСЛЕДНЕГО ОТРИЦАТЕЛЬНОГО

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

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

{***************************************************}

{Программа: EXAMPLE. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program EXAMPLE;

Const n = 10000;

Var a: array [1.. n] of integer; {массив}

i: integer; {номер текущего элемента}

nf: integer; {фактическое количество элементов в массиве}

Begin

Writeln(‘Введите количество элементов массива’);

Readln(nf);

If nf > n then

Begin

Writeln(‘Превышение размеров массива’);

Exit

End;

Writeln(‘Ввести элементы массива’);

For i: =1 to nf do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

For i: = 1 to n do writeln(‘a[’, i: 2, ‘]=’, a[i]: 4)

End. { EXAMPLE }

 

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

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

 

{***************************************************}

{Программа: SUM_ELEM_1. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program SUM_ELEM_1;

Const n = 10000;

Var a: array [1.. n] of real;

i: integer; {индекс текущего элемента}

ineg: integer; {номер последнего отрицательного элемента}

nf: integer; {фактическое количество элементов в массиве}

sum: real; {сумма элементов}

Begin

Writeln(‘Введите количество элементов массива’);

Readln(nf);

If nf > n then

Begin

Writeln(‘Превышение размеров массива’);

Exit

End;

Writeln(‘Ввести элементы массива’);

For i: =1 to nf do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

Writeln(‘Исходный массив: ’);

For i: = 1 to nf do writeln(‘a[’, i: 2, ‘]=’, a[i]: 4);

Writeln;

For i: =1 to nf do

If a[i] < 0 then ineg: = i;

sum: = 0;

For i: = ineg + 1 to nf do sum: = sum +a[i];

writeln(‘Сумма: ’, sum: 7: 2)

End. { SUM_ELEM_1 }

 

Номер последнего отрицательного элемента массива формируется в переменной ineg. При просмотре массива в эту переменную последовательно записываются номера всех отрицательных элементов массива. Таким образом, после выхода из цикла в ней остается номер самого последнего элемента. Может возникнуть мысль с целью оптимизации программы объединить цикл нахождения номера последнего отрицательного элемента с циклами ввода и контрольного вывода элементов массива, но так делать не советую, потому что ввод данных, их вывод и анализ – разные по смыслу действия, и смешивание их в одном цикле не прибавит программе ясности. После отладки программы операторы вывода можно удалить или закомментировать.

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

 

{***************************************************}

{Программа: SUM_ELEM_2. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program SUM_ELEM_2;

Const n = 10000;

Var a: array [1.. n] of real;

i: integer; {индекс текущего элемента}

ineg: integer; {номер последнего отрицательного элемента}

nf: integer; {фактическое количество элементов в массиве}

sum: real; {сумма элементов}

Begin

Writeln(‘Введите количество элементов массива’);

Readln(nf);

If nf > n then

Begin

Writeln(‘Превышение размеров массива’);

Exit

End;

Writeln(‘Ввести элементы массива’);

For i: =1 to nf do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

Writeln(‘Исходный массив: ’);

For i: = 1 to nf do writeln(‘a[’, i: 2, ‘]=’, a[i]: 4);

Writeln;

Ineg: = -1;

For i: =1 to nf do

If a[i] < 0 then ineg: = i;

If ineg = -1 then writeln(‘Отрицательных лементов нет’)

else begin

sum: = 0;

For i: = ineg + 1 to nf do sum: = sum +a[i];

writeln(‘Сумма: ’, sum: 7: 2)

end

End. { SUM_ELEM_2 }

 

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

 

{***************************************************}

{Программа: SUM_ELEM_3. }

{Программист: Иванов И.И. }

{Дата выполнения: 10 апреля 2006 г. }

{***************************************************}

Program SUM_ELEM_3;

Const n = 10000;

Var a: array [1.. n] of real;

i: integer; {индекс текущего элемента}

nf: integer; {фактическое количество элементов в массиве}

sum: real; {сумма элементов}

is_neg: boolean; {признак наличия отрицательного элемента}

Begin

Writeln(‘Введите количество элементов массива’);

Readln(nf);

If nf > n then

Begin

Writeln(‘Превышение размеров массива’);

Exit

End;

Writeln(‘Ввести элементы массива’);

For i: =1 to nf do

Begin

Writeln(‘a[‘, i: 2, ‘]=’);

Read(a[i])

End;

Writeln(‘Исходный массив: ’);

For i: = 1 to nf do writeln(‘a[’, i: 2, ‘]=’, a[i]: 4);

Writeln;

Is_neg: = false;

sum: = 0;

For i: = nf downto 1 do begin

If a[i] < 0 then begin

is_neg: = true;

Break

end;

sum: = sum +a[i]

end;

if is_neg then writeln(‘Сумма: ’, sum: 7: 2)

else writeln(‘Отрицательных элементов нет’)

End. { SUM_ELEM_3 }

 

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

 

Приложение № 7.

 

СЖАТИЕ МАССИВА

⇐ Предыдущая12345Следующая ⇒

Поделиться: