Пример за курсова работа Информатика-програмиране
УРАЛСКИ ДЪРЖАВЕН РУДЕНСКИ УНИВЕРСИТЕТ
Кон, обхождащ шахматната дъска
Изпълнено от: Таранова М.В.
Пример за програмата
Този интересен пъзел беше предложен от математика Ойлер. Задачата на пръв поглед е съвсем проста - имате нужда от шахматен рицар на произволен квадрат на шахматната дъска, за да заобиколите всички останали квадрати на дъската, чийто размер също е зададен произволно. В този случай една клетка може да бъде извървена само веднъж.
Конят, както знаете, ходи Г-образно. Тези. два квадрата във всяка посока (нагоре, надолу, надясно, наляво) и един квадрат в перпендикулярна посока. По този начин, с рицар, можете да направите максимум осем различни хода от даден квадрат (или по-малко, ако рицарят е на ръба на дъската).
За да се реши този проблем на компютър, е необходимо да се разработят правила, според които компютърът ще избере ход. По принцип следващият ход може да бъде избран произволно.
Оригинално правило, даващо линеен във времето алгоритъм за преминаване по дъската, е предложено от Warnsdorff през 1983 г. Приложих го в курсовата си работа.
Алгоритъмът е формулиран много просто: следващият рицарски ход трябва да бъде направен на площада, откъдето има най-малък брой възможни ходове. Ако има няколко клетки с еднакъв брой ходове, тогава можете да изберете всеки.
На практика това се прилага, например, както следва. Преди всеки ход на рицаря се изчислява рейтингът на най-близките налични квадрати - квадратите, на които рицарят все още не е бил и към които той може да се движи с едно движение. Рейтингът на дадено поле се определя от броя на най-близките полета, налични от него. Колкото по-нисък е рейтингът, толкова по-добър е той. След това се прави ход на полето с най-нисък рейтинг (на който и да е от тях, ако има няколко от тях) и така нататък, стига да има къде да отидете.