Информатика. Ч.2 Майстренко А.В. - 40 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

массива позволяет решать большой набор задач, таких как поиск элементов, упорядочение и изменение
порядка следования элементов. Доступ к любому элементу массива осуществляется по его номеру (ин-
дексу). Поэтому для обращения к элементу массива используют имя переменной-массива и значение
номера элемента.
Выход
Вход
Summa = 0
k = 1, N, 1
Summa = Summa + x
k
Вывод
Summa
а)
Выход
Вход
Faktorial = 1
k = 2, N, 1
Faktorial = Faktorial * k
Вывод
Faktorial
б)
Рис. 22 Схемы алгоритмов вычисления суммы (а) и произведения (б)
Рассмотрим алгоритм нахождения наименьшего значения и его индекса в одномерном массиве, со-
стоящем из N элементов – М(N) (рис. 23). При выборе наименьшего значения вначале задают или вы-
бирают некое эталонное значение. Для массива этим значением может являться первый элемент. Затем
в цикле начинают перебирать все оставшиеся элементы массива и сравнивать каждый из них с эталон-
ным значением. В случае если текущий элемент оказывается лучше эталона, его принимают за новый
эталон. При выборе наибольшего значения поступают аналогичным образом.
4 Сортировка массивов
Под сортировкой понимается процесс размещения объектов некоторого списка в порядке следова-
ния их значений (по возрастанию или по убыванию). Во всем спектре задач, связанных с применением
ЭВМ, сортировке принадлежит исключительно важное место.
Для выполнения операций сортировки существует достаточное количество различных методов,
многие из которых, к сожалению, имеют довольно сложные алгоритмы решения. Наиболее простыми и,
в то же время, обладающими достаточной эффективностью, являются методы линейной и "пузырько-
вой" сортировки.
Алгоритм линейной сортировки заключается в следующем. Выбирается первый элемент ряда и по-
следовательно сравнивается со всеми стоящими за ним элементами. В случае если два сравниваемых
элемента расположены неверно друг по отношению к другу, то они меняются местами. И так до конца
ряда. В итоге на первом месте в ряду окажется либо самый маленький, либо самый большой элемент
ряда (в зависимости от сортировки: по убыванию или по возрастанию). Затем берется второй элемент
ряда и также сравнивается со всеми стоящими за ним элементами, в случае необходимости выполняется
перестановка. Подобные действия выполняются со всеми элементами ряда до конца. После всех опи-
санных действий получается отсортированный ряд. На рис. 24 приведен пример линейной сортировки
одномерного массива S(N) по возрастанию.
Несмотря на простоту программной реализации, производительность линейной сортировки невысо-
ка, так как для обработки любого n-элементного ряда требуется одно и то же число сравнений. К при-

Страницы