Алгоритмы обработки векторов
Одномерный массив (вектор) – это совокупность элементов, записанных в одну строку. Для доступа к любому элементу вектора нужно указать имя массива и индекс. Для набора нижнего индекса можно нажать кнопку Панель векторов и матриц на математической панели, после чего щелкнуть на кнопке Xn или использовать клавишу [, так как при работе с векторами и матрицами приходится часто ставить нижний индекс.
Обработка массивов охватывает большой класс задач, которые решаются разными способами. Алгоритмы обработки массивов включают в себя последовательную обработку каждого элемента массива. При работе с элементами массива можно выделить разные виды задач: суммирование элементов массива, нахождение произведения элементов, подсчет элементов в массиве, удовлетворяющих заданному условию, поиск элементов, сортировка элементов массива. Структурировать алгоритмы обработки векторов можно как:
алгоритмы анализа;
алгоритмы выборки;
алгоритмы преобразования элементов;
алгоритмы поиска;
алгоритмы сортировки.
Алгоритмы анализа
К алгоритмам анализа относятся алгоритмы, в которых находятся основные характеристики массива, например, сумма элементов, среднее арифметическое, произведение элементов, количество элементов с заданным свойством и т.д. В данных алгоритмах осуществляется просмотр всех элементов массива. Эти алгоритмы похожи на алгоритмы обработки последовательностей, отличие заключается в том, что в массиве одновременно доступны все его элементы. Рассмотрим эти алгоритмы.
Нахождение суммы элементов массива
Нахождение суммы элементов массива, удовлетворяющих некоторому условию
Найти сумму положительных элементов массива.
Нахождение произведения элементов массива
Нахождение количества элементов с заданным свойством
Найти количество элементов массива, кратных 5.
Алгоритмы выборки
Данные алгоритмы используются для решения задач, в которых требуется выбрать из исходного массива элементы с заданным свойством и переписать их в другой одномерный массив. Для формирования нового массива нужно использовать другой индекс (k), не совпадающий с индексом исходного массива (i).
Выбрать из массива X положительные элементы и переписать их в массив Y.
Переписать в массив Y элементы массива Х, стоящие на нечетных местах.
Нахождение номеров элементов с заданным свойством
Найти номера нулевых элементов массива.
Хотя эта задача явно не относится к задачам на выборку, но чтобы ее можно было реализовать в MathCAD’e, необходимо формировать массив, в который будут записываться номера нулевых элементов исходного массива.
Алгоритмы преобразования элементов
Эти алгоритмы предназначены для решения задач, в которых изменяются значения элементов массива, осуществляется сдвиг или перестановка элементов местами.
Изменение значений некоторых элементов
Утроить элементы массива, стоящие на чётных местах.
Циклический сдвиг
Cдвинуть элементы массива на 1 элемент, при этом первый элемент массива становится на место последнего.
Перестановка элементов массива в обратном порядке
Поиск в массиве
Поиск элемента в массиве предполагает, что необходимо найти первое вхождение некоторого значения в массив. Самой распространенной задачей поиска является задача нахождения максимального (минимального) элемента массива и его номера в массиве.
Поиск максимального элемента массива и его номера
Рассмотрим более рациональный способ нахождения максимума, в котором осуществляется поиск только номера максимального элемента, а по номеру можно узнать и значение максимального элемента.
Если массив содержит несколько элементов, равных максимальному (минимальному), то по данному алгоритму будет найдено первое значение максимума (минимума).
Существует большое количество разных задач, в которых нужно использовать алгоритм поиска номера максимального или минимального элементов массива. Например, найдем сумму элементов массива, расположенных после максимального элемента.
Еще одна группа задач сводится к поиску в массиве элемента с заданным значением. Для этого необязательно просматривать весь массив, нужно завершить цикл, как только будет найден элемент с заданным значением.
Рассмотрим следующую задачу: найти в массиве первый отрицательный элемент, или установить, что его нет. Будем просматривать массив, начиная с первого элемента. Цикл завершится в одном из двух случаев: нашли первый отрицательный элемент, тогда i<=n, или просмотрели все элементы массива и не нашли отрицательного элемента, тогда i>n.
Сортировка массива
Под сортировкой понимают процесс перестановки элементов массива в определённом порядке. Для числовых массивов это означает упорядочивание элементов массива либо по возрастанию, либо по убыванию.
Элементы массива можно сортировать:
по возрастанию. Каждый следующий элемент больше предыдущего
А1 < А2 < ... < An;
по убыванию. Каждый следующий элемент меньше предыдущего А1> А2 > ... > An.
Существует много различных методов сортировки. Рассмотрим два метода сортировки: алгоритм линейной сортировки и алгоритм сортировки простым выбором, позволяющие упорядочить массив, состоящий из n элементов, по возрастанию.
Алгоритм линейной сортировки
Принцип метода: сравниваем каждый элемент массива с первым элементом. Если элемент массива окажется меньше первого элемента, то меняем их местами, если нет - ничего не делаем. После одного такого просмотра массива на первой позиции будет стоять наименьший элемент, который в дальнейшем будет исключен из рассмотрения.
Затем сравниваем каждый элемент массива со вторым элементом, указанный процесс повторяется, и в результате на второй позиции будет стоять наименьший элемент среди оставшихся элементов и т. д. для всех элементов до (n-1) – го.
Алгоритм сортировки простым выбором
Принцип метода: на первом шаге находим в массиве элемент с наименьшим значением на интервале от первого элемента до n-го и меняем его местами с первым элементом. Наименьший элемент занимает окончательную позицию и в дальнейшем исключается из рассмотрения. На втором шаге находим элемент с наименьшим значением на интервале от второго элемента до n-го и меняем его местами со вторым элементом и т. д. для всех элементов до (n-1) -го.
