- •Рецензент: Писаренко э.В.
- •Введение
- •Алгоритмизация
- •1. Вычисление суммы (суммирование) элементов вектора
- •2. Вычисление произведения элементов вектора
- •Пример 3
- •3. Вычисление произведения двух векторов
- •4. Суммирование (вычитание) матриц
- •5. ВычислениЕ произведения матриц
- •6. Вычисление произведения матрицы на вектор
- •7. Вычисление единичной матрицы
- •8. Транспонирование матрицы
- •Aij пустая ячейка b aji
- •9. Инвертирование элементов вектора
- •10. Алгоритм поиска максимального ( или минималь-ного ) элемента вектора
- •11. Алгоритм сортировки (упорядочивания) элементов вектора или матрицы
- •12. Вычисление полинома по схеме горнера
- •13. Вычисление суммы членов ряда
- •Содержание
11. Алгоритм сортировки (упорядочивания) элементов вектора или матрицы
Сортировка означает перестановку элементов вектора или матрицы в определенном порядке (по возрастанию или по убыванию) в соответствии с их значениями.
Рассмотрим алгоритм сортировки (упорядочивания) элементов вектора, когда значение каждого последующего элемента вектора больше предыдущего. Например, пусть исходный вектор X={}6=(3, 4, 2, -1, 6, 0), тогда в результате сортировки получим вектор X=(-1, 0, 2, 3, 4, 6).
Существуют различные способы решения данной задачи. Рассмотрим один из них.
Процедура сортировки элементов вектора X по возрастанию их значений следующая.
Первый шаг
Среди N-1 элементов вектора X (за исключением ) произведем поиск минимального элемента вектора и поменяем его местами с первым элементом, если значение <. В результате выполнения первого шага сортировки получим следующий вектор X=(-1, 4, 2, 3, 6, 0).
Второй шаг
Среди N-2 элементов вектора X (за исключением , ) произведем поиск минимального элемента вектора и поменяем его местами со вторым элементом, если значение <. В результате выполнения второго шага сортировки получим вектор X=(-1, 0, 2, 3, 6, 4).
Очевидно, после выполнения N-1 шага (в нашем примере после 5 шагов) получим окончательный упорядоченный вектор X=(-1, 0, 2, 3, 4, 6).
Алгоритм упорядочивания по возрастанию элементов вектора показан на рис. 22. Данный алгоритм пригоден для упорядочивания элементов вектора по убыванию с очевидной заменой знака " > " на знак " < " в блоке проверки условия (рис. 22).
Рассмотрим алгоритм сортировки элементов матрицы.
Дана матрица A={}P*N . Необходимо упорядочить элементы столбцов матрицы А в порядке убывания. Алгоритм сортировки элементов матрицы для этого случая приведен на рис. 23.
Рис.22 |
Рис.23 |
12. Вычисление полинома по схеме горнера
Дан полином PN(x) порядка N.
y = PN(x)= ( 18 )
Порядок N, значение аргумента и коэффициенты () известны. Поставим задачу разработки эффективной схемы вычисления полинома y = PN().
Представим уравнение (18) в следующем виде:
( 19 )
Очевидно, уравнение Горнера (19) предполагает меньший объем арифметических операций, чем исходное уравнение (18).
Рассмотрим следующую процедуру вычисления полинома с использованием рекуррентной формулы (рис. 24):
,
для . ( 20 )
Действительно,
для
для ( 21 )
. . . . . . . . . . . . . . . . . . . . . .
для =PN()
Рис.24. Алгоритм вычисления полинома по схеме Горнера.