- •Зміст пояснювальної записки
- •Постановка задачі Організаційно-інформаційна сутність задачі [1]
- •Математична модель задачі [1]
- •Опис методів розв’язання задачі Метод перебору з поверненням [2]
- •Алгоритм перебору з поверненням
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму [2]
- •Опис програми Методи та засоби розробки програми
- •Сценарій роботи програми
- •Функціональна структура програми Специфікація модулів
- •Специфікація функцій
- •Технологія створення програми
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Висновок.
- •Список використаної літератури.
- •Додаток 1 cd та опис його змісту
Зображення даних в оперативній пам’яті [2]
Розв’язання задачі перебору з поверненням можна представити в оперативній пам’яті комп’ютера у вигляді дерева пошуку. Корінь дерева (0 рівень) є пустий вектор. Його сини являються множиною кандидатів для вибору , і , в загальному випадку, вузли -того рівня являються кандидатами на вибір при умові, що вибрали так, як вказують предки цих вузлів. Питання про те, чи має задача розв’язок, рівносильне питанню, являється які-небудь вузли дерева розв’язками. Шукаючи всі розв’язки, ми хочемо одержати всі такі вузли.
Інколи немає необхідності зберігати все дерево розв’язку. В цих випадках можна обійтися масивом, або чергою, тільки для зберігання поточного часткового розв’язку, але тоді необхідна реалізація повернення на крок назад та вибору наступного елементу, з множини доступних елементів для правильної роботи алгоритму.
Опис алгоритму програмного модуля [2]
Розв’язання задачі можливо продемонструвати за допомогою рекурсивної схеми реалізації алгоритму:
void Backtrack (< вектор , >) // - розмірність вектора
{
if (< вектор є розв’язком >)
< записати його >;
else
{
< обчислити >;
for (int k=0; k<n; n++) // n – кількість елементів в
Backtrack (< вектор , +1 >); //маючи
// додавання до вектора елементів
}
}
При виконанні такої функції будуть знайдені всі розв’язки задачі.
Оцінка складності алгоритму [2]
Оцінимо часову складність алгоритму. Дана схема реалізації перебору з поверненням призводить до експоненціальних алгоритмів. Дійсно, нехай всі розв’язки мають довжину , тоді необхідно дослідити близько вузлів дерева. Якщо значення обмежене деякою константою , то отримаємо близько вузлів.
Опис програми Методи та засоби розробки програми
Прикладні задачі даної розрахунково-графічної роботи реалізовані за допомогою високорівневої мови програмування C++ в середовищі Microsoft Visual Studio 2008. Кожна прикладна задача була виконано в новому проекті та виконується окремим exe-файлом. Графічне меню розрахунково-графічної роботи, з якого користувач може вибрати реалізацію прикладної задачі, було зроблено за допомогою мови гіпертекстової розмітки HTML та каскадних таблиць стилів CSS в середовищі Adobe Dreamweaver CS5.
Сценарій роботи програми
Користувач знаходиться в головному меню програми, зробленого за допомогою HTML. Йому доступні такі пункти меню:
Теоретичні відомості (опис роботи алгоритму перебору з поверненням та його застосування)
Прикладні задачі (список виконаних прикладних задач за даним алгоритмом)
Відомості про виконавця.
При виборі пункту «Теоретичні відомості», користувачу буде доступна інформація з наглядним описом роботи алгоритму і його використання в прикладних задачах.
При виборі певної задачі з пункту «Прикладні задачі», користувачеві буде доступна її умова, опис роботи програми, спосіб її реалізації, код програми з коментарями, тести(вхідні та вихідні дані) та можливість її запустити й перевірити правильність виконання.
При виборі пункту «Відомості про виконавця» користувачу буде доступна інформація про виконавця даної розрахунково-графічної роботи та список використаної літератури.