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

Вхідний файл на першому рядку містить ціле число - кількість міст. На наступних рядках файлу знаходиться пара цілих чисел: - вартість заправки в місті з номером , та вартість проїзду по дорозі, що сполучає місто та . Після виконання програма виводить на екран для жителів кожного міста найвигідніший спосіб заправки.

Приклад 1:

Кількість жителів:

Матриця вартості заправки:

Результат розв’язку:

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в -му місті (проти годинникової стрілки). Вартість: ( )*

Для жителів 2-го міста кращий спосіб заправки в -му місті (за годинниковою стрілкою). Вартість: ( )*

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в -му місті (проти годинникової стрілки). Вартість: ( )*

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в їх власному місті. Вартість:

Для жителів -го міста кращий спосіб заправки в -му місті (проти годинникової стрілки). Вартість: ( )*

*в дужках вказана вартість заправки в даному місті

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

Задачу комівояжера можна розв’язати алгоритмом перебору з поверненням. Для цього треба для кожного міста знайти таке місто, з`їздивши в яке і заправившись, витратиться менше грошей, це легко зробити перебравши всі можливі випадки для кожного міста спочатку у напрямі "за годинниковою стрілкою", а потім "проти годинникової стрілки".

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

1. Зчитати кількість міст

2. Для кожного міста зчитати вартість проїзду в наступне місто та вартість заправки

3. Пошук міста для найвигіднішої заправки:

   1. Для кожного міста виконати:

      1. Найвигідніший спосіб заправки для даного міста є те ж саме місто

      2. Вартість найвигіднішого способу заправки для даного міста є вартість заправки в тому ж самому місті

      3. Для всіх міст виконати:

         1. Порахувати та запам’ятати вартість заправки з даного міста з’їздивши до -того за годинниковою стрілкою

         2. Якщо запам’ятована вартість менша за найменшу вартість заправки для даного міста, то:

            1. Найвигідніший спосіб заправки для даного міста є -те

            2. Запам’ятована вартість є найвигіднішою вартістю заправки для даного міста

            3. Спосіб переміщення з найвигіднішою вартістю – «за годинниковою стрілкою»

         3. Порахувати та запам’ятати вартість заправки з даного міста з’їздивши до -того проти годинникової стрілки

         4. Якщо запам’ятована вартість менша за найменшу вартість заправки для даного міста, то:

            1. Найвигідніший спосіб заправки для даного міста є -те

            2. Запам’ятована вартість є найвигіднішою вартістю заправки для даного міста

            3. Спосіб переміщення з найвигіднішою вартістю – «проти годинникової стрілки»

4. Вивести результат на екран:

   1. Для жителів кожного міста вивести в якому місті їм краще заправитися, вартість заправки та спосіб проїзду до місця заправки

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

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

При обробці вхідних даних програма перебирає всі можливі варіанти заправки для жителів кожного міста. Отриманий результат відповідає найкращому можливому способу заправки для жителів кожного з міст. Отже програма працює вірно і знаходить необхідний розв’язок.

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

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

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

Для користування програмою необхідний початковий рівень володіння ПК та вміння користуватися веб-браузером.

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

Для інсталяції програми достатньо скопіювати папку «РГР Перебір з поверненням» з CD- диску в необхідну директорію на жорсткому диску користувача.

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

Під час тестування кінцевої версії програми при коректних вхідних даних аварійних ситуацій не виникало.

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

Щоб запустити програму необхідно в головній папці програми запустити файл «РГР Перебір з поверненням.html» за допомогою будь-якого веб-браузеру.

Рис 8. Відеокопії сторінок: а) Теоретичні відомості; б) Відомості про виконавця;

в) Сторінка розв’язаної задачі; г) Прикладні задачі

Користувач знаходиться в головному меню програми, зробленого за допомогою HTML. Йому доступні такі пункти меню:

• Теоретичні відомості (теоретичні данні про алгоритм перебору з поверненням)

• Прикладні задачі (список виконаних програм за даним алгоритмом)

• Відомості про виконавця (рис.8 б).

При виборі пункту «Теоретичні відомості» (рис.8 а), користувачу буде доступна інформація з наглядним описом роботи алгоритму і його використання в прикладних задачах.

При виборі пункту «Прикладні задачі» (рис.8 г), користувачеві доступний вибір реалізованих програм, також є можливість запустити виконання реалізованих програм та скачати архів з проект Microsoft Visual Studio 2008.

При виборі реалізованої програми з списку (рис.8 в) користувачу доступна умова задачі, формат вхідних та вихідних даних, опис реалізації алгоритму. Також користувач може запустити програму з розв’язком задачі, код програми, архів з проектом Microsoft Visual Studio 2008.