Печатать книгуПечатать книгу

§ 14. Преобразование элементов массива

Сайт: Профильное обучение
Курс: Информатика. 10 класс (Повышенный уровень)
Книга: § 14. Преобразование элементов массива
Напечатано:: Гость
Дата: Четверг, 28 Ноябрь 2024, 01:30

Оглавление

14.1. Основные задачи

Среди задач преобразования элементов массива можно выделить задачи следующих типов:

1. Изменение элементов массива в зависимости от условий. 
2. Обмен местами элементов в массиве. 
3. Удаление элемента из массива.
4. Вставка элемента в массив.

Рассмотрим подробнее каждую из задач.

Некоторые из задач преобразования массивов встречаются очень часто. Поэтому в класс vector были добавлены функции, позволяющие преобразовывать массивы.

Многие из функций для преобразования векторов аналогичны функциям преобразования строк как по синтаксису, так и выполняемому действию. Список функций можно посмотреть в Приложении к главе 1.

14.2. Изменение элементов массива в зависимости от условий

Пример 14.1. Задан одномерный массив целых чисел. Преобразовать его элементы по следующему правилу: положительные элементы заменить значением 2, а отрицательные — увеличить на 5.

Этапы выполнения задания

I. Исходные данные: одномерный массив а, количество элементов n.

II. Результат: преобразованный массив a.

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. В цикле проверяем текущий элемент. Если он положительный, то заменяем его на 2. Если отрицательный, то прибавляем к нему 5. Важно помнить, что отрицанием условия «элемент положительный» является условие «элемент не положительный», что подразумевает возможность равенства элемента 0 (нули не изменяются). Поэтому нужны два оператора ветвления для проверки условия задачи. 
3.  Вывод результата.

IV. Описание переменных: n – int, а – vector <int>.

Пример 14.1.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  for (int i = 0; i < n; i++){

    if (a[i] > 0)

      a[i] = 2;

    if (a[i] < 0)

      a[i] += 5 ;

  }

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

VI. Тестирование.

VII. Анализ результатов. Элементы 3 и 5 заменены на 2, элементы -2 и -1 увеличены на 5, элемент 0 остался неизмененным, что соответствует условию задачи.

14.3. Обмен местами элементов в массиве

Для обмена местами двух элементов массива можно использовать дополнительную переменную, которую называют буфером. Буферу присваивают значение одного из элементов массива, этому элементу присваивают значение другого элемента массива, затем второму элементу присваивают значение буфера.

buf := a[i];

a[i] := a[k];

a[k] := buf;

Для обмена элементов можно использовать встроенную функцию swap: swap(a[i], a[k]).

Пример 14.2. Задан одномерный массив целых чисел. Поменять местами максимальный и минимальный элементы массива. Предполагается, что каждый из них встречается в массиве только один раз.

Этапы выполнения задания

I. Исходные данные: одномерный массив а, количество элементов n.

II. Результат: преобразованный массив a.

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. Найдем максимальный элемент массива и его индекс (n_max). 
3. Найдем минимальный элемент массива и его индекс (n_min). 
4. Поменяем местами элементы, стоящие на местах n_max и n_min. 
5. Вывод результата.

IV. Описание переменных: n, n_min, n_max – int, а – vector <int>.

Пример 14.3. Задан одномерный массив целых чисел. Циклически сдвинуть все элементы массива влево на 1, первый на последнее место. Например, массив 1 2 3 4 5 будет преобразован в 2 3 4 5 1.

Этапы выполнения задания

I. Исходные данные: одномерный массив а, количество элементов n.

II. Результат: преобразованный массив a.

III. Алгоритм решения задачи.Описание переменных: n – int, а – vector <int>.

1. Ввод исходных данных. 
2. В цикле осуществим обмен соседних элементов.
3. Вывод результата.

Решением задачи 14.3 может быть также следующий алгоритм (пример 14.4):

1. Сохраним значение первого элемента в буферной переменной. 
2. В цикле сдвинем все элементы на 1 влево. 
3. Запишем значение буфера на последнее место в массиве.

Если в массив добавить еще один элемент в конце, то его можно использовать в качестве буферной переменной. В этом случае в цикле нужно будет сделать на 1 сдвиг больше. Затем удалить последний элемент. Удалить последний элемент можно с помощью команды pop_back().

Фрагменты программ в примере 14.5 показывают, как можно циклически сдвинуть элементы массива на 1 вправо (последний на первое место).

Осуществим обмен элементов  следующим образом:

a[i] = a[k]; a[k] = a[i];

Тогда мы потеряем значение элемента, стоящего изначально на месте a[i], и получим два элемента со значением, равным a[k].

Пример 14.2.

 V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  //поиск минимального элемента

  int n_min = 0;

  for (int i = 1; i < n; i++)

    if (a[i] < a[n_min])

      n_min=i;

  //поиск максимального элемента

  int n_max = 0;

  for (int i = 1; i < n; i++)

    if (a[i] > a[n_max])

      n_max=i;

  swap (a[n_min], a[n_max]);

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 14.3.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  for (int i = 0; i < n - 1; i++)

    swap (a[i], a[i + 1]);

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 14.4.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  a.push_back(a[0]);

  //сдвиг влево

  for (int i = 0; i < n; i++)

    a[i] = a[i + 1];

  a.pop_back();

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

Пример 14.5. Циклический сдвиг вправо на 1. Фрагменты программ:

for (int i = n - 1; i > 0; i--)

  swap (a[i], a[i - 1]);

  

a.push_back(a.back());

  //сдвиг вправо

for (int i = n - 1; i > 0; i--)

  a[i] = a[i - 1];

a.front() = a.back();

a.pop_back();

14.4. Понятие итератора

Итератор — обобщенный указатель [1], который позволяет пользователю перебирать элементы контейнера, без необходимости знать, как реализован сам контейнер.

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

Для вектора определены стандартные итераторы begin() и end(). Итератор begin() указывает на первый элемент в векторе. Итератор end() – на место после последнего элемента вектора.

Для любого итератора (it) доступны следующие операции (пример 14.6):

  • инкремент (it++) — для доступа к следующему элементу;
  • разыменование (*it) — для получения значения элемента;
  • операторы равенства (it1 = = it2) и неравенства (it1 != it2) для определения того, совпадают ли два итератора.

Для вектора итератор обеспечивает дополнительную функциональность:

  • добавление константы (it += 20 сдвинуться на 20 элементов вперед);
  • расстояние между итераторами
    (int dist = it2 - it1).

Начиная со стандарта C++11, обход вектора с помощью итератора может происходить следующим образом:

vector <int> a(n);

for (auto i: a)

  cout << i << " ";

Переменная i, тип которой определяется автоматически, будет поочередно получать значения элементов вектора. Таким образом можно получить значения элементов вектора, но невозможно получить индекс элемента. Такой цикл называют циклом foreach, или циклам, основанным на диапазоне.

[1] Указатель — переменная, обозначающая адрес памяти. Указатель предназначен для прямого обращения по адресу памяти к объекту, который расположен по этому адресу.

Для вектора определены также реверсивные (обратные) итераторы, которые позволяют перебирать элементы контейнера в обратном направлении. Для получения реверсивного итератора применяются функции rbegin() и rend(). Итератор rbegin() указывает на конец текущего вектора, а итератор rend() — на начало вектора.

Пример 14.6. Операции с итератором

vector <int> a = {1, 2, 3, 5, 9};

vector <int> :: iterator it;

Рассмотрим операции:

int x;

it = a.begin();

x = *it;

cout << x << endl;

Итератор it указывает на начало вектора. Значение переменной x — значение элемента вектора, на который указывает итератор. Будет выведено значение 1.

it++;

cout << *it << endl;

Итератор сместился на один элемент и теперь указывает на элемент с индексом 1, будет выведено значение 2.

it = a.begin() + 3;

cout << *it << endl;

Итератор сместился на 3 элемента от начала и указывает на элемент с индексом 3, будет выведено значение 5.

if (it == a.begin())

  cout << boolalpha << true;

else

  cout << boolalpha << false;

После предыдущей операции итератор указывает на элемент с индексом 3, поэтому будет выведено false.

int dist1 = it - a.begin();

int dist2 = a.end() - a.begin();

cout <<  dist1 << endl;

cout <<  dist2 << endl;

Будут выведены значения 3 и 5. Значение 5 — количество элементов в векторе.

Циклу foreach соответствует следующая запись цикла for:

vector <int> :: iterator i;

for (i = a.begin();

     i != a.end();

     i++)

  cout << *i << " ";

или

  cout << "a % b = " << d << endl;

  cout << "a % b = " << d << endl;

for (auto i = a.begin();

  cout << "a % b = " << d << endl;

     i != a.end();

     i++)

  cout << *i << " ";

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

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

erase(pos)

Удаляет один элемент

erase(first, last)

Удаляет элементы в диапазоне [first; last)

Параметрами функции erase являются итераторы. Если нужно удалить, например пятый элемент, то параметр функции может быть записан так: a.begin() + 5.

Пример 14.7. Задан одномерный массив целых чисел. Удалить из него все числа кратные 5. Сколько чисел удалили?

Этапы выполнения задания

I. Исходные данные: одномерный массив а, количество элементов n.

II. Результат: преобразованный массив a и количество удаленных чисел k.

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. Будем последовательно просматривать элементы массива. Если найдем число, кратное 5, то удалим его из массива, используя функцию erase. Так как количество удаляемых элементов заранее не известно, то применим цикл while. 
3. При удалении элемента счетчик k будем увеличивать на 1. 
4. Вывод результата.

IV. Описание переменных: n, k – int, а – vector <int>.

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

Пример 14.7.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  int i = 0, k = 0;

  while (i < a.size()){

    if (a[i] % 5 == 0){

      a.erase(a.begin() + i);

      k++;

    }

    else

      i++;

  }

  for (int i = 0; i < a.size(); i++)

    cout << a[i] << " ";

  cout << endl << "udalili ";

  cout << k << " elementov" << endl;

  return 0;

}

VI. Тестирование.

VII. Анализ результатов. Элементы 5, 15, 35, 10 и 30 кратны 5, поэтому их удалили из массива. Элементы 3 и 4 не кратны 5, поэтому они остались в массиве и сдвинулись в начало.

Пример 14.8.  Фрагмент программы:

for (int i = n - 1; i >=0; i-- )

  if (a[i] % 5 == 0)

    a.erase(a.begin() + i);

for (int i = 0; i < a.size(); i++)

  cout << a[i] << " ";

cout << endl << "udalili ";

cout << n - a.size();

cout << " elementov" << endl;

Счетчик k можно не использовать, количество удаленных элементов можно найти как разность между начальным количеством элементов n и длиной вектора после удаления элементов:

n – a.size().

14.6. Вставка элемента в массив

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

insert(pos, value)

Вставляет value перед элементом, на который указывает pos

insert(pos, value, count)

Вставляет count копий значения value перед элементом, на который указывает pos

insert(pos, first, last)

Вставляет элементы из диапазона [first, last) перед элементом, на который указывает pos

Параметры pos, first, last являются итераторами.

Пример 14.9. Задан массив целых чисел. Вставить число x на k-е место, если элемент a[k] кратен x.

Этапы выполнения задания

I. Исходные данные: одномерный массив а, количество элементов n, число, которое нужно вставить в массив x.

II. Результат: преобразованный массив a.

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. В цикле проверяем элементы массива. 
3.  Если текущий элемент кратен x, то вставляем число x в массив. 
4. Вывод результата.

IV. Описание переменных: n, x – int, а – vector <int>.

Пример 14.9.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  int x;

  cout << "x = ";

  cin >> x;

  for (int i = n - 1; i >= 0; i--)

    if (a[i] % x == 0)

      a.insert(a.begin() + i, x);

  for (int i = 0; i < a.size(); i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

VI. Тестирование.

VI. Анализ результатов. Число 5 вставлено перед значениями 10, 15, 30, 20, 45.

В программе используется обход массива с конца. Если в программе записать такой цикл:

for (int i = 0; i < a.size(); i++)

  if (a[i] % x == 0)

    a.insert(a.begin() + i, x);

то программа может зациклиться. Например, на нулевом месте стоит число 10, удовлетворяющее условию задачи. На его место вставили число 5. Число 10 сдвинулось на позицию 1 и будет опять проверяться на следующей итерации цикла, и опять сдвинется вправо.

Вопросы к параграфу

1. Какие типы задач преобразования массивов вы можете назвать?

2. Как можно поменять местами два элемента в массиве?

3. Как удалить элемент из массива?

4. Как вставить элемент в массив?

Упражнения

    

1. Можно ли в примере 14.1 заменить команды под № 1 командами под № 2?

1.  if (a[i] > 0)

      a[i] = 2;

    if (a[i] < 0)

      a[i] += 5 ;

 

2.  if (a[i] < 0)

      a[i] += 5 ;

    if (a[i] > 0)

      a[i] = 2;

В каких случаях программа будет давать неверный результат?

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

3. Задан одномерный массив из четного количества элементов. Поменяйте местами его «половинки»: 1 2 3 4 5 6 → 4 5 6 1 2 3.

4. В массиве записана информация об учащихся класса (фамилия и имя). Из класса выбыли два учащихся. Известны номера выбывших учащихся. Исключите их данные из массива.

5. Переставьте первый элемент массива на последнее место, второй — на первое, третий — на второе и т. д. 1 2 3 4 5 6 → 6 5 4 3 2 1.

6. Осуществите циклические сдвиги элементов в массиве.

1. На два элемента вправо 1 2 3 4 5 6 → 5 6 1 2 3 4.
2. На два элемента влево 1 2 3 4 5 6 → 3 4 5 6 1 2.
3. На k элементов вправо. Число k вводится.
4. На k элементов влево. Число k вводится.

7. Разбить элементы массива на группы по 4. В каждой четверке осуществить циклический сдвиг влево на 1. Первый на 4-е место. Если количество элементов в массиве не кратно 4, то для последней группы сдвиг осуществляется для того количества элементов, которое осталось.

8. Удалить из массива все отрицательные элементы. Вывести преобразованный массив.

9. Удалить из массива все элементы, которые являются полными квадратами (например, 9, 25, 64).

10. Удалить из массива все элементы, которые являются степенью 2.

11. Задан линейный массив, элементами которого являются слова. Удалите из него указанные слова.

1. Слова, начинающиеся на согласную букву. 
2. Слова, в которых менее 5 согласных. 
3. Слова, которые являются палиндромами.

12. Вставить элемент x в позицию x. Если x ≤ 0 или x ≥ n, вставить его на первое или последнее место соответственно.

13. Прочитайте числа из файла в массив. Если два соседних числа имеют разные знаки (одно положительное, а другое отрицательное), вставьте между ними число 0. Запишите полученный массив в файл.