Звільняємо місце для нового числа
Є масив 3 12 5 8 9. Вставимо число 7 перед останнім елементом, його індекс k = 4. Число 9 пересунемо праворуч, а на звільнене місце запишемо 7.
Жоден початковий елемент не зникає. Решта чисел зберігають свій порядок.
Звичайний масив не збільшує свою місткість. Ми заздалегідь оголошуємо його із запасом. Змінна n показує кількість використаних комірок, а capacity позначає їхню загальну кількість.
Функція InsArr
// Перед викликом у масиві має бути вільна комірка.
void InsArr(int arr[], int& n, int d, int k) {
if (k >= 0 && k <= n) {
for (int i = n; i > k; i--) {
arr[i] = arr[i - 1];
}
arr[k] = d;
n++;
}
}Параметри: arr є масивом; n є кількістю використаних комірок; d є новим числом; k є індексом місця вставлення.
- Копіюємо елементи праворуч, починаючи з останнього:
arr[n] = arr[n - 1]. - Записуємо нове число:
arr[k] = d. - Збільшуємо кількість елементів:
n++. Завдякиint& nзмінюється змінна з головної програми.
Чому починаємо з кінця? Інакше першим копіюванням затремо число, яке ще потрібно перенести. Наприклад, у масиві 2 5 8 спочатку переносимо 8, потім 5, потім 2.
| Індекс k | Де з’явиться число |
|---|---|
| 0 | На початку, перед першим елементом |
| Від 1 до n − 1 | Перед елементом із цим індексом |
| n | У кінці, після останнього; зсув не потрібен |
Щоб вставити після елемента з індексом j, передайте j + 1. Для порожнього масиву n = 0 допустиме місце вставлення k = 0.
Перед кожним викликом потрібна умова n < capacity. Ця функція не отримує місткість, тому сама не може перевірити наявність вільної комірки. У повних програмах нижче запас гарантовано обмеженням початкового n.
Вставлення покроково
У моделі місткість дорівнює 9. Порожні комірки позначені рискою. Кожне натискання виконує один крок: копіювання, запис нового числа або збільшення n. Помаранчевим позначені комірки поточної дії.
Приклад 1 · Перед останнім однозначним числом
Однозначними вважаємо цілі числа від −9 до 9, зокрема 0. Знаходимо індекс останнього такого числа. Якщо пошук повернув −1, повідомляємо, що його немає. Інакше вводимо x і вставляємо його перед знайденим елементом.
int FindLast(int arr[], int n) {
for (int i = n - 1; i >= 0; i--) {
if (arr[i] >= -9 && arr[i] <= 9) return i;
}
return -1;
}| Початковий масив | x | Результат |
|---|---|---|
| 3 12 5 8 9 | 7 | 3 12 5 8 7 9 |
| 12 15 18 11 | Не вводимо | Однозначних немає |
| 2 5 8 | 1 | 2 5 1 8, перед останнім однозначним |
| 2 15 18 | 1 | 1 2 15 18, знайдений елемент є першим |
| 12 0 15 | 7 | 12 7 0 15 |
Це приклади можливих масивів. Випадкове заповнення не гарантує саме такі числа.
Повна програма C++
Введіть n від 1 до 100 і межі a та b: −100 ≤ a ≤ b ≤ 100. Наприклад: 5 1 20. Після пошуку програма попросить x, якщо потрібний елемент є. Місткість 300 комірок дає запас і для наступного прикладу. Кожну програму запускайте окремо.
#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 InsArr(int arr[], int& n, int d, int k) {
if (k >= 0 && k <= n) {
for (int i = n; i > k; i--) {
arr[i] = arr[i - 1];
}
arr[k] = d;
n++;
}
}
int FindLast(int arr[], int n) {
for (int i = n - 1; i >= 0; i--) {
if (arr[i] >= -9 && arr[i] <= 9) return i;
}
return -1;
}
int main() {
const int capacity = 300;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 1 || n > 100 || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int k = FindLast(mass, n);
if (k == -1) {
cout << "Однозначних елементів немає\n";
} else {
int x;
cout << "Введіть число для вставлення: ";
cin >> x;
InsArr(mass, n, x, k);
PrintArr(mass, n);
}
}
return 0;
}Приклад 2 · Перед і після кожного однозначного
Вводимо x. Для кожного початкового однозначного елемента вставляємо x з обох боків. Нові числа x повторно не перевіряємо, навіть якщо вони теж однозначні.
for (int i = n - 1; i >= 0; i--) {
if (mass[i] >= -9 && mass[i] <= 9) {
InsArr(mass, n, x, i + 1); // Спочатку після
InsArr(mass, n, x, i); // Потім перед
}
}Чому саме такий порядок
Перегляд починається з кінця початкового масиву. Змінна i зменшується, хоча n під час вставлень зростає. Елементи ліворуч залишаються на своїх місцях, тому наступне початкове число не пропустимо.
Спочатку вставляємо після, у позицію i + 1: тоді поточний елемент ще має індекс i. Потім вставляємо перед, у позицію i.
На кожне початкове число припадає щонайбільше два вставлення. Тому результат має не більше 3 · n₀ елементів, де n₀ є початковою кількістю. За n₀ ≤ 100 вистачить масиву з місткістю 300.
Якщо однозначних немає, масив не зміниться. Якщо всі числа однозначні, його використана частина збільшиться втричі. Наприклад, для 0 5 та x = 7 отримаємо 7 0 7 7 5 7.
Повна програма C++
Введіть n, a, b за тими самими правилами, потім x для вставлення.
#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 InsArr(int arr[], int& n, int d, int k) {
if (k >= 0 && k <= n) {
for (int i = n; i > k; i--) {
arr[i] = arr[i - 1];
}
arr[k] = d;
n++;
}
}
int main() {
const int capacity = 300;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 1 || n > 100 || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int x;
cout << "Введіть число для вставлення: ";
cin >> x;
for (int i = n - 1; i >= 0; i--) {
if (mass[i] >= -9 && mass[i] <= 9) {
InsArr(mass, n, x, i + 1); // Спочатку після
InsArr(mass, n, x, i); // Потім перед
}
}
PrintArr(mass, n);
}
return 0;
}Два вставлення за знайденими індексами
Якщо потрібно вставити числа перед двома різними початковими елементами, спочатку знайдіть обидва індекси. Виконайте вставлення перед елементом із більшим індексом, потім із меншим. Так менший індекс залишиться правильним.
Перед використанням результату пошуку перевірте, чи він не дорівнює −1. Лише після перевірки обчислюйте позицію «після» як індекс + 1: інакше −1 + 1 дасть 0 і призведе до помилкового вставлення на початок.
Варіанти для самостійної роботи
У кожному варіанті два окремі пункти. Кожен виконуйте для початкового масиву. Заповнюйте його функцією RandArr, виводьте функцією PrintArr, вставляйте число функцією InsArr. Використовуйте зазначені функції пошуку.
Заздалегідь передбачте запас. У наведених варіантах додається щонайбільше одне число на кожний початковий елемент, отже вистачить місткості 2 · n₀. Вставлені числа повторно не відбирайте. Якщо потрібних елементів немає, повідомте про це та залиште масив без змін.
Для роботи з цифрами від’ємного числа розглядайте його модуль, знак не є цифрою. Число 0 має одну цифру 0. Просте число є натуральним числом, більшим за 1, що має рівно два натуральні дільники.
Варіант 1
- Вставити число В перед останнім парним числом масиву. Додатково використовувати функцію FindLast.
- Вставити число В після кожного парного числа масиву.
Варіант 2
- Вставити число В після першого від’ємного числа масиву. Додатково використовувати функцію FindFirst.
- Вставити число В перед кожним від’ємним числом масиву.
Варіант 3
- Вставити число В у масив перед останнім числом, яке більше числа 20. Додатково використовувати функцію FindLast.
- Вставити число В у масив після кожного числа, яке більше числа Х.
Варіант 4
- Вставити число В у масив після першого числа, яке закінчується на цифру 1. Додатково використовувати функцію FindFirst.
- Вставити число В у масив перед кожним числом, яке закінчується на цифру С.
Уточнення: C є цифрою від 0 до 9.
↑ До вибору варіантаВаріант 5
- Вставити число В перед останнім максимальним числом масиву. Додатково використовувати функцію IndMax.
- Вставити число В після всіх максимальних чисел. Додатково використовувати функцію IndMax.
Уточнення: Збережіть значення максимуму початкового масиву до вставлень. У другому пункті вставляйте B після кожного початкового входження саме цього максимуму. Не шукайте новий максимум серед доданих чисел.
↑ До вибору варіантаВаріант 6
- Вставити число В після першого мінімального числа масиву. Додатково використовувати функцію IndMin.
- Вставити число В перед усіма мінімальними числами. Додатково використовувати функцію IndMin.
Уточнення: Збережіть значення мінімуму початкового масиву до вставлень. У другому пункті вставляйте B перед кожним початковим входженням саме цього мінімуму.
↑ До вибору варіантаВаріант 7
- Вставити число В перед останнім числом, яке закінчується на 3. Додатково використовувати функцію FindLast.
- Вставити число В після кожного числа, яке закінчується на 3.
Варіант 8
- Вставити число В у масив після першого числа, яке кратне 3 або 5. Додатково використовувати функцію FindFirst.
- Вставити число В у масив перед кожним числом, яке кратне 3 або 5.
Варіант 9
- Вставити число В у масив перед першим числом, яке кратне 3 та закінчується на цифру 2. Додатково використовувати функцію FindFirst.
- Вставити число В у масив після кожного числа, яке кратне числу Х та закінчується на цифру С.
Уточнення: У другому пункті X ≠ 0, а C є цифрою від 0 до 9. Остачу від ділення на 0 обчислювати не можна.
↑ До вибору варіантаВаріант 10
- Вставити число В у масив перед останнім числом, сума цифр якого дорівнює 10. Додатково використовувати функції FindLast та SumDig.
- Вставити число В у масив після кожного числа, сума цифр якого дорівнює Х. Додатково використовувати функцію SumDig.
Варіант 11
- Вставити число В у масив перед першим числом, у записі якого є цифра 5. Додатково використовувати функції FindFirst та NumDigCofA.
- Вставити число В у масив після кожного числа, у записі якого є цифра 5. Додатково використовувати функцію NumDigCofA.
Варіант 12
- Вставити число В у масив після останнього числа, у якого перша цифра дорівнює 3. Додатково використовувати функції FindLast та FirstDig.
- Вставити число В у масив перед кожним числом, у якого перша цифра дорівнює С. Додатково використовувати функцію FirstDig.
Уточнення: C є цифрою від 0 до 9. Число 0 вважаємо таким, що починається з цифри 0.
↑ До вибору варіантаВаріант 13
- Вставити число В у масив перед першим числом, яке складається з однакових цифр (включаючи однозначні). Додатково використовувати функції FindFirst, NumDig та NumDigCofA.
- Вставити число В у масив після кожного числа, яке складається з однакових цифр (включаючи однозначні). Додатково використовувати функції NumDigCofA та NumDig.
Варіант 14
- Вставити число В у масив перед першим простим числом. Додатково використовувати функції FindFirst та IsPrime.
- Вставити число В у масив після кожного простого числа. Додатково використовувати функцію IsPrime.
Варіант 15
- Вставити число В у масив перед останнім числом, у якого цифри розташовані за спаданням (321, 52). Додатково використовувати функцію FindLast та написати функцію з прототипом bool IsDesc(int n), яка визначає, чи розташовані цифри числа n за спаданням?
- Вставити число В у масив після кожного числа, у якого цифри розташовані за спаданням (321, 52). Додатково використовувати написану функцію IsDesc.
Уточнення: «За спаданням» означає строго: кожна наступна цифра менша за попередню. Наприклад, 321 підходить, 322 не підходить. Однозначні числа вважайте такими, що відповідають умові.
↑ До вибору варіантаВаріант 16
- Вставити число В у масив після останнього числа Фібоначчі. Додатково використовувати функції FindLast та IsFib.
- Вставити число В у масив перед кожним числом Фібоначчі. Додатково використовувати функцію IsFib.
Уточнення: Числа Фібоначчі тут: 0, 1, 1, 2, 3, 5, 8, 13, … . Від’ємні числа не є числами Фібоначчі.
↑ До вибору варіантаВаріант 17
- Вставити число В у масив після першого числа, яке починається та закінчується однаковими цифрами (окрім однозначних). Додатково використовувати функції FindFirst та FirstDig.
- Вставити число В у масив перед кожним числом, яке починається та закінчується однаковими цифрами (окрім однозначних). Додатково використовувати функцію FirstDig.