ми перебору.
Розглянемо приклад. Нехай шість ферзів розставлені на дошці, як показано на рис. 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, б). p> Як же реалізувати розглянутий алгоритм? Самий простий і самий трудомісткий за часом виконання - це метод прямого перебору. Першим ходом поставимо ферзя на яку-небудь клітину, витративши на це одиницю часу. Потім в наступному ході переглядаємо 64 можливих варіантів постановки чергового ферзя. Для кожного варіанта (i, j), i - номер горизонталі, j - номер вертикалі, необхідно перевірити по 8 клітин i-й горизонталі і j-й вертикалі, від 1 до 8 клітин для кожної діагоналі, що проходить через клітку (i, j). p> Таким чином, число переборів виявляється непомірно велікім.Учтем обставина, що на кожній горизонталі може бути встановлений тільки один ферзь. Тому перший ферзь встановимо на першій горизонталі, другий - на другий і т.д. Тоді для кожного /-го ходу залишиться всього лише вісім варіантів постановки ферзя, а перевірятися будуть клітини тільки на j-й вертикалі і двох діагоналях. Незважаючи на це, число перевірок залишається великим. p> Якщо тепер взяти до уваги те, що не тільки на кожній горизонталі, але на кожній вертикалі і кожної діагоналі може знаходитися тільки один ферзь, число перевірок можна істотно скоротити. Для цього необхідно мати інформацію про стан (В«зайнятоВ» - В«вільноВ») 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) p> 5. Якщо i <12, то пункт 6, інакше 7; (Z3)
6. Збільшуємо i на одиницю і перехід до пункту 2; (v3)
7. Виведення на екран одного рішення; (v4)
8. Обнуляємо значення i-ої фігури на дошці; (v5)
9. Якщо j
Кінець
Словесний алгоритм дає короткий опис програмної реалізації рішення задачі, і призначений із загальною схемою алгоритму. Зокрема в ньому не розглядається процес подання форми кожної фігури в пам'яті ЕОМ, так як це питання описується далі. Також існує неточність з приводу кількості циклів, так ка в програмі їх значно більше, з причини роботи з тривимірними масивами. Однак для зручності і наочності, я вважаю, цим можна знехтувати. p align=center> v Обгрунтування вибору структур даних
Перш ніж приступити до розробки алгоритму і створення програми, нам необхідно мати уявлення про спосіб представлення даних в ЕОМ. Тому першим питанням, при розробці програм, є вибір структур даних. У своїй програмі мені довелося застосувати послідовно дві структури для подання в пам'яті фі...
