Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 1 з дисципліни: “Алгоритми та методи обчислень” на тему: “Аналіз складності алгоритмів” Мета лабораторної роботи Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. Теоретичні відомості В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, рішення деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними. Єдиного «правдивого» визначення поняття «алгоритм» немає. «Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до рішення поставленого завдання.» (А. Колмогоров) «Алгоритм - це точне розпорядження, яке визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.» (А. Марков) «Алгоритм - строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцеві команд.» (М. Угринович) «Алгоритм - це послідовність дій, спрямованих на одержання певного результату за кінцеве число кроків.» (ROXANstudio) «Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli]) «Алгоритм - однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для рішення нестандартних завдань.» Індивідуальне завдання Варіант 12 Продублювати всі непарні елементи заданої послідовності. Код програми #include <iostream> #include <conio.h> using namespace std; int* makeArray(int length) { int* array = new int[length]; for (int i(0); i < length; i++) { while (!(cin >> array[i])); } return array; } int numOfUnmatchedElements(int* array, int length) { int count = 0; for (int i(0); i < length; i++) { if (array[i] & 1) count++; } return count; } int* unmatchedElements(int array[], int length) { int count = numOfUnmatchedElements(array, length); int* newArray = new int[count]; for (int i(0), j(0); i < length && j < count; i++) { if (array[i] & 1) newArray[j++] = array[i];; } return newArray; } void printArray(int array[], int length) { for (int i(0); i < length; i++) { cout << array[i] << ' '; } } void clearMemory(int array[], int length) { delete[] array; } void main() { setlocale(LC_ALL, ""); int length; cout << "Введiть кiлькiсть елементiв у масивi: "; cin >> length; cout << "Введiть елементи масиву:" << endl; int* array = makeArray(length); cout << endl << "Введений масив:" << endl; printArray(array, length); int count = numOfUnmatchedElements(array, length); if (count) { cout << endl << "Непарнi числа:" << endl; int* newArray = unmatchedElements(array, length); printArray(newArray, count); cout << endl; clearMemory(newArray, length); } else cout << endl << "Непарних чисел немає" << endl; clearMemory(array, length); _getch(); } Результат виконання програми / / Висновок Я оволодів методикою аналізу складності основних алгоритмічних конструкцій, навчився обчислювати функцію трудомісткості, ознайомився з класифікацією алгоритмів на основі функції трудомісткості, опанував методику аналізу розроблених алгоритмів на предмет їх складності.