7.2. Приклад алгоритму та програми

Скласти програму сортування масиву методом вибору.

Алгоритм програми

1. Вибрати перший елемент невідсортованої частини масиву і вважати його мінімальним; запам’ятати індекс цього елемента.

2. Для елементів від наступного після вибраного і до останнього повторювати такі дії:

   1. Порівняти вибраний елемент і поточний.

   2. Якщо вибраний елемент більший за поточний, запам’ятати поточний елемент як мінімальний, а його індекс — як індекс мінімального елемента.

   3. Поміняти місцями мінімальний і вибраний на кроці 1 елементи.

   4. Пересунути початок невідсортованої частини на одну позицію вправо.

Код програми

//ex7_9.cpp. Сортування методом вибору #include<iostream> #include<stdlib.h> #include<time.h> using namespace std; int n; //кількість елементів int a[10]; //масив, що сортується //=================== генерація масиву ======================= void input() { srand((unsigned)(time(NULL))); //ініціалізувати генератор //випадкових чисел cout<<"enter number of the components (<=10)"<<endl; cin>>n; //ввести кількість елементів массиву for(int i=0;i<n;i++) //генерувати масив a[i]=rand()%30; }

//============= виведення масиву ======================= void output() { for (int i=0;i<n;i++) //вивести проміжні результати cout<<a[i]<<" "; cout<<endl; } //==============сортування масиву вибором ================== void sort() { int min,imin; //мінімальний елемент і його індекс for(int i=0;i<n-1;++i) { min=a[i]; //пошук мінімального елемента в діапазоні від //i-го до останнього елемента imin=i; //індекс мінімального елемента for (int j=i+1;j<n;j++) //пошук мінімального елемента if (min>a[j]) { min=a[j]; imin=j; } a[imin]=a[i]; //обмін місцями мінімального та поточного //елементів a[i]=min; output(); //вивести проміжні результати } } //=============== головна функція ============================= int main() { cout<<"selection sort"<<endl; input(); //генерувати масив cout<<"generated array"<<endl; output(); //вивести масив cout<<"series of selection "<<endl; sort(); //сортувати масив cout<<"sorted array "<<endl; output(); //вивести відсортований масив system("pause"); }

Рис. 7.1. Результати роботи програми сортування масиву методом вибору

7.3. Варіанти завдань

1. Створити одновимірний массив, кількість елементів якого задана користувачем. У масиві поміняти місцями максимальний і мінімальний елементи. Надрукувати вхідний та вихідний масиви.

2. Створити одновимірний массив, кількість елементів якого задана користувачем. Упорядкувати масив у порядку зростання, підрахувати кількість переставлень елементів та їх порівнянь. Надрукувати вхідний та вихідний масив.

3. Заданий одновимірний масив А, кількість елементів якого задана користувачем. Побудувати масив В, кожний елемент якого обчислюється за формулою , де - максимальний елемент масиву А. Надрукувати вхідний та вихідний масиви.

4. Задані одновимірні масиви А, В з 10 чисел. Побудувати масив С, кожний елемент якого обчислюється за формулою:

В масиві С поміняти максимальний елемент і перший. Вивести масиви до переставлення елементів та після.

5. Створити одновимірний массив, кількість елементів якого задана користувачем. Визначити максимальне та мінімальне значення серед елементів із парними та непарними номерами.

6. Створити одновимірний массив, кількість елементів якого задана користувачем.

Обчислити суму елементів між максимальним та мінімальними значеннями масиву.

7. Створити два одновимірних массивів, кількість елементів яких задана користувачем. Здійснити обмін значень двох векторів та визначити їх скалярний добуток.

8. Створити два одновимірних массивів, кількість елементів яких задана користувачем. Знайти найменший серед тих елементів першого вектора, які співпадають із значеннями елементів другого вектора.

9. Заданий масив цілих чисел. Побудувати новий масив, в якому спочатку стоять числа, що діляться на 2, потім ті, що діляться на 2 та 3, потім на 3. Надрукувати вхідний та вихідний масиви.

10. Згенерувати значення елементів одновимірного масиву за допомогою генератора псевдовипадкових чисел, задавши кількість елементів масиву з клавіатури. Знайти мінімальний за значенням елемент і записати його на початок масиву, вивільнивши для нього місце шляхом зсуву елементів масиву вправо.

11. Створити масив, значеннями елементів якого є коефіцієнти многочлена . Знайти значення многочлена при заданому аргументу , похідної від многочлена при заданому та інтегралу від многочлена на заданому відрізку.

12. Ввести значення елементів одновимірного масиву, задавши попередньо їх кількість. Визначити кількість входжень до масиву значення кожного з його елементів.

13. В одновимірному масиві обчислити кількість елементів у найдовшій серії. Серія — це послідовність однакових елементів, розташованих поряд.

14. Згенерувати додатні та від’ємні псевдовипадкові значення елементів одновимірного масиву, ввівши кількість елементів з клавіатури. Переставити елементи масиву так, щоб спочатку були розташовані всі додатні елементи, потім всі від’ємні. Порядок серед додатних і від’ємних елементів має зберегтися.

15. У введеному з клавіатури одновимірному масиві знайти найбільший серед від’ємних та найменший серед додатних елементів масиву.

16. Побудувати одновимірний масив, значення елементів якого є числами Фібоначчі. Числа Фібоначчі формуються за правилом: кожне наступне число дорівнює сумі двох попередніх.

17. Задати два упорядкованих за зростанням одновимірних масиви. Побудувати упорядкований за зростанням третій масив злиттям двох заданих.

18. У селищі, де N будинків, розташованих уздовж прямої дороги з однієї сторони на рівних відстанях, прокладають телефонний зв’язок. Зазначено, скільки телефонних апаратів треба встановити в кожному будинку. Кожен телефон має бути з’єднаний з АТС окремим кабелем. Визначити, в якому будинку необхідно встановити АТС, щоб сумарна довжина кабелів була мінімальною.

19. Задані масиви А, В з цілих чисел, кількість вводиться з клавіатури. Побудувати масив С, в якому кожний елемент дорівнює найбільшому спільному дільнику чисел а_і, b_і. Використати алгоритм Евкліда.

20. Створити одновимірний массив, кількість елементів якого задана користувачем. Знайти максимальний серед парних елементів та мінімальний серед елементів з парними індексами. В масиві поміняти місцями знайдені максимальний та мінімальний елементи, надрукувати вхідний та вихідний масиви.

21. Створити одновимірний массив, кількість елементів якого задана користувачем. Впорядкувати масив за алгоритмами сортування вставкою (включенням), сортування вибором, сортування обміном (бульбашкове сортування). Визначити покажчики ефективності кожного з алгоритмів.

22. Створити одновимірний массив, кількість елементів якого задана користувачем. Значення елементів в масиві можуть повторюватися. Визначити індекс першого та останнього входження заданого числа в масив. Знайти число, яке повторюється найбільшу кількість разів.

23. Створити одновимірний массив, кількість елементів якого задана користувачем. Знайти суму елементів з парними індексами, добуток від’ємних елементів, максимальний елемент та його індекс серед додатних чисел, мінімальний елемент та його індекс серед елементів зх непарними індексами.

24. Обчислити суму та добуток двох многочленів:

та