2015-06-05
1128
Обычно алгоритмы данной группы осуществляют последовательный перебор и накопление сведений об элементах массива с последующим вычислением характеристик всей последовательности значений.
К задачам подобного рода можно отнести: вычисления суммы и среднеарифметического значений элементов, нахождение количества определённых элементов, вычисление статистических характеристик (отклонений, медиан, дисперсий) и т.п.
Некоторые из этих задач решаются с помощью нескольких последовательных переборов всех элементов массива.
Рассмотрим в качестве примера программу, которая вычисляет процент положительных значений среди ненулевых элементов массива.
Алгоритм решения задачи представлен на рисунке 17.
На рисунке 17 блоки 2, 3, 4 используются для ввода исходных данных. Блок 3 организует цикл с параметром i, который, изменяясь от 1 n (n – количество элементов в массиве), перебирает все индексы элементов массива. Блок 4 в каждом новом проходе цикла заполняет последовательно каждый из элементов массива.
|
|
|
Блок 5 инициализирует служебные переменные: chNO используется для подсчёта количества ненулевых элементов, chP используется для подсчёта количества положительных элементов.
Далее блок 6 организует перебор всех элементов массива, аналогично блоку 3. В этом цикле каждый элемент проверяется на положительность и отличность от 0. Если элемент положительный (блок 7), то увеличивается на 1 значение переменной chP (блок 8). Затем снова выполняется проверка: если элемент не равен нулю (блок 9), то увеличивается на 1 значение переменной chNO (блок 10).
Рисунок 17 – Блок-схема алгоритма вычисления процента положительных значений среди ненулевых элементов массива
После окончания цикла вычисляем требуемый процент (блок 11) и выводим полученное значение (блок 12).
В таблице 8 приведена трассировка части алгоритма (рис. 17). Каждая строка трассировочной таблицы соответствует выполнению определённого алгоритмического блока. В колонках представлены значения определённых переменных, или выражений, необходимых для пояснения алгоритма. Для удобства восприятия жирным в таблице выделены значения, которые изменились во время выполнения соответствующего блока.
Таблица 8 – Трассировка алгоритма подсчёта количества
положительных и ненулевых элементов
| № блока | i | chNO | chP | A[i] | A | ||||
| ... | |||||||||
| -2 | -2 | -1 | |||||||
| -2 | -2 | -1 | |||||||
| -2 | -2 | -1 | |||||||
| -2 | -2 | -1 | |||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -2 | -1 | ||||||||
| -1 | -2 | -1 | |||||||
| -1 | -2 | -1 | |||||||
| -1 | -2 | -1 | |||||||
| -1 | -2 | -1 | |||||||
| -1 | -2 | -1 | |||||||
| -1 | -2 | -1 | |||||||
| ... |
Реализация алгоритма в программу выглядит следующим образом:
|
|
|
program Proz;
Var
A: array [1..10] of real;
chNO,chP,n,i:integer;
Begin
writeln('введите размер массива');
readln(n);
for i:=1 to n do
readln(A[i]);
chNO:= 0;
chP:= 0;
for i:=1 to n do
Begin
if A[i]>0 then
chP:= chP + 1;
if A[i]<>0 then
chNO:= chNO + 1;
end;
writeln('процент положительных значений -', chP/chNO*100);
End.
Рассмотрим ещё один пример: необходимо найти все чётные элементы в массиве А и поместить их в массив В.
Алгоритм решения задачи представлен на рисунке 18.
В целом рассматриваемый алгоритм (рис. 18) схож с алгоритмом поиска определённых элементов. Разница состоит в том, что значения найденных элементов не накапливаются для последующей обработки, а перемещаются в новый массив.
Для индексов найденных элементов используется независимый счётчик j. В начале перебора ему присваивается значение 1 (блок 5). При нахождении в исходном массиве первого чётного элемента выполняется его запись в массив В под номером j (j = 1), и значение счётчика j увеличивается на единицу и становится равным 2 (блоки 7, 8). Соответственно, следующий найденный элемент будет помещён в массив В под номером 2.
Рисунок 18 – Блок-схема алгоритма поиска
чётных элементов
В таблице 9 приведена трассировка части алгоритма (рис. 18). Каждая строка трассировочной таблицы соответствует состоянию переменных после выполнения определённого алгоритмического блока. В колонках представлены значения определённых переменных, или выражений, необходимых для пояснения алгоритма. Для удобства восприятия жирным в таблице выделены значения, которые изменились во время выполнения соответствующего блока.
Таблица 9 – Трассировка алгоритма копирования чётных
элементов из массива А в массив В
| № блока | A[i] | i | A | j | B | ||||||||
| ... | |||||||||||||
| - | - | ||||||||||||
| ... |
Реализация алгоритма в программу выглядит следующим образом:
program A_Bmas;
Var
B,A:array[1..100] of integer;
n,i,j:integer;
Begin
write('n>');
read(n);
for i:=1 to n do
Begin
write('A[',i,']→');
read(A[i]);
end;
j:=1;
|
|
|
for i:=1 to n do
Begin
if A[i] mod 2 = 0 then
Begin
B[j]:=A[i];
j:=j+1;
end;
end;
for i:=1 to j-1 do
writeln(B[i]);
End.
