Обмен значений элементов

Пример 3.12. В массиве поменять местами два соседних элемента с номерами k1 и k2.

Номера элементов, которые меняются местами, должны быть известны.

Дано: n – размер массива; A[n] – массив вещественных чисел; k1, k2 – номера элементов, подлежащих обмену.

Найти новый массив А размера n.

Фрагмент алгоритма решения задачи выглядит так:

x = A[k1]; A[k1] = A[k2]; А[k2] = x.

Здесь х – вспомогательная переменная, в которой сохраняется первоначальное значение элемента массива A[k1].

Тест

k1=2; k2 = 6

Данные		Результат
N=9	A=(3, 1, 10, 1, 6, 5, 12, 36, –15)	A = (3, 5, 10, 1, 6, 1, 12, 36, –15)

Усложним задачу.

Пример 3.13. Дан одномерный массив A, состоящий из 2n элементов. Поменять местами его половины.

Дано: 2  n – размер массива; A[n] – массив вещественных чисел.

Найти новый массив А размера 2  n.

Словесное описание алгоритма.

Пусть массив А состоит из 10 элементов, тогда n = 5. Из массива А(1, 12, 23, 3, 7, 13, 27, 6, 9, 11) нужно получить массив А(13, 27, 6, 9, 11, 1, 12, 23, 3, 7). Мы должны поменять местами элементы с номерами 1 и 6, 2 и 7, 3 и 8, 4 и 9, 5 и 10, иными словами 1 и n + 1, 2 и n +2, 3 и n + 3, 4 и n + 4, 5 и n + 5. Можно заметить, что элемент с номером i меняется местами с элементом с номером n + i. Поэтому, используя фрагмент алгоритма, приведенный в примере 3.12, можно применить такой цикл:

нц

Для i от 1 до n повторять

x = A[i]

A[i] = A[n + i]

A[n + i] = x

кц

Задачи для самостоятельного решения

1. Дан одномерный массив. Поменяйте местами:

а) первый и максимальный элементы массива;

б) второй и минимальный элементы массива;

в) первый и последний отрицательный элементы массива.

2. Дан одномерный массив А, состоящий из 2n элементов. Поменяйте местами его половины следующим образом: первый элемент поменять местами с последним, второй – с предпоследним и так далее.

3. Дан одномерный массив В, состоящий из 2n элементов. Переставьте его элементы по следующему правилу:

а) b[n + 1], b[n + 2], …, b[2n], b[1], b[2], …, b[n];

б) b[n + 1], b[n + 2], …, b[2n], b[n], b[n – 1],…, b[1];

в) b[1], b[n + 1], b[2], b[n + 2], …, b[n], b[2n];

4. Дан одномерный массив. Переставьте в обратном порядке элементы массива, расположенные между минимальным и максимальным элементами.

3.7. Удаление и вставка элементов массива

Пример 3.14. Удалить из массива, в котором все элементы различны, наибольший элемент. После удаления массив уплотнить, сдвинув все следующие за ним элементы, влево.

Дано: n – размер массива; A[n] – массив вещественных чисел.

Найти новый массив А размера n – 1.

Для решения задачи необходимо:

1) найти номер k наибольшего элемента массива. Эта задача решена в примере 3.5.

2) сдвинуть все элементы массива, начиная с k–го на один элемент влево.

Для того чтобы разработать алгоритм, рассмотрим конкретный пример. Пусть дан одномерный массив, состоящий из 10 элементов: А(6, 3, 7, 11, 2, 8, 1, 5). Номер наибольшего элемента равен 7 (k = 7), то есть, начиная с седьмого элемента, будем сдвигать элементы на один влево: седьмому элементу присвоим значение восьмого, восьмому элементу присвоим значение девятого, а девятому присвоим значение десятого элемента. На этом сдвиг заканчивается. Таким образом, сдвиг начинается с k–го элемента и заканчивается элементом с номером n – 1, где n –количество элементов в массиве. После этого количество элементов в массиве станет на один элемент меньше. Массив примет вид: А(6, 3, 4, 7, 11, 8, 1, 5).

Фрагмент алгоритма решения задачи:

Нахождение максимального элемента и его номера max = а[1] k = 1 нц Для i от 2 до n повторять Если а[i] > max то max = а[i] k = i Все если кц Сдвиг элементов массива нц Для i от = k до n – 1 повторять а[i] = а[i+1] кц Уменьшение количества элементов массива n = n – 1

Мы уже рассматривали подробно алгоритм нахождения максимального элемента массива и его номера. Покажем, как выполняется вторая часть алгоритма (сдвиг элементов массива) для тестового примера.

Тест

Данные		Результат
N = 8	A = (6, 3, 7, 11, 2, 8, 1,  5)	A = (6, 3, 7, 2, 8, 1, 5) N = 7

В массиве номер наибольшего элемента k = 4. Удаляем этот элемент.

i	Массив
4; 4 ≤ 7? Да	А = (6, 3, 7, 2, 2, 8, 1, 5)
5; 5 ≤ 7? Да	А = (6, 3, 7, 2, 8, 8, 1, 5)
6; 6 ≤ 7? Да	А = (6, 3, 7, 2, 8, 1, 1, 5)
7; 7 ≤ 7? Да	А = (6, 3, 7, 2, 8, 1, 5, 5)
8; 8 ≤ 7? Нет	Конец цикла. n = 8 – 1 = 7

Пример 3.15. Решить предыдущую задачу, считая, что максимальных элементов может быть несколько.

Дано n – размер массива; A[n] – массив вещественных чисел.

Найти: Новый массив А размера n – k, где k – количество удаленных элементов массива.

Когда необходимо удалять несколько элементов, то это лучше делать с конца массива, так как иначе нужно будет снова возвращаться к элементу, который только что удаляли. Эта проблема возникает в том случае, когда подряд идут два максимальных элемента: если первый удалить, то на его место снова встанет максимальный элемент. Просматривать массив с конца можно при помощи цикла с параметром, который имеет следующий вид:

нц

Для i от i_кон до i_нач шаг –1 повторять

<тело цикла>

кц

Значение переменной i уменьшается на единицу, начиная от i_кон до i_нач.

Кроме того, номер максимального элемента запоминать не будем, а просмотрим массив с конца, и если текущий элемент имеет максимальное значение, то удалим его, при этом значение счетчика удаленных элементов k будем увеличивать на 1. Для решения этой задачи фрагмент алгоритма для нахождения максимального элемента выглядит так:

Amax = a[1];

нц

Для i от 2 до n повторять {Нахождение максимального элемента}

Если a[i] > Amax то Amax = a[i];

Все если

кц

Просматриваем элементы, удаляем элемент, равный максимальному значению, подсчитываем количество удаленных элементов.

нц Для i от n до 1 шаг –1 повторять Если a[i] = Amax то a[i] = a[i + 1] k = k + 1 Все если кц n = n – k