Информатика и выч. техника \ Информатика

Работа с массивами, элементами массивов и решение инженерных задач: Методические указания, страница 2

      IMax = i

    End If

  Next

Next

…

End Sub

12.Преобразование матрицы в одномерный массив

Обработка одномерных массивов происходит быстрее, чем двумерных того же размера.

Требуется переслать по столбцам элементы матрицы А размером VxМ в одномерный массив В того же размера с сохранением порядка следования элементов.

Открыв циклы по столбцам и строкам матрицы А, необходимо заполнить одномерный массив В. Индексацию элементов массива В будем вести следующим образом:

B((j-1) * N – 1) - это и есть то выражение, которое каждый раз вычисляется при обращении к элементу матрицы и даёт адрес элемента в памяти относительно адреса начала массива.

Sub Matr_in_Vect()

…

For j = 1 To M

  For i = 1 To N

    B((j - 1) * N - i) = A(i,j)

  Next

Next

…

End Sub

13.Удаление элемента из массива

Требуется удалить K-й элемент из массива B размером N.

Удалить элемент можно, сдвинув весь «хвост» массива, с (К+1)-ого элемента, т.е. Bi = Bi + 1 , где i = K,K + l,...,N - 1

Sub Delete()

…

For i = К То N – 1

  B(i) = B(i + 1)

Next

…

End Sub

14.Включение элемента в заданную позицию массива

Перед включением элемента в К-ю позицию необходимо раздвинуть массив В, т.е. передвинуть «хвост» на одну позицию вниз.

Перемещение элементов массива нужно начать с конца. Далее, К-му элементу присваивается вводимое значение X.

Число элементов массива увеличивается на 1, поэтому объявленный размер массива должен быть на 1 больше предполагаемого размера.

Sub Insert()

…

For i = N To К Step - 1

  B(i + 1) = B(i)

Next

B(K) = X

…

End Sub

15.Упорядочение массива по возрастанию (убыванию)

Требуется расположить элементы массива в порядке возрастания (убывания).Для решения этой задачи существует много методов. Рассмотрим два из них.

Первыйоснован на поиске минимального (максимального) элемента. Вначале найдём минимальный элемент массива и поменяем его местами с первым. Затем найдём минимальный элемент из оставшихся (кроме первого) и поменяем его местами со вторым. После нахождения минимального из последних двух элементов массива и размещения его на предпоследнем месте на последнем останется наибольший.

Замечание. При перестановке найденного минимального и 1-го элементов не нужна вспомогательная переменная, т.к. значение минимального элемента находится в переменной MIN.

Второй методупорядочения массива (так называемый метод «пузырька») по возрастанию (убыванию) основан на проверке значений всех пар соседних элементов (a1 с а2, а2 с а3, а3 с а4 и т.д.) и перестановке их, если значение правого меньше (больше) левого. Этот процесс повторяется до тех пор, пока массив не будет упорядочен. Формально требуется N-1 просмотров всего массива размером N для упорядочения его, например, по возрастанию, если наименьший элемент занимает N-e место.

ПРИМЕР (метод пузырька)

Sub возрастание_пузырёк()

…

For j = 1 To n – 1

  For i = 1 Tо n – j

    If a(i) > a(i + 1) Then

      temp = a(i)

      a(i) = a(i + 1)

      a(i - 1) = temp

    End If

  Next i

Next j

…

End Sub

16.Поиск заданного элемента упорядоченном массиве (бинарный поиск)

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

В массиве А требуется определить индекс К элемента, равного заданному значению В. Массив A упорядочен по возрастанию.

Идея алгоритма заключается в следующем. Заданное число В сравнивается со средним элементом массива А, имеющим индекс i = (i1 – i2) / 2, где i1 - нижняя граница, iN. - верхняя граница индексов (вначале i1 = 1, ii = N, где N - размер массива). Если A≠В, то далее поиск продолжается в одной из половин массива (исключая элемент Аi) в зависимости от результата сравнения Ai и В Для этого изменяется значение или i1 (i1 = i-1), или iN (iN = i-1). Заданное число B сравнивается со средним элементом в выбранной половине и т д.

ПРИМЕР  (поиск заданного элемента)

Sub поиск_заданного_элемента()

…

n1 = 1

nn = n

i = Int((n1 + nn) / 2

Do Until (a(i) = b)

  If b < a(i) Then

    nn = i – 1

  Else

    n1 = i + 1

  End If

  i = Int((n1 + nn) / 2)

Loop

…

End Sub

17.Циклический сдвиг элементов массива

Требуется переместить элементы массива A, состоящего из N элементов, вправо (влево) на М позиций. При этом М элементов из конца массива перемещается в начало. Например, результатом циклической перестановки исходного массива A=(a1, a2, а3, а4, a5) вправо на 2 позиции будет массив А=(а4, a5, а1, а2, а3).

Рассмотрим три варианта алгоритма решения задачи.

1. С использованием вспомогательного массива B размером, равным размеру исходного массива.

2. С использованием вспомогательного массива B размером М.

3. С использованием одной вспомогательной переменной.

В первом варианте «хвост» массива пересылается во вспомогательный массив (элементы аN-M+1,...,aN  переходят в элементы b1,...,bM). Все остальные элементы пересылаются за ними со сдвигом индекса на М (элементы а1,...,аN-M переходят в элементы bM+1,...,bM)

Во втором варианте « хвост» массива пересылается во вспомогательный массив (М элементов аN-M+1,…,aN пересылаются в массив В). Все остальные элементы А перемещаются вправо на М позиций (аi+M = a1, i = N-M, n - M-1,...1). после чего массив B копируется в первые М элементов A. Следует обратить внимание на обратный порядок перемещения элементов (с конца). Прямой порядок перемещения (с начала) привёл бы к искажению исходного массива.

В третьем варианте во вспомогательную переменную каждый раз пересылается последний элемент массива А, после чего все элементы сдвигаются вправо на одну позицию (в обратном порядке, т.е. с конца массива) и на место первого элемента помещается содержимое вспомогательной переменной. Эта процедура повторяется М раз.

ПРИМЕР (циклический сдвиг)

Sub циклический_сдвиг()

…

For i = 1 То m

  b(i) = a(n - m + i)

Next i

For i = m + 1 To n

  b(i) = a(i - m)

Next i

…

End Sub

Скачать файл