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)

Дата добавления: 2014-01-06