Завдання Y пентаміно

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

v Введення
Широке поширення ідей структурного програмування в останні 20-30 років справила великий вплив на теорію і практику програмування і призвело до перегляду ролі типу і структури даних при розробці відповідних алгоритмів і програм. У зв'язку з цим в останні десятиліття при виробництві складних програмних систем потрібна підготовка висококваліфікованих фахівців, які досконало володіють сучасною теорією побудови систем обробки даних. У цій теорії важливе місце займають методи організації та обробки даних. Рішення будь-якої задачі зводиться до обробки безлічі даних, які являють собою абстракцію деякого фрагмента реального світу.
Для вирішення конкретного завдання, з одного боку, необхідно вибрати відповідний рівень абстрагування, тобто визначити безліч даних, які становлять реальну ситуацію, що відноситься до задачі. З іншого боку, слід вибрати спосіб представлення цих даних з урахуванням можливостей комп'ютера та мови програмування.
Таким чином, для створення програмного продукту, що реалізує алгоритм рішення завдання даної курсової роботи, нам необхідно мати знання теорії структур, методів представлення даних на логічному (абстрактному) і фізичному (машинному) рівнях, а також ефективних алгоритмів обробки різних структур даних.
Також для того, щоб створити дійсно ефективно працюючу програму, яка дає потрібний результат за потрібний час слід провести аналіз складності алгоритму по одному з відомих методів. Це дозволить уникнути створення програмного продукту, що не відповідає обов'язковим вимогам щодо ефективності програм.
Метою цієї курсової роботи є створення програмної реалізації алгоритму, який знаходить рішення геометричній головоломки: Y-пентаміно. Гра "Пентамін" - це дуже захоплююче і корисне заняття, розвиваюче безліч здібностей. Фігурки представляють собою всі однозв'язний комбінації з п'яти квадратиків. Всього в одному наборі 12 фігур. Фігурки можна виготовити з паперу, картону, пластиліну, дерева, глини, або з пластмаси, в загальному, з чого завгодно. Далі, беремо ці фігурки і починаємо збирати прямокутну область, розміром 6х10 квадратиків. Це завдання досить складна для обчислень вручну, але ЕОМ справляється з нею набагато швидше. Основні етапи створення програми, включаючи процес розробки алгоритму, вибору мови програмування, аналіз складності алгоритму і програми, наведені нижче.
Головною складністю, яка виникає при розробці алгоритму рішення, є застосування рекурсії, точніше рекурсивного методу проб і помилок, з використанням алгоритму з поверненнями. Теоретичні відомості про ці методи приведені в наступному розділі.
Програмний продукт, і сама курсова робота в цілому можуть бути застосовані як у наукових цілях, при аналізі швидкодії систем штучного інтелекту, так і в ширших цілях, наприклад, як програма-помічник, вбудована в основну середу-гру «пентаміно». Програми такого роду допомагають знайти рішення головоломок, якщо користувач не може зробити цього самостійно.
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: можна допустити помилку в формуванні умови виходу з циклу, особливо, якщо не знаєш закони де Моргана, до того ж іноді простіше використовувати цикл for, а якщо варіантів мало, можна обійтися взагалі без циклів. Спробуємо усунути вище наведені недоліки. Для розробки загальної схеми перебору з поверненнями скористаємося процедурою з задачі про лабіринті, просто слід її узагальнити:
{Пошук одного рішення}
procedure backtracking (k: integer); {k - номер ходу}
begin
{Запис варіанту}
if {рішення знайдено} then
{Висновок рішення}
else
{Перебір всіх варіантів}
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{Стирання варіанту}
end;
begin
backtracking (1);
end.
Зрозуміло дана схема також не ідеальна, але вона усуває зазначені вище недоліки. Також можна відповідно зробити схеми для інших класів переборних завдань. Спочатку схема для пошуку всіх рішень:
{Пошук всіх рішень}
procedure backtracking (k: integer); {k - номер ходу}
begin
{Запис варіанту}
if {рішення знайдено} then
{Запис рішення}
else
{Перебір всіх варіантів}
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{Стирання варіанту}
end;
Замість запису рішення, його можна виводити у вихідний файл, або обробляти іншим чином в залежності від умови задачі. Цю схему можна змінити, що перебували не всі рішення, а тільки одне оптимальне. Під оптимальністю рішення зазвичай розуміють, що для даного рішення деяка функція приймає або мінімальна, або мінімальне значення.
Розглянемо докладніше алгоритм перебору з поверненням на прикладі відомої задачі про вісім ферзя.
Скількома способами можна розставити 8 ферзів на шахівниці так, щоб вони не били один одного? Легенда приписує формулювання і рішення цього завдання "королю математиків" Гаусу. Він перший зумів відшукати всі 92 рішення.
Рішення. Відповідно до описаної раніше загальною схемою алгоритму перебору з поверненням запропоновану завдання можна було б вирішувати за наведеним нижче алгоритмом "Всі розстановки". По ньому ферзі розставляються послідовно на вертикалях з номерами від нуля і далі. У процесі виконання приписи можливі зняття ферзів з дошки (повернення).
Алгоритм "Все розстановки"
1. Вважаємо D = Ж, j = 0 (D - безліч рішень, j - поточний стовпець для чергового ферзя).
2. Намагаємося в стовпці j просунути вниз по вертикалі або новий (якщо стовпець j порожній), або вже наявний там ферзь на найближчу допустиму рядок. Якщо це зробити не вдалося, то переходимо до пункту 4.
3. J ¬ j +1. Якщо j <n -1, то переходимо до пункту 2. В іншому випадку j = n -1, тобто всі вертикалі вже зайняті. Знайдене часткове рішення запам'ятовуємо в множині D і переходимо до пункту 2.
4. J ¬ j -1, тобто знімаємо ферзь зі стовпця j і переходимо до попереднього стовпцю. Якщо j І 0, то виконуємо пункт 2. Інакше обчислення припиняємо. Рішення завдання знаходяться в множині D, яке, взагалі кажучи, може бути і порожнім.
§ Метод проб і помилок:
Розглянемо цей метод також на прикладі задачі про вісім ферзя ..
Процес розстановки ферзів може виглядати так. Поставимо перший ферзя на яку-небудь клітину. Потім поставимо другий ферзя на першу клітку і перевіримо, що йому не загрожує перший. Якщо загрожує, то пересунемо другого ферзя і знову перевіримо і так до тих пір, поки другий ферзь не виявиться на допустимій клітці. Потім будемо рухати третій ферзя і т.д.
У розглянутій задачі номером ходу i буде порядковий номер ферзя, а номером варіанту j - порядковий номер спроби встановити цього ферзя після того, як попередні ферзі встановлені. Може виявитися, що в ході розстановки 1-го ферзя всі варіанти будуть невдалими, тобто ми не зуміємо поставити його на дошку. У такому випадку ми повинні будемо повернутися на крок назад і встановити попереднього (i - 1)-го ферзя по-іншому, тобто перейти до наступного варіанта його розстановки. Очевидно, що для цього треба знати останній розглянутий варіант установки (i - 1)-го ферзя. Потім збільшуємо номер варіанта і продовжуємо перегляд варіантів установки цього ферзя.
Отже, процес розстановки ферзів виглядає наступним чином. Ми рухаємося вперед, збільшуючи номер ходу. Для кожного ходу рухаємося убік, підбираючи допустимий варіант, і йдемо вперед до наступного ходу, якщо варіант підібраний. Якщо неможливо підібрати варіант, то повертаємося на крок назад і продовжуємо рух убік, починаючи з наступного варіанта. Після установки останнього ферзя записуємо отримане рішення. У цих рухах вперед і назад за номерами ходів і полягає особливість схеми перебору.
Розглянемо приклад. Нехай шість ферзів розставлені на дошці, як показано на рис. 4.3, а). Для сьомого ферзя (i = 7) при перегляді варіантів по клітках у порядку (1,1), (1,2), ...,( 1,8), (2,1), (2,2),. .. перший підходящим варіантом є клітина (4,7 Встановимо ферзя на цю клітку. Тепер для восьмого ферзя не виявиться відповідного варіанту: 7-а горизонталь і 8-а вертикалі вільні, але діагональ (8 - 2) зайнята клітиною (2-3) . Повернімося на хід назад, приберемо 7-го ферзя з дошки і приступимо до його установки на іншу допустиму клітку. Перегляд варіантів, починається з клітини (4,8) і вона виявляється припустимою. Встановимо туди 7-го ферзя і перейдемо до наступного ходу - установці 8-го ферзя. Перегляд варіантів призводить до допустимої клітці (7,7). Всі ферзі розставлені, остаточна розстановка показана на рис. 4.3, б).
Як же реалізувати розглянутий алгоритм? Самий простий і самий трудомісткий за часом виконання - це метод прямого перебору. Першим ходом поставимо ферзя на яку-небудь клітину, витративши на це одиницю часу. Потім в наступному ході переглядаємо 64 можливих варіантів постановки чергового ферзя. Для кожного варіанта (i, j), i - номер горизонталі, j - номер вертикалі, необхідно перевірити по 8 клітин i-й горизонталі і j-й вертикалі, від 1 до 8 клітин для кожної діагоналі, що проходить через клітку (i, j ).
Таким чином, число переборів виявляється непомірно велікім.Учтем обставина, що на кожній горизонталі може бути встановлений тільки один ферзь. Тому перший ферзь встановимо на першій горизонталі, другий - на другий і т.д. Тоді для кожного /-го ходу залишиться всього лише вісім варіантів постановки ферзя, а перевірятися будуть клітини тільки на j-й вертикалі та двох діагоналях. Незважаючи на це, кількість перевірок залишається великим.
Якщо тепер взяти до уваги те, що не лише на кожній горизонталі, але на кожній вертикалі і кожної діагоналі може перебувати тільки один ферзь, кількість перевірок можна істотно скоротити. Для цього необхідно мати інформацію про стан («зайнято» - «вільно») 8 вертикалей, 15 висхідних (зліва знизу - направо вгору) і 15 низхідних (зліва зверху - праворуч вниз) діагоналей. З цією метою використовуємо три одновимірних масиву: а [8] - стан вертикалей, Ь [\ 5] - | стан висхідних діагоналей, з [\ 5] - стан спадних діагоналей. Тоді для кожного варіанта (i, j) необхідні тільки три перевірки. Постає питання: Як для варіанта (i, j) вибирати для перевірки елементи масивів а, Ь, с? Послідовний номер елемента а збігається з номером варіанту у. Звернемо увагу на те, що для кожної висхідній діагоналі сума (i + J) постійна: (1 + 1) = 2, (2 + 1) = = (1 + 1) = (1 + 2) = 3 і т.д . (8 + 8) = 16, ці суми змінюються від 2 до 16 (2,3,4 ,..., 15,16), а для кожної низхідній діагоналі постійна різниця (i-j): (8 - 1) = 7; (7 - 1) = (8 - 2) = 6; ...;( 1 - 8) = - 7, вони змінюються від 7 до - 7 (7,6 ,..., - 6, - 7 ). Це дозволяє для кожного варіанта (i, j) однозначно обчислювати індекси відповідних масивів з урахуванням меж зміни індексів.
Можливі дві умови задачі розстановки ферзів: знайти одну або всі можливі розстановки. Всього є 92 різні розстановки, але тільки 12 з них є незалежними, інші можна отримати поворотами і дзеркальними відображеннями дошки.
v Алгоритм рішення задачі
Словесний (змістовний) алгоритм вирішення задачі:
Початок
1. Виконати пункти 2-8; (v1)
2. Якщо не досягли меж дошки, то виконуємо пункт 3, інакше пункт 9; (z1)
3. Якщо сума кожного елемента i-ої фігури пентаміно і кожного поля дошки, починаючи з вихідної позиції j, не більше одиниці, то пункт 4, інакше пункт 2; (z2)
4. Надаємо відповідних елементів дошки значення i (тобто встановлюємо фігуру пентаміно на дошку); (v2)
5. Якщо i <12, то пункт 6, інакше 7; (z3)
6. Збільшуємо i на одиницю і перехід до пункту 2; (v3)
7. Висновок на екран одного рішення; (v4)
8. Обнуляємо значення i-ої фігури на дошці; (v5)
9. Якщо j <n, то пункт 1; (z4)
Кінець
Словесний алгоритм дає короткий опис програмної реалізації рішення задачі, і призначений із загальною схемою алгоритму. Зокрема в ньому не розглядається процес подання форми кожної фігури в пам'яті ЕОМ, так як це питання описується далі. Також існує неточність з приводу кількості циклів, так ка в програмі їх значно більше, через роботи з тривимірними масивами. Однак для зручності і наочності, я вважаю, цим можна знехтувати.
v Обгрунтування вибору структур даних
Перш ніж приступити до розробки алгоритму і створення програми, нам необхідно мати уявлення про спосіб представлення даних в ЕОМ. Тому першим питанням, при розробці програм, є вибір структур даних. У своїй програмі мені довелося застосувати послідовно дві структури для представлення в пам'яті фігур пентаміно. Спочатку кожна фігура була описана як рядок масиву geometry. Кількість стовпців в цьому масиві-25. Саме стільки необхідно для представлення двовимірного масиву 5х5. А кількість рядків відповідно дорівнює 12, тому що ми знаємо, що всього фігурок дванадцять.
Можливо, виникне питання: «Чому для представлення кожної фігури потрібно 25 чисел?» Справді, це досить багато, але якщо для кожної фігури створити окремий масив зі своєї "власної" розмірністю, то в пам'яті необхідно зберігати цей масив розмірностей для кожної фігури пентаміно і звертатися до них виключно за індексами масиву. А це крім того, що незручно в процесі відладки, до того ж досить громіздко і нітрохи не економить пам'ять. Внаслідок цього, я вважала за краще мати константних масив geometry [12] [25].
Однак, як вже було сказано, таке подання даних є тільки на початковому етапі роботи програми. Якщо при виконанні рекурсії, у звернення до підпрограмі, як фактичних параметрів виступає масив, розмірністю 12х25, то це надзвичайно знижує ефективність програми, економію пам'яті, а також швидкодію. Незважаючи на те, що сучасна обчислювальна система впорається навіть з найгіршим програмним варіантом алгоритму, цей факт варто враховувати. З цієї причини, мені довелося перевести масив geometry в структури типу масив записів. Кожна запис масиву має два поля: масив shape (5x5), в якому представлена ​​форма кожної фігури і змінна located. Вона служить чимось на зразок мітки на кожну фігуру, яка надає інформацію про те, чи варто фігура на дошці чи ні. З такою структурою даних працювати набагато зручніше так як при рекурсивному виклику процедури, ми передаємо всього лише поточний елемент масиву записів, тобто один запис.
Знову-таки, знову виникає питання: «Чому не можна було уявити фігури пентаміно в такому вигляді, не витрачаючи зайвої пам'яті на масив geometry?» Це можливо лише в тому випадку, якщо дані вводять з пристрою введення, але це дуже утомливо, так як їх обсяг досить великий. Також можна було зчитувати з файлу, але ці способи ідентичні за обсягом займаної пам'яті. Описувати ж кожне поле кожного запису у вигляді константи не дозволяють кошти мов програмування, як Turbo Pascal, так і Visual C + +.
Говорячи про вибір мови програмування, то це питання, що виникає відразу після розробки алгоритму. При виборі мови, я керувалася обраним представленням даних, властивостями алгоритму і особливостями завдання. Мій вибір припав на мову С + + в середовищі Microsoft Visual C + +, так як за моїми уявленнями саме в ній міститься найбільш гнучкі засоби для обробки різних даних, як завгодно великого обсягу. Опис підпрограм, написаних на цій мові, дані нижче і містить три підпрограми, що використовуються в програмі:

1. Підпрограма з масиву geometry формує структуру типу масив записів, використовувану далі в головній підпрограмі placing:
void forming ();
2. Підпрограма безпосередньо реалізує метод проб і помилок з використанням методу backtracking. Здійснює рекурсивне покриття прямокутної області nxm фігурами пентаміно і при знаходженні кожного рішення звертається до функції print:
void placing (int i);
3. Підпрограма здійснює вивід на екран різних даних, що використовуються і отримані у програмі:
void print ();
Доступ до функцій forming () здійснюється безпосередньо з основної функції main (), функція placing (int i) спочатку викликається у функції main, а потім відбувається рекурсивний виклик підпрограми.
v Програма
Далі наводиться безпосередньо сам текст вихідного коду програми, що реалізує алгоритм вирішення задачі Y-пентаміно.
# Include <iostream.h>
# Include <cmath>
# Include "pent.h"
void forming (int geo [12] [25]);
void placing (int);
void print (int geo [12] [25]);
int main ()
{/ / Масив, в якому кожен рядок, реалізує подання 1 фігури
int geometry [12] [25] = {1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ;
/ / Структура 1 фігури
/ / Прямокутна область розміщення фігур
/ / (Надалі поле розстановки) 6х10
/ / Clrscr (); / / очищення екрана
cout <<"beginning dates:" <<endl; / / вивід початкових даних
getch (); / / очікування натискання клавіші
/ / Підпрограма формування масиву фігур,
/ / З початкового масиву geometry
forming (geometry);
/ / Int kol = 10; int kol2 = 0; short b = 1;
/ / Int g =- 33, h = 48;
/ / Основна функція, що виконує всілякі розстановки фігур
/ / На полі розстановки
placing (1);
/ / Вивід даних (поле розстановки) на екран
print (geometry);
getch ();
/ / B? Print (kol, kol2): Print (kol, pow (kol, 2) + g);
/ / B? Prrint (kol, kol2): Prrint (kol, pow (kol, 2)-h);
return 0;
}
/ / Підпрограма формування масиву фігур,
/ / З початкового масиву geometry
void forming (int geo [12] [25])
{Struct pents
{Int shape [5] [5]; / / форма фігури
char located; / / знаходиться на дошці / не перебуває
} Image [12]; / / масив з 12 фігур
int h;
for (int i = 1; i <= 12; i + +) / / кількість фігур
{H = 1;
for (int j = 1; j <= 5; j + +) / / розмірність кожної фігури
for (int k = 1; k <= 5; k + +)
/ / Присвоєння масиву форматів кожної фігури,
/ / Значень з нгчальних даних
{Image [i]. Shape [j] [k] = geo [i] [h];
h + +;
}
}
for (i = 1; i <= 12; i + +)
/ / Поки жодна фігура не ледіт на полі розстановки,
/ / Тому значення "N"
image [i]. located = 'N';
}
/ / Основна функція, що виконує всілякі розстановки фігур
/ / На полі розстановки
void placing (int i) / / i-номер фігури
{Const static int n = 6, m = 10;
struct pents
{Int shape [5] [5]; / / форма фігури
char located; / / знаходиться на дошці / не перебуває
} Image [12]; int field [n] [m];
/ / Допоміжні лічильники і
/ / Ознака знаходження відповідного варіанту
int j1, h1, b;
/ / Цикл знаходження всіляких варіантів для i-ої фігури
for (int j = 1; j <= n; j + +)
{J1 = j;
/ / Переглядаємо кожен стовпець j-го рядка
for (int h = 1; h <= m; h + +)
{H1 = h; b = 1;
/ / Цикли доступу до елементів масиву формату кожної фігури
for (int k = 1; k <= 5; k + +)
{For (int l = 1; l <= 5; l + +)
/ / Якщо сума елементів масиву форми i-ої фігури
/ / І елементів масиву поля розстановки більше 1
/ / Тобто відбувається накладення фігур один на одного, то b присвоїти значення 0
{If (image [i]. Shape [k] [l] + field [j1] [h1]> 1) b = 0;
h1 + +;
}
j1 + +; h1 = h;
}
/ / Якщо не разу не відбулося накладення фігур, тобто фігура підходить,
/ / То вихід з циклу пошуку
/ / Тобто з циклу можливих вихідних позиції фігури по стовпцях
if (b == 1) break;
j1 = j;
}
if (b == 1)
/ / Присвоюємо полю розстановки підійшла нам фігуру
{For (int k = 1; k <= 5; k + +)
for (int l = 1; l <= 5; l + +)
if (image [i]. shape [k] [l] == 1) field [-j + k] [-l + h] = i;
/ / Поміняли ознака знаходиться на дошці / не перебуває
image [i]. located = 'Y';
/ / Якщо це не випадок з останньою фігурою,
/ / То рекурсією здійснюємо установку след.фігури
if (i <12) placing (+ + i);
/ / Else / / інакше, тобто якщо дійшли до посл.фігури (знайшли 1 варіант), висновок на екран
/ / Print ();
/ / Обнуляємо значення останньої поставленої фігури
/ / На полі расстановеі і шукаємо след.подходящій варіант
for (k = j; k <= 6; k + +)
for (int l = h; l <= 10; l + +) field [k] [l] = 0;
/ / Поміняли ознака знаходиться на дошці / не перебуває
image [i]. located = 'N';
}
} / / Виконуємо все вищесказане для кожної фігури,
/ / Устонавлівая її, знаходячи відповідний варіант і
/ / Видалення для последущего пошуку інших варіантів
}
/ / Вивід даних (поле розстановки) на екран
void print (int geo [12] [25])
{
for (int i = 1; i <12; i + +) {
for (int j = 1; j <25; j + +) / / координати поля розстановки
cout <<geo [i] [j];
cout <<endl;} / / безпосередній висновок
/ / Збереження формату виводу
}
Незважаючи на гнучкість вбудованих засобів мови С + + і його незаперечна зручність при створенні програм, він має ряд особливостей, часто ведуть до плутанини і помилок. Додані коментарі дозволяють уникнути цього. З цієї причини текст програми багато ними забезпечений.
v Тестування програми
У процесі тестування програми необхідно слід провести аналіз складності алгоритму та оцінку ефективності її роботи.
Проведемо цей аналіз з допомогою алгоритмічної заходи Колмогорова. Для оцінки логічної складності алгоритмів пропонується використовувати кількісну міру у вигляді повної ентропії (алгоритмічної міри кількості інформації за Колмогорова) двійковій послідовності

Ia (k, s) = n * H (k, s),
де H (k, s) = - ((k / n) log (k / n) + (s1 / n) log (s1 / n) + (s0 / n) log (s0 / n))
або Н (к, s) = - ((k / n) log (k / n) +2 (s / n) log (s / n));

n - загальне число виходів безумовних і умовних операторів змістовного алгоритму (граф-схеми),
к - число виходів безумовних операторів,
s1, - число «поодинокі» виходів умовних операторів,
S0 - число «нульових» виходів умовних операторів,
s - число умовних операторів (s = s1 = s0).
Ia (k, s) =- n ((k / n) log (k / n)) біт - частка логічної сложності1 алгоритму за безумовним операторам;
Ij (k, s) =-n (2 (s / n) log (s / n)) біт-частка логічної складності алгоритму за умовними операторам.
Ця формула є абсолютною логічну складність алгоритму, виміряну в двійкових одиницях (бітрейтом).
Обчислимо ці значення для нашого алгоритму:
n = 13; k = 5; s = s1 = s0 = 4;
k / n = 0.39; s / n = 0.31;
(K / n) log (k / n) =- 0.53; (s / n) log (s / n) =- 0.52;
Н (к, s) = - (-0.53 +2 (-0.52)) = 1.57; I (k, s) = 13 * 1.57 = 20.41 біт.
Враховуючи той факт, що кількість інформації, що витрачається при реалізації алгоритму рішення за методом повного перебору, складає близько 28.6, ми можемо сміливо стверджувати, що даний алгоритм досить ефективний. Безсумнівно, це не означає, що реалізована за цим алгоритмом програма ідеальна. Наприклад, її можна було оптимізувати, скоротивши кількість стовпців у масиві geometry на 8, так як останні вісім елементів ніде не використовуються. Однак, це алгоритмічна міра і багато ще залежить від реалізації алгоритму в програмному продукті.
У моїй задачі потрібно вивести всі можливі рішення, але незважаючи на те, що їх не так багато, як очікувалося (мабуть через те, що в умові завдання повороти фігур не передбачені), все-таки це займе багато місця. Так як тест програми полягає у виведенні меншої кількості результатів, то я наведу кілька прикладів виведення для області 6х10 і5х12.
6х10:
1)
1 1 1 2 2 3 4 4 5 5
6 6 1 2 3 3 3 4 4 5
7 6 1 2 2 3 8 8 4 5
7 6 6 9 9 9 10 8 8 5
7 7 9 9 10 10 10 8 11 11
7 12 12 12 12 12 10 11 11 11
2)
9 4 4 7 7 7 7 11 11 11
9 9 4 4 7 2 2 2 11 11
5 9 10 4 3 2 8 2 6 6
5 9 10 3 3 3 8 8 6 1
5 10 10 10 3 8 8 6 6 1
5 5 12 12 12 12 12 1 1 1
3)
11 11 12 10 9 9 9 1 1 1
11 11 12 10 10 10 9 9 1 червня
7 11 12 10 4 4 6 6 6 1
7 7 12 4 4 8 6 3 2 2
7 5 12 4 8 8 3 3 3 2
7 5 5 5 5 8 8 3 2 2
5х12:

1)
7 7 7 7 8 8 10 9 9 9 5 5
2 7 2 8 8 1 10 10 10 9 9 5
2 2 2 3 8 1 10 4 4 6 6 5
11 11 3 3 3 1 1 1 Квітень 4 6 5
11 11 11 3 12 12 12 12 12 4 6 6
2)
9 5 5 10 10 10 4 4 6 6 8 8
9 9 5 7 10 4 4 3 2 2 6 8
1 9 5 7 10 4 3 3 3 2 6 8
1 9 5 7 7 11 11 3 2 2 6 8
1 1 1 7 11 11 11 12 12 12 12 12

3)
7 7 7 7 9 10 10 10 8 1 1 1
5 7 4 4 9 9 10 8 8 2 2 1
5 4 4 11 11 9 10 3 8 8 2 1
5 4 11 11 11 9 3 3 3 2 2 6
5 5 12 12 12 12 12 3 6 6 6 6
Як можна помітити, кожна цифра в області означає номер фігури, яка поставлена ​​на цю клітку. Т. е. якщо індекс i фігури в масиві = 7, то клітини, зайняті цією фігурою відзначаються цією цифрою.


v Висновок
Отже, ми завершили розробку курсової роботи, а саме її головної мети - створення програмного продукту, що знаходить рішення головоломки «Y-пентаміно». Підводячи підсумки, можемо зробити кілька важливих висновків.
1. Застосування методу проб і помилок, замість звичайного повного перебору, дозволяє істотно скоротити час виконання програми, а також обсяг затрачуваної пам'яті. Це було з'ясовано під час аналізу складності алгоритму за алгоритмічної мірою А. Колмогорова. Обчислення показали, що кількість інформації алгоритму за методом проб і помилок, значно менше, ніж у алгоритму прямого перебору.
2. Важливою характеристичної особливістю розробки програми для вирішення головоломок є те, що практично неможливо скоротити число переборів за рахунок розгляду окремих випадків, не мають місця бути в тому чи іншому випадку. У задачі пентаміно була тільки можливість запобігти розгляд замкнутих областей дошки, площа яких менше або більше п'яти (в такі області фігуру вже ставити не можна, тому переглядати її в програмі немає сенсу - потрібно шукати інше рішення). Однак навіть у цьому випадку існують такі варіанти, при яких обмеження процесу розстановки цією умовою веде до появи помилок. В інших же випадках, це зробити вкрай складно, тому що далеко не всі можуть не тільки виявляти закономірності при вирішенні головоломок, а й навіть просто вирішити їх.
3. Основна складність у програмі належить представлення даних та безпосередній роботі з ними. Всі інші питання виникають саме внаслідок специфічності вихідних даних і результату. Дійсно, кожна фігура пентаміно є двовимірний масив, а масив фігур є вже тривимірний. Це досить громіздке. І особливо це видно при перевірці можливості вставки фігури в прямокутну область, коли доводиться оперувати з великим числом циклів, щоб перевірити кожен елемент пентаміно. У іншому ж, а саме в алгоритмі знаходження покриття дошки з фігурками пентаміно, це завдання мало, чим відрізняється від тієї ж відомою задачі про розстановці восьми ферзів на шаховій дошці.
v Список літератури
1. Касьянов В. Н., Євстигнєєв В. А. Графи в програмуванні: обробка, візуалізація та застосування. - СПб.: БХВ-Петербург, 2003.
2. Хусаїнов Б.С. Структури та алгоритми обробки даних. Приклади на мові Сі: Учеб. посібник. - Фінанси і статистика, 2004.
3. Х.М. Дейтел, П. Дж. Дейтел. Як програмувати на С + +: Четверте видання. Пер. з англ .- М.: ТОВ «Біном-Пресс», 2005р.
4. Дж. Макконнелл. Основи сучасних алгоритмів. 2-е доповнене видання. Москва: Техносфера, 2004.
5. Морозов М. Велика книга загадок і головоломок № 5. Егмонт Росія Лтд, 2004.
***
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
53.6кб. | скачати


Схожі роботи:
Вправа завдання тестове завдання точки перетину
Вправа - завдання - тестове завдання точки перетину
Завдання 18
Статистичні завдання
Завдання з авіації
Завдання за статистикою
Оздоровчі завдання
Завдання демографії
Завдання з оподаткування
© Усі права захищені
написати до нас