Реалізація базових алгоритмів
Отже, в розділі 3, курсової роботи був обґрунтований вибір мови програмування, проаналізоване використання базових алгоритмів в додатку, з переліком використаних елементів бібліотек, а також розглянута реалізація програми на прикладі вхідного та вихідного інтерфейсів, при створенні яких були використані базові алгоритми та структури даних. Жадібний алгоритм реалізується при виборі користувачем… Читати ще >
Реалізація базових алгоритмів (реферат, курсова, диплом, контрольна)
При розробці системи пошуку оптимальної туристичної путівки, були використані такі базові алгоритми: динамічний масив, сортування, пошук оптимальної туристичної путівки та жадібний алгоритм.
Вхідний інтерфейс можна розділити на такі елементи:
- · ініціалізація даних користувача;
- · створення динамічного масиву путівок, які задовольняють вимоги користувача.
Після ознайомлення з параметрами вхідних даних, потрібно натиснути будь-яку клавішу, після чого з’явиться перше поле для введення текстових даних, яке слід ініціалізувати. Після завершення введення даних першого поля натиснути клавішу ENTER, після чого з’явиться друге поле для введення текстових даних. Користувач повинен ввести ще одне поле з текстовими даними, та три поля з числовими даними. Процес введення користувачем даних забезпечується методом ask () класу Travel_ticket:
void ask ().
{.
cout << endl;
cout << «Enter your data» << endl;
printf («|——————————————————————— «);
printf («|Enter your city — «);
cin >> city;
printf («|——————————————————————— «);
printf («|Enter your date of travelling: «);
cin >> period_start;
printf («|——————————————————————— «);
cout << «|Enter quantity of adults — «;
cin >> adults;
printf («|——————————————————————— «);
cout << «|Enter quantity of children — «;
cin >> children;
printf («|——————————————————————— «);
cout << «|Enter cost of pass — «;
cin >> vartist;
printf («|——————————————————————— «);
cout << endl;
}.
Далі введенні дані користувача перевіряються на наявність збігів з даними туристичних путівок, які наявні в розпорядженні програми, та обраховується їхня кількість. Потім, динамічно створюється масив, розмірність якого є кількістю даних туристичних путівок.
int size = 0;
for (int i = 0; i < size1; i++).
{.
if (user->get_cost () >= mas[i]->get_cost ()).
if (user->get_adults () get_adults ()).
if (user->get_child () get_adults ()).
if (user->Get_day ()Get_day ()&&user->Get_month ()==mas[i]->Get_month ()&&user->Get_year ()==mas[i]->Get_year ()).
if ((user->get_c (0) == mas[i]->get_c (0))&&(user->get_c (1) == mas[i]->get_c (1))).
{.
size++;
}.
}.
Travel_ticket **mas2 = (Travel_ticket**)malloc (size * sizeof (Travel_ticket*));
int j = 0;
for (int i = 0; i < size1; i++).
{.
if (user->get_cost () >= mas[i]->get_cost ()).
if (user->get_adults () get_adults ()).
if (user->get_child () get_adults ()).
if (user->Get_day () Get_day () && user->Get_month () == mas[i]->Get_month () && user->Get_year () == mas[i]->Get_year ()).
if ((user->get_c (0) == mas[i]->get_c (0)) && (user->get_c (1) == mas[i]->get_c (1))).
{.
if (j < size).
{.
mas2[j] = mas[i];
}.
j++;
}.
}.
Потім користувач потрапляє у меню де реалізовані наступні алгоритми :
- · сортування;
- · жадібний алгоритм.
Сортування здійснюється при виборі користувачем команди «Sort». Виконується сортування бульбашкою за вартістю туристичної путівки: від найбільшої вартості до найменшої.
for (int i = 1; i < size; ++ i).
{.
for (int j = size-1; j >=i; —j).
if (mas2[j-1]->get_cost () get_cost ()).
{.
temp = mas2[j-1];
mas2[j — 1] = mas2[j];
mas2[j] = temp;
}.
}.
Жадібний алгоритм реалізується при виборі користувачем команди меню «Greedy algorithm». Даний алгоритм знаходить максимальну кількість туристичних путівок, яку користувач може дозволити собі, враховуючи його суму грошей, та відбражає на екрані путівки, які входять у цю кількість.
int amount = user->get_cost ();
int *number = new int[size];
int *costs = new int[size];
for (int i = 1; i < size; ++i).
{.
for (int j = size — 1; j >= i; —j).
if (mas2[j — 1]->get_cost () get_cost ()).
{.
temp = mas2[j — 1];
mas2[j — 1] = mas2[j];
mas2[j] = temp;
}.
costs[i] = mas2[i]->get_cost ();
}.
int *q= new int[size];
for (int i = 0; i < size; i++).
q[i] = costs[i];
int *p=new int[size];
for (int i = 0; i.
{.
q[i] = 0;
p[i] = 0;
number[i] = 0;
}.
int num = 0;
for (int i = 0; i.
{.
num = 0;
if (costs[i] <= amount).
{.
number[i] = num += amount / costs[i];
amount %= costs[i];
if (amount ≠ 0 || amount == 0).
{.
q[i] = costs[i];
p[i] = num;
number[i] = num;
}.
}.
}.
if (amount>0).
printf («Amount of money is too small «);
else.
{.
printf («Quantity of passes — %d «, sum (number, size));
cout << endl;
for (int i = 0; i.
{.
if (q[i] ≠ 0 && p[i] ≠ 0).
{.
printf («%d — «, p[i]);
printf («%d — «, q[i]);
cout << endl << endl;
mas2[i]->Print ();
}.
}.
cout << endl;
}.
Вихідний інтерфейс можна розділити на такі елементи:
- · пошук оптимальної туристичної путівки;
- · виведення на екран.
У разі якщо користувач не обрав собі путівки в меню програма автоматично призначає оптимальною путівку з мінімальню вартістю.
min = mas2[0];
for (int i = 0; i < size; i++).
if (mas2[i]->get_cost () get_cost ()).
min = mas2[i];
За допомогою наступного фрагменту лістингу відбувається виведення знайденої оптимальної туристичної путівки на екран. Це забезпечує метод Print () класу Travel_ticket.
void Print ().
{.
printf («|——————————————————————| «);
cout << «|City — «<< city << «» <
printf («|——————————————————————| «);
cout << «|Period «<< endl;
cout << «from «<< period_start << «» << endl;
cout << «to «<< period_finish << «» << endl;
printf («|——————————————————————| «);
cout << «|Quantity of adults — «<< adults << endl;
printf («|——————————————————————| «);
cout << «|Quantity of children — «<< children << endl;
printf («|——————————————————————| «);
cout << «|Category of hotel — «<< category_hotel << endl;
printf («|——————————————————————| «);
cout << «|Location of hotel — «<< location_hotel << endl;
printf («|——————————————————————| «);
cout << «|Cost of pass — «<< vartist<< endl;
printf («|——————————————————————| «);
cout << «|Type of pass — «<< ticket << endl;
printf («|——————————————————————| «);
cout << «|Hotel — «<< hotel<< endl;
printf («|——————————————————————| «);
cout << endl << endl;};
Реалізація програми пошуку оптимальної туристичної путівки мовою С++
На прикладі пошуку оптимальної туристичної путівки можна продемонструвати роботу базових алгоритмів та структур даних. Натиснувши кнопку «ОК» створюється динамічний масив комірок лабіринту, а натиснувши кнопку «Знайти» відбувається використання алгоритму пошуку шляху, частиною якого є сортування. Приклад використання динамічного масиву, а також сортування, пошук туристичної путівки, та жадібний алгоритм — у додатку А.
Таким чином в програмі реалізовані вхідний та вихідний інтерфейси, та використані базові алгоритми: сортування, пошук туристичної путівки, динамічний масив та жадібний алгоритм.
Отже, в розділі 3, курсової роботи був обґрунтований вибір мови програмування, проаналізоване використання базових алгоритмів в додатку, з переліком використаних елементів бібліотек, а також розглянута реалізація програми на прикладі вхідного та вихідного інтерфейсів, при створенні яких були використані базові алгоритми та структури даних.