DIM A(N, M)
DO
DO
Описание и обработка матриц
Лекция 10
END
NEXT I
NEXT I
NEXT J
END
NEXT I
NEXT J
END IF
ELSE
DO
. . . . . . . . . . . . . . .
Сортировка вставками
END
NEXT I
NEXT I
NEXT J
SWAP S(K), S(I)
‘Вывод отсортированного массива
FOR I = 1 TO N
PRINT S(I); “ “;
Идея сортировки вставками в том, что начинают формировать новый отсортированный массив. И когда там помещено i элементов, то i + 1 элемент размещают среди них так, чтобы не нарушить порядок последовательности.
FOR J = 2 TO N
I = J – 1
IF A(I + 1) < A(I) THEN SWAP A(I + 1), A(I): I = I - 1
I = 0
LOOP WHILE I <> 0
‘Вывод отсортированного массива
FOR I = 1 TO N
PRINT S(I); “ “;
Метод «пузырька»
FOR I = 1 TO N-1
FOR J = 1 TO N-1
IF A(J + 1) < A(J) THEN SWAP A(J + 1), A(J)
‘Вывод отсортированного массива
FOR I = 1 TO N
PRINT S(I); “ “;
Приведенные алгоритмы называются квадратичными – т. к. они требуют порядка n*n действий. Существуют ряд алгоритмов сортировки, требующих выполнения меньшего числа операций. Но программы, реализующие эти алгоритмы, содержат большее количество операторов, чем в приведенных примерах.
Матрицей называется двумерный массив. То есть массив, имеющий два измерения. Из-за «определенности» матрицы – строго ограниченного набора данных (известно: количество элементов по горизонтали, вертикали, известен тип элементов) ее обработка ведется в 4 стандартных этапа.
I ЭТАП. Состоит в том, что необходимо задать размерность матрицы.
П ЭТАП. Состоит в формировании элементов матрицы.
Ш ЭТАП. Состоит в выполнении задания.
IV ЭТАП. Состоит в выводе на экран или печать элементов исходной и полученной матрицы.
Все этапы являются стандартными и однотипными. Рассмотрим их подробнее.
I этап. Задание количества строк и столбцов, определяющих общее количество элементов. Как правило, в условии задачи не дана строгая размерность матрицы, а даны лишь пределы размерностей. Например, N <= 15, M<=10. Следовательно, матрица может быть и 7х8 и 10х4 и т.д. Но перед началом обработки матрицы необходимо выделить в памяти место для хранения элементов матрицы. Можно выделить сразу максимально нужное количество ячеек памяти. Но оперативная память является важным элементом, влияющим на скорость выполнения программ и с ней необходимо аккуратно обращаться. Следовательно, необходимо выделять ровно то количество ячеек памяти, которое необходимо. Это достигается использование цикла с предусловием DO …LOOP UNTIL.
INPUT “Введите количество строк матрицы 1<=N<=15”; N
LOOP UNTIL N>=2 and N<=15
INPUT “Введите количество столбцов матрицы 1<=M<=15”; M
LOOP UNTIL M>=2 and M<=15
После ввода размерностей используемой матрицы в памяти выделяется место под хранение массива, для этого надо описать матрицу с помощью оператора DIM .
Имя и размерность матрицы, тип ее данных. определяются оператором DIM аналогично массивам.
П этап Формирование элементов матрицы может происходить двумя способами.
1 Ввод значений с клавиатуры. Ввод с клавиатуры осуществляется тогда, когда известны элементы матрицы. Из-за того, что матрица имеет два измерения ее обработку ведут посредством двух вложенных циклов.
FOR I=1 TO M
FOR J=1 TO N
INPUT “ ВВЕДИТЕ ЗНАЧЕНИЕ”, A(I,J)