Циклический сдвиг

Инвертирование массива

Объединение двух массивов с чередованием элементов

Требуется объединить два массива одинакового размера

A = (a₀, a₁,, a_n-1) и B = (b₀, b₁,, b_n-1) в один массив C = (a₀, b₀, a₁, b₁,…,a_n-1, b_n-1).

Элементами массива С с четными индексами являются элементы массива A:

c₀ = a₀, с₂ = a₁,…, с_2i = a _i,…,

элементами с нечетными индексами – элементы массива B:

c₁ = b₀, c₃ = b₁…, …, с_2i-1 = b_i,…

Таким образом, требуется организовать цикл и выполнить операции:

с_2i= a_i, с_2i-1 = b_{i - 1}, для i = 0, 1, 2,, n – 1.

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

1. Объединение двух упорядоченных массивов в один с сохранением упорядоченности.

Требуется объединить два упорядоченных по убыванию массива A размером n и B размером m в один массив C размером n+m, также упорядоченный.

Схема алгоритма

• Начиная с первых элементов массивов A и B, сравниваем элементы A[i] и B[j]. В массив C пересылаем больший из них, например, A[i] (если выполняется условие A[i]>=B[j]).

• Далее продолжаем пересылать в массив C элементы массива A (индекс j при этом не меняется), пока очередной элемент массива A не будет меньше B[j] (условие A[i]>=B[j] не выполняется).

• Тогда начинаем пересылать в массив C элементы массива B (индекс i при этом не меняется), пока для какого-либо элемента массива B не будет снова выполнено условие (A[i]>=B[j]).

• Если один из массивов исчерпан (выполнено условие i > n или j > m), то оставшиеся элементы другого массива пересылаются друг за другом без всяких проверок.

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

• Требуется изменить порядок следования элементов массива размером n на обратный, т.е. поменять местами

0-й элемент массива с (n – 1)-м, 1-й с (n – 2)-м, i-й с (n – i+1)-м. Последними нужно поменять местами средние элементы, т.е. (n/2)-й и (n/2+1)-й.

• Требуется переместить элементы массива А размером n на m позиций вправо. При этом m элементов из конца массива перемещаются в начало.

А = (a₁, a₂, a₃, a₄,a₅) – исходный массив

A = (a₄, a₅, a₁, a₂,a₃) – после циклической перестановки на 2 позиции вправо.

• Вариант 1. Используется вспомогательный массив для временного хранения m последних элементов массива А. Далее оставшиеся элементы с 0-го по (n–m–1)-й смещаются вправо на m позиций. (Заметим, что перемещение нужно начинать с последнего из перемещаемых элементов, чтобы не испортить элементы массива А.) После этого в первые m элементов пересылаются элементы вспомогательного массива.

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

Дата добавления: 2014-12-07