C++ • Переставлення

Тема 8 • Функції переставлення елементів

Міняємо місцями
та розвертаємо ділянку

Значення зберігаються, змінюється їхнє розташування

Два різні прийоми

Обмін: два елементи отримують значення один одного.

Розворот: кілька пар від країв до середини міняються місцями.

У всіх випадках кількість елементів та їхній набір не змінюються.

Обмін двох елементів: три присвоювання

Нехай arr[1] = 8, arr[4] = 7. Щоб обміняти їх, спочатку збережемо одне значення в тимчасовій змінній temp.

int temp = arr[1];  // temp = 8
arr[1] = arr[4];    // arr[1] = 7
arr[4] = temp;      // arr[4] = 8

Без temp команда arr[1] = arr[4] затерла б початкову вісімку. Присвоювання не є одночасним обміном.

void SwapArr(int arr[], int n, int k1, int k2) {
    if (k1 >= 0 && k1 < n && k2 >= 0 && k2 < n) {
        int temp = arr[k1];
        arr[k1] = arr[k2];
        arr[k2] = temp;
    }
}

k1 та k2 є індексами двох елементів. Обмін можливий і коли k1 > k2. Якщо індекси однакові, значення залишиться тим самим.

Приклад 2

Розвертаємо ділянку від k1 до k2 включно

Обмінюємо лівий і правий елементи ділянки, потім пересуваємо лівий індекс на 1 вправо, правий на 1 вліво. Повторюємо, поки лівий індекс менший за правий.

void SwapArr(int arr[], int n, int k1, int k2) {
    if (k1 >= 0 && k1 <= k2 && k2 < n) {
        while (k1 < k2) {
            int temp = arr[k1];
            arr[k1] = arr[k2];
            arr[k2] = temp;
            k1++;
            k2--;
        }
    }
}

Це інший опис SwapArr з іншим призначенням. Не вставляйте обидва описи з однаковими параметрами в одну програму. Для першого прикладу потрібний обмін двох елементів, для другого розворот ділянки.

Було:  3 8 5 2 7
Обмін індексів 0 та 4: 7 8 5 2 3
Обмін індексів 1 та 3: 7 2 5 8 3
Середній елемент з індексом 2 не рухається

Увесь масив розвертаємо викликом SwapArr(mass, n, 0, n - 1);. Наприклад, для ділянки 1…3 у масиві 0 1 2 3 4 результат буде 0 3 2 1 4: елементи поза ділянкою не змінюються.

Повна програма з RandArr та PrintArr
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void RandArr(int arr[], int n, int a, int b) {
    for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "\n";
}

void SwapArr(int arr[], int n, int k1, int k2) {
    if (k1 >= 0 && k1 <= k2 && k2 < n) {
        while (k1 < k2) {
            int temp = arr[k1];
            arr[k1] = arr[k2];
            arr[k2] = temp;
            k1++;
            k2--;
        }
    }
}

int main() {
    const int capacity = 100;
    int mass[capacity];
    int n, a, b;
    cin >> n >> a >> b;
    if (n < 1 || n > capacity || a < -100 || a > 100 ||
        b < -100 || b > 100 || a > b) {
        cout << "Incorrect data\n";
    } else {
        srand(time(0));
        RandArr(mass, n, a, b);
        PrintArr(mass, n);
        SwapArr(mass, n, 0, n - 1);
        PrintArr(mass, n);
    }
    return 0;
}

Порядок введення: n, a, b. Обмеження: 1 ≤ n ≤ 100, −100 ≤ a ≤ b ≤ 100. Спочатку програма виводить початковий масив, потім результат або повідомлення.

Перед переставленням перевіряємо індекси

  • Обидва індекси належать діапазону 0…n − 1.
  • Результат пошуку −1 не є індексом елемента.
  • Для розвороту початкова ліва межа не більша за праву.
  • У розвороті включаємо обидві граничні позиції.
  • Якщо ділянка має один елемент, обмінів немає.

Після обміну значення за знайденими індексами можуть бути вже іншими. Не виконуємо повторний пошук між трьома присвоюваннями одного обміну.

Побач, як temp зберігає число

Від 1 до 10 цілих чисел від −100 до 100. Для зміни налаштувань почни новий розбір.

Тимчасова змінна temp

Рамки виділяють поточну пару. На проміжному кроці два елементи можуть мати однакові значення, але початкове число не втрачено: його зберігає temp.

Варіанти для учнів

Збережено всі 17 варіантів, функції та приклади переставлень. Для кожної програми використовуйте стандартний масив зі сталою місткістю та знайомі RandArr і PrintArr. Індекси шукайте до початку переставлення.

Якщо перший та останній відповідні елементи є тією самою позицією, обмін із собою допустимий. У непорожньому масиві мінімум і максимум завжди існують.

Варіант 1

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями перший та останній від'ємні елементи масиву. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 2

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями перший та останній додатні елементи масиву. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 3

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями перший та останній елементи масиву які кратні 3. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 4

За допомогою функцій: RandArr , PrintArr , IndMin , IndMax , SwapArr в одновимірному масиві поміняйте місцями перший мінімальний та перший максимальний елементи. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 5

За допомогою функцій: RandArr , PrintArr , IndMin , IndMax , SwapArr в одновимірному масиві поміняйте місцями останній мінімальний та останній максимальний елементи. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 6

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями перше та останнє однозначні числа. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

Однозначні числа мають модуль від 0 до 9, двозначні від 10 до 99. Мінус не є цифрою.

↑ До вибору варіанта

Варіант 7

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями перше та останнє двозначні числа. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

Однозначні числа мають модуль від 0 до 9, двозначні від 10 до 99. Мінус не є цифрою.

↑ До вибору варіанта

Варіант 8

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві поміняйте місцями його перше однозначне та останнє двозначне числа. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

Однозначні числа мають модуль від 0 до 9, двозначні від 10 до 99. Мінус не є цифрою.

↑ До вибору варіанта

Варіант 9

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , IsPrime, SwapArr в одновимірному масиві поміняйте місцями його перше та останнє прості числа. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

↑ До вибору варіанта

Варіант 10

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , IsFib, SwapArr в одновимірному масиві поміняйте місцями його перше та останнє числа Фібоначчі. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

Для цієї вправи числа Фібоначчі починаються з 0, 1, 1, 2, 3, 5… Від’ємні не підходять.

↑ До вибору варіанта

Варіант 11

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві переставте у зворотному порядку всі його елементи між першим та останнім від'ємними елементами. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

У цій вправі розвертаємо ділянку включно з обома знайденими граничними елементами. Спочатку визначаємо ліву й праву межі за їхніми індексами. Якщо вони збігаються, масив не змінюється.

↑ До вибору варіанта

Варіант 12

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , SwapArr в одновимірному масиві переставте у зворотному порядку всі його елементи між першим та останнім елементами, що кратні 5. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

У цій вправі розвертаємо ділянку включно з обома знайденими граничними елементами. Спочатку визначаємо ліву й праву межі за їхніми індексами. Якщо вони збігаються, масив не змінюється.

↑ До вибору варіанта

Варіант 13

За допомогою функцій: RandArr , PrintArr , IndMin , IndMax , SwapArr в одновимірному масиві переставте у зворотному порядку його елементи між першим мінімальним та останнім максимальним. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

У цій вправі розвертаємо ділянку включно з обома знайденими граничними елементами. Спочатку визначаємо ліву й праву межі за їхніми індексами. Якщо вони збігаються, масив не змінюється.

Якщо індекс мінімуму виявився правіше від індексу максимуму, поміняйте місцями самі індекси перед викликом функції розвороту.

↑ До вибору варіанта

Варіант 14

За допомогою функцій: RandArr , PrintArr , FindFirst , FindLast , IsPrime, SwapArr в одновимірному масиві переставте у зворотному порядку його елементи між першим та останнім простими числами. Якщо хоча б один із елементів не знайдено, то вивести повідомлення.

У цій вправі розвертаємо ділянку включно з обома знайденими граничними елементами. Спочатку визначаємо ліву й праву межі за їхніми індексами. Якщо вони збігаються, масив не змінюється.

↑ До вибору варіанта

Варіант 15

За допомогою функції RandArr заповніть одновимірний масив випадковими цілими числами.

За допомогою функції PrintArr виведіть масив на екран.

За допомогою функції SwapArr в одновимірному масиві переставте елементи його половин у зворотному порядку.

Для парної кількості елементів, наприклад, було (0 1 2 3 4 5 6 7), стало (3 2 1 0 7 6 5 4).

Для непарної кількості елементів, наприклад, було (0 1 2 3 4 5 6 7 8), стало (3 2 1 0 8 7 6 5 4).

Збережено саме наведене правило: перша частина має n / 2 елементів, друга n − n / 2. За непарної довжини середній елемент входить у другу частину та рухається разом із нею. Кожну частину розвертаємо окремо, а не міняємо частини місцями.

↑ До вибору варіанта

Варіант 16

За допомогою функції RandArr заповніть одновимірний масив випадковими цілими числами.

За допомогою функції PrintArr виведіть масив на екран.

Напишіть функцію з прототипом void SwapArr (int* arr, int n), яка міняє місцями його половини таким чином:

Для парної кількості елементів, наприклад, було (0 1 2 3 4 5 6 7 8 9), стало (5 6 7 8 9 0 1 2 3 4).

Для непарної кількості елементів, наприклад, було (0 1 2 3 4 5 6 7 8), стало (5 6 7 8 0 1 2 3 4).

За непарного n перша частина має n / 2 + 1 елементів, друга n / 2. У результаті спочатку стоїть друга частина, потім перша. Центральний елемент не залишається на місці. Це правило прямо випливає з наведеного прикладу.

↑ До вибору варіанта

Варіант 17

За допомогою функції RandArr заповніть одновимірний масив з парної кількості елементів випадковими цілими числами.

За допомогою функції PrintArr виведіть масив на екран.

Якщо в масиві непарна кількість елементів, то вивести повідомлення.

Напишіть функцію з прототипом void SwapArr (int* arr, int n), яка міняє місцями його елементи таким чином: наприклад, було 0 1 2 3 4 5 6 7 8 9 стало 1 0 3 2 5 4 7 6 9 8. Тобто перший з другим, третій з четвертим ...

Введену n перевіряємо до переставлення. Якщо n непарна, виводимо повідомлення; інакше обмінюємо сусідні пари з індексами (0, 1), (2, 3), (4, 5) тощо.

↑ До вибору варіанта

Перевір себе

Навіщо потрібна temp?

Щоб зберегти значення, яке буде затерте наступним присвоюванням.

Чи змінюється довжина масиву?

Ні. Міняються місцями наявні значення.

Коли припиняємо розворот?

Коли k1 більше або дорівнює k2. Непарна середня позиція залишається на місці всередині цієї ділянки.

Чи можна викликати обмін, якщо пошук повернув −1?

Ні. Спочатку перевіряємо, чи обидва елементи знайдені.

Обмін країв є тим самим, що розворот?

Лише для ділянки з двох або трьох елементів. У довшій ділянці після обміну країв потрібно також обмінювати внутрішні пари.