Міністерство освіти і науки Російської Федерації
Агентство з освіти
Тихоокеанський Державний Економічний Університет
Економічний інститут
Курсова робота
На тему: В«Пошук найкоротшого шляху пересування слона
з шахового полю В»
Перевірила: Виконав:
Прудникова Л.І., доцент ______ 121ПІ _________,
к.ф.-м.н , ______ Гоман Т.С.
Владивосток 2009
Зміст
Введення
Формальна постановка задачі
Методи рішення
Модульна організація програми
Загальна схема взаємодії модулів
Опис модулів
Текст програми
Керівництво користувача
Тестовий приклад гри
Висновок
Список літератури
Введення
Умова розв'язуваної задачі дослівно по завданням звучить наступним чином: В«знайти найкоротший шлях пересування слона по заданому клітинному полю, що з'єднують два заданих поля дошки В»
Метою представленої роботи є розробка програми "Пошук найкоротшого шляху", яке створює шахову дошку, знаходить найкоротший шлях пересування слона і відображає його.
Перед початком обчислення користувач повинен вказувати у програмі наступну інформацію:
- розмірність поля
- встановити слона на початкову позицію і вказати кінцеву (за допомогою миші)
Після цього програма повинна показати найкоротший шлях (шляхи) руху слона, виділяючи його іншим кольором.
Необхідно передбачити контроль цілісності даних, що вводяться.
Формальна постановка задачі
Методи рішення
Існує досить багато різних методів вирішення такого завдання, кожен з яких грунтується на своїх принципах і прийомах, має унікальні переваги і, відповідно, недоліки. У даній роботі був використаний метод знаходження найкоротшого шляху на графі.
1. Задаємо розмір поля n
2. Перевіримо, щоб слон і його місце розташування повинні знаходитися на полях одного кольору.
3. Утворюємо матрицю для розрахунку шляху розмірності n +1
4. З допомогою отриманої матриці щоб уникнути виходу за шахове поле заповнимо оздоблюють елементи значеннями false
5. Виберемо всі можливі клітини, коли слон з початкового місця розташування і точки призначення, використовуючи раніше отриману матрицю
6. Визначимо спільні точки цих двох множин:
а) якщо вони мають одну спільну точку, то існує єдиний найкоротший шлях в 2 ходи
б) якщо вони мають 2 спільні точки, то існує 2 різних найкоротших шляхи, довжиною в 2 ходи
в) якщо точок перетину більше 2, то слон досягає свого кінцевого місцеположення за 1 хід.
Модульна організація програми
Реал...
