Салаватский филиал угнту



Скачать 404.02 Kb.
страница7/9
Дата10.07.2019
Размер404.02 Kb.
Название файлаРуководство по выполнению лабораторных работ по курсу.RTF
ТипРуководство
1   2   3   4   5   6   7   8   9
Нахождение максимума и минимума.
При программирование матричных задач приходится сталкиваться с проблемой поиска минимального или максимального элемента одномерного массива или матрицы. Процесс поиска минимума отличается от поиска максимума лишь знаком отношения, поэтому рассмотрим лишь алгоритм нахождения минимального значения.

Для поиска минимального элемента одномерной последовательности (вектора) применяется следующих алгоритм :



  • в качестве минимального берется значение первого элемента массива

  • начиная со второго элемента и до последнего проверяется условие:

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

В качестве примера покажем фрагмент программы поиска минимального значения одномерного массива X

Min=x(1)

For i=2 To N

If x(i)

Next i


Сортировка одномерного массива.
Третья подзадача 5-ой лабораторной работы предлагает произвести упорядочивание одномерной последовательности.

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

Задача сортировки массивов является достаточно массовой при решении практических задач на ЭВМ, потому для ее решения разработан ряд алгоритмов.

Рассмотрим два из них: всплытие пузырька и сортировка по Шеллу.

Пузырьковая сортировка по возрастанию предполагает проведение следующих действий. Сравниваются между собой значения первого и второго элементов сортируемой последовательности. Меньшее ставится на первое место, большее на второе. Далее сравниваются второй и третий элементы массива. Как и ранее меньшее значение ставится на место второго элемента сортируемой последовательности, а большее на место третьего и т.д. В результате одного такого прохода два близлежащих элемента массива будут упорядочены. При необходимости эту операцию повторяют нужное число раз. В худшем случае для полной сортировки массива, состоящего из N элементов ,потребуется N-1 проходов ( случай когда минимальный элемент стоит на последнем месте ).В лучшем случае сортировка может не потребоваться совсем ( элементы первоначального массива расположены в требуемом порядке). При практической реализации сортировки путем всплытия пузырька можно повторить N-1 раз одиночный проход либо перед проведением очередного этапа упорядочивания проверять, была ли перестановка элементов на предыдущем ходе. Для этого в программе вводится вспомогательная переменная ,получающая контрольное значение (например, 1) при перестановке элементов массива. Сортировка повторяется лишь при значении вспомогательной переменной равной контрольному значению. Такой подход дает более экономичный алгоритм.

Приведем фрагмент программы, сортирующий одномерный массив Х по возрастанию.

For i=1 to N-1 ‘цикл N-1 проходов

For j=1 to N-1 ‘ цикл одного прохода

if x(j+1)

Next j,i


Во фрагменте программы для обмена значений использован оператор Swap, фрагмент приведен для не экономичного варианта реализации пузырьковой сортировки.

Кроме сортировки путем всплытия пузырька ,в практике программирования часто применяют сортировку по Шеллу. Смысл сортировки по возрастанию состоит в следующем. Начиная с первого и до последнего элементов массива определяется наименьший. Первый и найденный элемент меняются местами. Далее, начиная со второго и до последнего находят наименьший из оставшихся. Второй и найденный элементы меняются местами и т.д. Процедуру поиска минимального элемента и перестановку с текушим повторяют N-1 раз.

Приведем фрагмент программы ,сортирующий одномерный массив Х по возрастанию по Шеллу.

For i=1 to N-1 ‘цикл N-1 проходов

k=i:y=x(i)

For j=i+1 to N ‘ цикл поиска min и номера эл. if x(j)

Next j

Swap x(i),x(k)



Next i

Описанные выше приемы сортировки приемлемы не только для упорядочивания одномерного массива, но и для сортировки строк/столбцов/диагоналей матрицы. Так если требуется привести к нужному виду первую строку матрицы, следует в приведенных алгоритмах заменить Х(*) на А(1,*), здесь * заменяет индекс массива (i или j или k ...).

При сортировке последнего столбца матрицы следует в формулах использовать значения A(*,N). При сортировке элементов главной диагонали следует учитывать, что эти элементы фактически образуют одномерный массив A(I,I), и поэтому к ним можно применить ту же процедуру сортировки.



Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9


База данных защищена авторским правом ©nedocs.ru 2017
обратиться к администрации

    Главная страница