Зміст пояснювальної записки

Зміст пояснювальної записки 1

Постановка задачі 3

Організаційно-інформаційна сутність задачі [1] 3

Математична модель задачі [1] 3

Вхідні дані 3

Вихідні дані 3

Опис методів розв’язання задачі 4

Метод перебору з поверненням [2] 4

Алгоритм перебору з поверненням 4

Зображення даних в оперативній пам’яті [2] 4

Опис алгоритму програмного модуля [2] 5

Оцінка складності алгоритму [2] 5

Опис програми 5

Методи та засоби розробки програми 5

Сценарій роботи програми 5

Функціональна структура програми 6

Специфікація модулів 6

Специфікація функцій 6

Схема взаємодій функцій програми 8

Технологія створення програми 9

Застосування алгоритмів для прикладних задач 10

Задача про вісім ферзів 10

Умова задачі [2] 10

Вхідні та вихідні тести 10

Опис алгоритму методу 10

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

Відеокопії екрана 10

Аналіз достовірності результатів 10

Обхід конем шахової дошки 11

Умова задачі [2] 11

Вхідні та вихідні тести 11

Опис алгоритму методу 11

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

Відеокопії екрана 12

Аналіз достовірності результатів 12

Задача про лабіринт 12

Умова задачі [2] 12

Вхідні та вихідні тести 13

Опис алгоритму методу 14

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

Відеокопії екрана 15

Аналіз достовірності результатів 16

Задача комівояжера 16

Умова задачі [2] 16

Вхідні та вихідні тести 16

Опис алгоритму методу 17

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

Відеокопії екрана 18

Аналіз достовірності результатів 18

Задача про парламент 18

Умова задачі [2] 18

Вхідні та вихідні тести 19

Опис алгоритму методу 20

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

Відеокопії екрана 21

Аналіз достовірності результатів 22

Задача про автозаправку 22

Умова задачі [2] 22

Вхідні та вихідні тести 22

Опис алгоритму методу 22

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

Відеокопії екрана 23

Аналіз достовірності результатів 23

Порадник користувача 24

Область використання, рівень підготовки користувача. 24

Рекомендації по інсталяції програми 24

Аварійні ситуації під час роботи програми 24

Технологія користування програмою 24

Висновок. 25

Список використаної літератури. 25

Додаток 1 26

CD та опис його змісту 26

Постановка задачі Організаційно-інформаційна сутність задачі [1]

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

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

Розв’язок задачі методом перебору з поверненням будується конструктивно послідовним розширенням часткового розв’язку. Якщо на конкретному кроці таке розширення провести не вдається, то відбувається повернення до меншого часткового розв’язку, і спроби його розширити тривають. Для прискорення перебору з поверненням обчислення завжди намагаються організувати так, щоб була можливість відмовитися як можна раніше від якомога більшого числа завідомо невідповідних варіантів.