гур пентамино. Спочатку кожна фігура була описана як рядок масиву geometry. Кількість стовпців у цьому масиві-25. Саме стільки необхідно для представлення двовимірного масиву 5х5. А кількість рядків відповідно дорівнює 12, так як ми знаємо, що всього фігурок дванадцять.
Можливо, виникне питання: В«Чому для подання кожної фігури потрібно 25 чисел? В»Справді, це досить багато, але якщо для кожної фігури створити окремий масив зі своєю "власної" розмірністю, то в пам'яті необхідно зберігати цей масив розмірностей для кожної фігури пентамино і звертатися до них виключно за індексами масиву. А це крім того, що незручно в процесі налагодження, до того ж досить громіздко і нітрохи не економить пам'ять. Внаслідок цього, я воліла мати константний масив geometry [12] [25]. p> Однак, як вже було сказано, таке подання даних є тільки на початковому етапі роботи програми. Якщо при виконанні рекурсії, у звернення до підпрограмі, в якості фактичних параметрів виступає масив, розмірністю 12х25, то це надзвичайно знижує ефективність програми, економію пам'яті, а також швидкодія. Незважаючи на те, що сучасна обчислювальна система впорається навіть з найгіршим програмним варіантом алгоритму, цей факт варто враховувати. З цієї причини, мені довелося перевести масив geometry в структури типу масив записів. Кожна запис масиву має два поля: масив shape (5x5), в якому представлена ​​форма кожної фігури і мінлива located. Вона служить чимось на зразок мітки на кожну фігуру, надає інформацію про те чи варто фігура на дошці чи ні. З такою структурою даних працювати набагато зручніше так як при рекурсивном виклик процедури, ми передаємо всього лише поточний елемент масиву записів, тобто одну запис.
Знову-таки, знову виникає питання: В«Чому не можна було уявити фігури пентамино в такому вигляді, не витрачаючи зайвої пам'яті на масив geometry? В»Це можливо лише в тому випадку, якщо дані вводять з пристрою введення, але це занадто утомливо, так як їх обсяг досить великий. Також можна було зчитувати з файлу, але ці способи ідентичні за обсягом займаної пам'яті. Описувати ж кожне поле кожного запису у вигляді константи не дозволяють кошти мов програмування, як Turbo Pascal, так і Visual C + +. br/>
Говорячи про вибір мови програмування, те це питання, що виникає відразу після розробки алгоритму. При виборі мови, я керувалася обраним поданням даних, властивостями алгоритму і особливостями завдання. Мій вибір припав на мову С + + в середовищі 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-пентамино. p> # include
# include
# 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: "<
