Задача за "Ход на коня". Задача 1: Ход на коня



Дата23.10.2018
Размер50.81 Kb.
ЛУ-7,8

Методи “Връщане назад” и “Балансировка”


Цел: Запознаване с методите за създаване на ефективно ПО – “Връщане назад” (още “Отстъпване”) и “Балансировка” и демонстриране на използването им при решаване на сложни задачи.

Теоретична част:

“Връщане назад” – задачата тук се задава като задача за създаване на алгоритми за решаване на специфични проблеми. Такива алгоритми не следват определено правило, а се настройват чрез “проби и грешки”. Задачите, които изискват за решаването си такива алгоритми, използват най-често рекурсия и се състоят от изследване на краен брой подзадачи.

Предмет на тази подтема е общият принцип на разбиване на такива задачи на подзадачи, и използването на рекурсия за решаване на последните. Отделните похвати се демонстрират с определени задачи. Тук избраната задача е т.нар. задача за “Ход на коня”.

Задача 1: Ход на коня

Дефинирането на задачата е следното: Дадена е шахматна дъска с размери n x n. Шахматната фигура кон (по-нататък само кон) е на поле с координати Хо,Уо. Трябва да се определи такова движение на коня на дъската, по правилата на шаха, че да бъдат посетени всички полета и то само веднаж.

Задачата се свежда до – извършване_на_следващ_ход, или да се установи, че е невъзможно да се извърши такъв ход. Първоначално трябва да се дефинира алгоритъм, който “се опитва” да направи следващ ход:

Алгоритъм Опит_следващ_ход;

Инициализиране_на_възможните_ходове

do

Избор на следващ кандидат от списък_следващи_ходове



ако ходът_е_ приемлив,

то регистриране_на_хода

ако дъската_не_е_обходена

то Опит_следващ_ход

ако ходът_е_неприемлив

то изтриване_на_предишен_регистриран_ход

while ходът_е_успешен или няма_повече_кандидати

(край)


От тук-нататък е необходимо да се вземат някои решения за представяне на данните, а именно:

Дъската се представя като матрица.

Всяко посетено поле от дъската се представя с цяло число – номер - на кой ход е било посетено това поле.

Избира се булев признак за указване на успешен/неуспешен ход.

Избира се признак за определяне, кога полетата на дъската са били посетени и няма повече полета-кандидати за посещаване.

Записва се условие, което определя дали следващият ход, по правилата на шаха, е в поле от дъската или извън нея.

Въвежда се локална променлива за указване на успешен/неуспешен ход при рекурсивното обръщение.

Записът на подобна функция “Опит_следващ_ход” , на С/С++, има следния вид:

void Tryy(int i, int x, int y, int q){

int k,l,m,q1;

k=0;

do{


k=k+1;q1=0;

l=x+c[k]; m=y+b[k];

if ((l>=1) && (l<=n) && (m>=1) && (m<=n)){

if(d[l][m]==0) {

d[l][m]=i;

if(i

Tryy(i+1,l,m,q1);

if(q1==0)

d[l][m]=0;

}

else



q1=1;

}

}



}

while ((q1==0) || (k!=8));

q=q1;

} /*end tryу */



До тук бъдещата програма се разработва незавизимо от правилата на играта “шах”. Това се прави с цел да се улесни решаването на основната задача, като се решават различни подзадачи.

Получаването на възможните за посещаване от коня полета може да се реализира чрез опериране с индексите на масива-шахматна дъска, например със следните масиви (c – за стълб, r - за ред).

c[1]=2; r[1]=1;

c[2]=1; r[2]=2;

c[3]=-1; r[3]=2;

c[4]=-2; r[4]=1;

c[5]=-2; r[5]=-1;

c[6]=-1; r[6]=-2;

c[7]=1; r[7]=-2;

c[8]=2; r[8]=-1;

Налага се и избор на индекс за номериране на полетата - кандидати за посещаване.

Характерна особеност на представеният тук пример е, че всяка стъпка към намиране на пълното решение се регистрира след предприемане. Такава регистрация позволява по всяко време да се извърши връщане към предишна регистрация (предишното състояние, например) и стъпката да се заличи от списъка на регистрираните стъпки, ако се установи че не води до решение на проблема или води “в задънена улица”. Това действие се нарича “отстъпване”, а методът – “метод с отстъпване” (още “метод с връщане назад”).

Примерно решение на задачата, за n=5 е дадено на следващите редове.

1 6 15 10 21

14 9 20 5 16

19 2 7 22 11

8 13 24 17 4

25 18 3 12 23


Метод “Балансировка”:

Ако се разгледа внимателно методът за сортировка чрез пряка размяна (“мехурчеста сортировка”, виж Тема 4), може да се забележи, че при всеки тур, списъкът от елементи (числа или ключове) може да се представи разделен на две части – преместваният елемент и останалите елементи.

Сложността по време на метода може да се представи така:

T(n)= 0, ако n=1

T(n)= T(n-1)+n-1, ако n>1

Асимптотичната оценка на метода е пропорционална на n*n. Тази недобра оценка се дължи на разделянето на елементите на две силно неравни части. Оценката ще е най-добра, ако разделянето всеки път води до получаване на две равни части. Този принцип се нарича “балансировка”, а методите основани на него – “методи с балансиране”.

Принципът “балансировка” е залегнал в основата на метод за сортировка наречен “ сортировка чрез сливане”.
Задача 2: Сортировка чрез сливане

Задачата се формулира така: Да се напише програма на С/С++ за реализиране на метода ‘Сортировка чрез сливане” върху числено множество несортирани елементи.

Същността на метода за сортировка се състои в разбиване на списъка (множеството), който ще се сортира, на две равни части, сортировка на частите поотделно и сливането им последствие в един списък. Разбиването на равни части може да продължи рекурсивно до получаване на част от два елемента, които само трябва да си сменят местата, евентуално след едно сравнение.

Сортировката чрез сливане има различни реализации. Тук ще бъде дадена функция, която реализира сортировка чрез сливане “отгоре-надолу”, предложена в [7].

Функцията за сортировка чрез сливане на елементи с начален номер l и краен номер r има следния вид:

void Merge_sort( item a[], int l, int r){

int m=(r+l)/2;

if(r<=l) return;

Merge_sort(a,l,m);

Merge_sort(a,m+1,m);

merge(a,l,m,r); }

Тази реализация на сортировка чрез сливане е прототип на рекурсивна програма от тип “разделяй и владей”. Тя сортира масив a[n] като го разделя на две части a[l..m], и a[m+1..r], сортира ги независимо чрез рекурсивни обръщения, и слива подредените полумасиви за да получи крайният резултат. Функцията merge може да се нуждае от това, да ползва временен масив, с дължина – дължината на началния, за получаване на резултата. Възможно е обаче и да се ивърши “сливане на място”, при което допълнителния масив да не е толкова голям, колкото началният масив a[n].



Въпроси по темата и задачи за изпълнение:

Метод “Връщане назад”:

1. Напишете програма, която решава задачата за хода на коня. Тествайте я за случай – n=5. Проверете резултата с дадения по-горе. Опитайте и с други стойности на n-4,6,8 (Използвайте същите масиви c и r, в противен случай решението ще се различава от даденото (за n=5). Защо?).

Метод “Балансировка”:



  1. Каква е основната цел на метод “Балансировка”.?

3. Напишете програма на С/С++, която реализира “сортировка чрез сливане”.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница