Класически задачи по програмиране

Този интересен пъзел е предложен от математика Ойлер. Задачата на пръв поглед е доста проста - трябва ви шахматен кон, разположен на произволна клетка на шахматната дъска, за да обиколи всички останали клетки на дъската. В този случай една клетка може да бъде като само веднъж. Известно е, че конят ходи в L-образна форма. Тези. две клетки във всяка посока (нагоре, надолу, надясно, наляво) и една клетка в перпендикулярна посока. По този начин конят може да направи максимум осем различни хода от дадено поле (или по-малко, ако конят е на ръба на дъската).

За да разрешите този проблем на компютър, е необходимо да разработите правила, според които компютърът ще избере ход. По принцип следващият ход може да бъде избран на случаен принцип. Но само голям оптимист може да очаква добри резултати. Интересна опция за избор на ходове е предложена в книгата "Как да програмираме в C ++" от H. Deitel, P. Deitel.

За реализирането му са необходими два двумерни масива (размер 8x8). В първия масив (табла) записваме данни дали сме ходили до някоя клетка. Например, в началото всички елементи на масива са нула. Веднага щом поставим коня в която и да е клетка, съответният елемент от масива трябва да получи единица. Тук всичко е просто. Попълването на втория масив (достъпност - достъпност) е малко по-сложно. Всеки негов елемент, както и в дъската на масива, отговаря на клетка от дъската, но тук записваме информация колко клетки могат да бъдат като дадената. Например до клетка a1 може да се стигне от две клетки (c2 и b3). Масивът за достъпност преди започване на решаването на проблема изглежда така:

2	3	4	4	4	4	3	2
3	4	6	6	6	6	4	3
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
3	4	6	6	6	6	4	3
2	3	4	4	4	4	3	2

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

Имайки тези два масива, изборът на ход не е труден. Трябва да отидете до онези клетки, за които елементите на масива за достъпност имат минимална стойност, а елементите на масива на дъската са равни на нула.

Възможно е задълбочаване на анализа, т.е. брои няколко хода напред. В този случай трябва да изберем хода, който ни води до клетката с минималната стойност на елемента в масива за достъпност.

Освен това бих искал да обясня как се прави преместването. Вече казахме, че има осем възможни хода. Всички те са кодирани с числа от 0 до 7. На фиг. 2 показва всички възможни ходове.

2	1
3	0
К
4	7
5	6

Всяко движениеможе да се представи като преместване на даден брой клетки хоризонтално и вертикално. Например нулево движение съответства на хоризонтално преместване на две клетки, а "-1" клетка вертикално (знакът минус показва посоката на движение). Удобно е да използвате следните масиви за извършване на движения:

Стойностите на елементите на тези масиви съответстват на хоризонтално и вертикално движение за всички възможни ходове. Например, за да завършите ход 4, трябва да извършите две операции:

където X и Y са текущите координати (съответно хоризонтално и вертикално).

---