28.6. Расчет среднего и дисперсии элементов в массивах

← 28.5. Расчет модуля вектора и нормы матрицы

28.7. Поиск минимальных или максимальных... →

Среднее значение Xmean одномерного массива (выборки), состоящего из n элементов, и его дисперсия D рассчитываются по известным формулам:

.

Корень квадратный из дисперсии называется среднеквадратичным отклонением S.

Блок-схема алгоритма приведена на рис. 28.12. Сначала считается среднее значение, а затем – дисперсия. Суммы накапливаются в циклах по переменной i – индексу суммирования. Циклы имеют одинаковые параметры, но объединять их, на первый взгляд, нельзя, так как второй цикл использует результат, появляющийся при завершении первого. Но если преобразовать формулу для дисперсии, раскрывая квадрат разности, то можно получить:

При этом появляется две суммы – сумма элементов массива и сумма их квадратов, которые накапливаются в одном цикле. Блок-схема этого варианта алгоритма приведена на рис. 28.13.

← 28.5. Расчет модуля вектора и нормы матрицы

28.7. Поиск минимальных или максимальных... →

28.7. Поиск минимальных или максимальных значений в массивах

← 28.6. Расчет среднего и дисперсии элементов в...

28.8. Алгоритмы упорядочивания элементов в... →

Поиск минимального значения элементов одномерного массива реализуется алгоритмом, блок-схема которого представлена на рис. 28.14 а. Для поиска используется вспомогательная переменная Xm, которой сначала присваивается значение, заведомо большее всех элементов массива (в данном алгоритме 10³⁸). Затем организуется цикл перебора всех элементов массива. В теле цикла величина каждого элемента сравнивается со значением Xm. Если она оказывается меньше, то ее значение присваивается переменной Xm, а индекс этого элемента присваивается переменной im. После завершения цикла im будет содержать индекс элемента с наименьшей величиной, а переменная Xm – его значение. Если в массиве содержится несколько минимальных значений одинаковой величины, то будет найдено первое. Если же условие выполнения действия в структуре «обход» записать как Xi<=Xm, то будет найдено последнее.

Для поиска максимального по величине элемента нужно переменной Xm изначально присвоить минимально возможное значение (например, -10³⁸), а условие в альтернативе изменить на противоположное: Xi > Xm.

Поиск минимального или максимального значений в двумерном массиве отличается только тем, что задается двойной цикл сканирования (рис. 28.14 б).

Можно легко совместить поиск минимального и максимального значения в одном цикле сканирования. Для этого необходимы две переменные Xmin и Xmax для запоминания текущих минимального и максимального значений и переменные imin и imax для запоминания индексов элементов.

← 28.6. Расчет среднего и дисперсии элементов в...

28.8. Алгоритмы упорядочивания элементов в... →

28.8. Алгоритмы упорядочивания элементов в массивах

← 28.7. Поиск минимальных или максимальных...

28.9. Умножение матрицы на вектор и матрицы на... →

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

Первый алгоритм достаточно прост по сути; он строится на основе изложенного в 28.7. Рассмотрим его на примере упорядочивания по возрастанию n элементов одномерного массива X. Он основан на следующих действиях.

Сначала находится минимальный элемент массива в ряду от первого до последнего, n-ного. Этот элемент Xm c индексом im обменивается местами с первым. Затем находится новый минимальный элемент в ряду от второго до последнего. Он обменивается местами со вторым. И так далее. Цикл поиска и обмена местами повторяется до предпоследнего элемента, т.е. n-1 раз. Блок схема этого алгоритма представлена на рис. 28.15.

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

Проанализируем работу этого алгоритма на примере массива из четырех элементов:

При первом исполнении основного цикла будет найден минимальный четвертый элемент и обменен местами с первым:

При втором прохождении будет найден минимальный третий элемент и обменен местами со вторым:

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

Более эффективным является другой алгоритм сортировки, называемый пузырьковым. Его блок-схема приведена на рис. 28.16. Он является более компактным, чем предыдущий. Проанализируем его работу на таком же примере. Для наглядности изобразим вертикальное расположение ячеек массива при возрастании номера сверху вниз.

Исходное состояние элементов массива следующее:

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

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

При последнем исполнении тела внешнего цикла внутренний цикл исполняется один раз и в нем переставляются местами третий и четвертый элементы;

Сортировка завершена.

Алгоритмы упорядочивания матриц оказываются более сложными. Приведем в качестве при-мера алгоритм перестановки строк матрицы, в результате которой средние значения элементов по строкам возрастают от первой строки к последней. Он представлен на рис. 28.17.

Матрица A имеет m строк и n столбцов. Сначала в цикле по индексу строки i рассчитываются средние значения по строкам; их значения записываются в массив S. Затем производится сортировка элементов массива S по возрастанию первым из описанных выше методом. При перестановке элементов массива S одновременно переставляются связанные с ними строки матрицы. После окончания сортировки массива S все строки матрицы A оказываются упорядочены нужным образом.

Второй алгоритм, представленный на рис. 28.18 упорядочивает элементы матрицы A из m строк и n столбцов так, чтобы они возрастали как по строкам, так и по столбцам. Для этого используется вспомогательный одномерный массив X. Сначала элементы матрицы A по строкам переписываются в одномерный массив X, затем упорядочиваются там пузырьковым методом, а затем переписываются обратно в той же последовательности по строкам. При переписывании данных из двумерного массива в одномерный и обратно использованы два разных способа установления соответствия между индексами двумерного и одномерного массивов. В первом случае индекс одномерного массива формируется как счетчик, который сначала обнуляется, а в теле цикла перезаписи увеличивается на единицу. Во втором случае используется соответствие между индексами i (строки) и j (столбца) матрицы и индексом k одномерного массива:

 k = j+(i-1)*n

Оба этих способа эквивалентны. На блок-схеме фрагмент упорядочивания одномерного массива не детализирован, т.к. он совпадает с приведенным на рис. 28.16.

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

← 28.7. Поиск минимальных или максимальных...

28.9. Умножение матрицы на вектор и матрицы на... →