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

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

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

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

 

ПОШУК:   

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

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

ПЕРЕБИРАННЯ ВАРІАНТІВ

 

В ПРОГРАМУВАННІ

 

1. Задача про розміщення ферзів

 

Розглянемо шахівницю, що має розміри не 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

 

flag := ( H[i] <> H[j] ) and ( abs ( H[i]-H[j] ) <> i-j ); j := j+1

-----> Page:

0 [1] [2] [3] [4] [5] [6] [7] [8] [9]

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