UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗадача про розміщення ферзів. Дерево пошуку та його обхід (реферат)
Авторdimich
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1512
Скачало319
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Задача про розміщення ферзів. Дерево пошуку та його обхід

 

Розглянемо шахівницю, що має розміри не 8? 8, а n? n, де n>0. Як

відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним

вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох

ферзів на шахівниці будемо називати їх розміщенням. Розміщення

називається допустимим, якщо ферзі не атакують одне одного. Розміщення n

ферзів на шахівниці n? n називається повним. Допустимі повні розміщення

існують не при кожному значенні n. Наприклад, при n=2 або 3 їх немає. За

n=4 їх лише 2 (рис.19.1), причому вони дзеркально відбивають одне

одного.

 

Задача. Написати програму побудови всіх повних допустимих розміщень n

ферзів, де 4? n? 20.

 

Для початку з'ясуємо деякі властивості допустимих розміщень. Очевидно,

що в них кожний ферзь займає окрему вертикаль і горизонталь. Занумеруємо

вертикалі й горизонталі номерами 1, … , n та позначимо через

, Hi> послідовність номерів горизонталей, зайнятих ферзями, що стоять у

вертикалях 1, 2, ? , i, де 0? i? n. Випадок i=0 відповідає порожньому

розміщенню <>.

 

Існує n способів розмістити ферзя в першій вертикалі, тобто перейти від

порожнього розміщення до непорожнього. Цей перехід позначимо стрілкою

(рис. 19.2(а)). За кожного з розміщень ферзя в першій вертикалі є n

варіантів розміщення ферзя в другій вертикалі, але з них слід відкинути

недопустимі. Відмітимо їх знаком '*' (рис.19.2(б)).

 

Узагалі, нехай зафіксовано розміщення ферзів у перших i-1вертикалях:

 

S(i-1)=.

 

Для побудови всіх допустимих розміщень із початком S(i-1) треба

перебрати всі допустимі розміщення S(i)з ферзем у i-й вертикалі та для

кожного побудувати всі допустимі розміщення з початком S(i).

 

Отже, маємо рекурсивний алгоритм побудови всіх допустимих розміщень, за

яким пошук усіх допустимих заповнень ферзями останніх n-i+1вертикалей

зводиться до пошуку заповнень n-i вертикалей.

 

Уточнимо цей алгоритм рекурсивною процедурою deps. Нехай розмір

шахівниці не більше nm=20. Номери вертикалей та діагоналей містяться в

діапазоні nums=1..nm, а розміщення зображається станом масиву H типу

 

arh = array[ nums ] of nums.

 

Процедура deps задає побудову розміщення, починаючи з i-ї вертикалі за

фіксованих H[1], ? , H[i-1]. Підпрограми test та writs задають

відповідно перевірку допустимості розміщення та

друкування повного розміщення. Вони викликаються у процедурі deps:

 

procedure deps ( var H : arh; n, i : nums);

 

var j, k : nums;

 

begin

 

for k := 1 to n do

 

begin

 

H[i] := k;

 

if test ( H, i) then

 

if i = n then writs ( H, n) {друкування повного розміщення }

 

else deps ( H, n, i+1 ) {рекурсивний виклик}

 

end

 

end

 

Функція test задає перевірку допустимості розміщення

H[i]> за умови, що є допустимим:

 

function test ( var H : arh; i : nums ) : boolean;

 

var j : nums; flag : boolean;

 

begin

 

j := 1; flag := true;

 

{перевірка, чи займається нова горизонталь і діагональ}

 

while ( j < i ) and flag do

 

begin

 

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ