v Введення
Широке поширення ідей структурного програмування в останні 20-30 років справила великий вплив на теорію і практику програмування і призвело до перегляду ролі типу і структури даних при розробці відповідних алгоритмів і програм. У зв'язку з цим в останні десятиліття при виробництві складних програмних систем потрібна підготовка висококваліфікованих фахівців, які досконало володіють сучасною теорією побудови систем обробки даних. У цій теорії важливе місце займають методи організації та обробки даних. Рішення будь-якої задачі зводиться до обробки безлічі даних, які являють собою абстракцію деякого фрагмента реального світу.
Для вирішення конкретного завдання, з одного боку, необхідно вибрати відповідний рівень абстрагування, тобто визначити безліч даних, що представляють реальну ситуацію, що відноситься до задачі. З іншого боку, слід вибрати спосіб подання цих даних з урахуванням можливостей комп'ютера та мови програмування.
Таким чином, для створення програмного продукту, що реалізує алгоритм рішення завдання даної курсової роботи, нам необхідно володіти знаннями теорії структур, методів представлення даних на логічному (абстрактному) і фізичному (машинному) рівнях, а також ефективних алгоритмів обробки різних структур даних.
Також для того, що б створити дійсно ефективно працюючу програму, яка дає потрібний результат за потрібний час слід провести аналіз складності алгоритму по одному з відомих методів. Це дозволить уникнути створення програмного продукту, що не відповідає обов'язковим вимогам по ефективності програм.
Метою цієї курсової роботи є створення програмної реалізації алгоритму, який знаходить рішення геометричної головоломки: Y-пентамино. Гра "Пентамін" - це дуже захопливе і корисне заняття, розвиваюче безліч здібностей. Фігурки являють собою всі однозв'язний комбінації з п'яти квадратиків. Всього в одному наборі 12 фігур. Фігурки можна виготовити з паперу, картону, пластиліну, дерева, глини, або з пластмаси, в Загалом, з чого завгодно. Далі, беремо ці фігурки і починаємо збирати прямокутну область, розміром 6х10 квадратиків. Це завдання досить складна для обчислень вручну, але ЕОМ справляється з нею набагато швидше. Основні етапи створення програми, включаючи процес розробки алгоритму, вибору мови програмування, аналіз складності алгоритму і програми, наведені нижче.
Головною складністю, що виникає при розробці алгоритму рішення, є застосування рекурсії, точніше рекурсивного методу проб і помилок, з використанням алгоритму з поверненнями. Теоретичні відомості про ці методи наведені в наступному розділі. p> Програмний продукт, і сама реферат в цілому можуть бути застосовані як у наукових цілях, при аналізі швидкодії систем штучного інтелекту, так і в ширших цілях, наприклад, як програма-помічник, вбудована в основну середу-гру В«пентаминоВ». Програми такого роду допомагають знайти рішення головоломок, якщо користувач не може зробити цього самостійно.
В
v Теоретичні відомості, що стосуються методу
При вирішенні завдання, поставленої в курсовій роботі, слід застосувати два основні алгоритмів перебору: алгоритм з поверненнями назад (backtracking) і метод проб і помилок.
В§ Алгоритм з поверненнями тому:
Метод перебору з поверненнями дозволяє вирішувати практично незліченну безліч завдань, багатьом з яких не відомі інші алгоритми. Незважаючи на таке велике різноманіття переборних завдань, в основі їх вирішення є щось спільне, дозволяє застосувати даний метод. Таким чином перебір можна вважати практично універсальним методом переборних вирішення завдань. Наведемо загальну схему цього методу:
Рішення задачі методом перебору з поверненням будується конструктивно послідовним розширенням часткового вирішення. Якщо на конкретному кроці таке розширення провести не вдається, то відбувається повернення до більш короткого часткового рішенням, і спроби його розширити тривають. <В
{пошук одного рішення}
procedure backtracking (k: integer); {k - номер ходу}
begin
{ініціалізація вибору варіанта}
repeat
{вибір варинта}
if {варіант підходить} then
begin
{запис варіанту}
if {рішення не знайдено} then
begin
backtracking (k +1); {рекурсивний виклик}
if {рішення не знайдено} then
{стирання варіанту}
end
else
{висновок рішення}
end ;
until {варіантів немає} or {рішення знайдено}
end;
begin
{запис першого варіанту}
backtracking (1);
end.
До достоїнств схеми слід віднести спільність, простоту і логічність. Але вона має і недоліки. По-перше, треба самому робити запис першого варіанту, непогано б, щоб це робила сама процедура. Також у ній використовує цикл repeat: можна допустити поми...
