Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз складності алгоритмів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 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();
}
Результат виконання програми
/
/
Висновок
Я оволодів методикою аналізу складності основних алгоритмічних конструкцій, навчився обчислювати функцію трудомісткості, ознайомився з класифікацією алгоритмів на основі функції трудомісткості, опанував методику аналізу розроблених алгоритмів на предмет їх складності.
30.03.2016 11:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора