| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [C++] Расстановка 12 коней |
| Автор: TuttiFrutti 17.11.2006, 20:48 | ||
| Ребята,уважаемые кодеры,не могу решить зада4у,кто 4ем может помогите!!! ...Зада4а:Написать программу, 4тобы пк расставил 12 коней на шахматной доске так,чтобы все клетки были под ударом.(клетки,занятые конями не с4итать) Вот,4то я нарешал.Использовал функцию слу4айных 4исел,для определения координат каждогог из 12 коней,но как вы сами понимаете, вероятность того ,4то совпадет нужная расстановка о4ень мала,тем более random функция повторяет присвояемые зна4ения.Help....help....help!!! Мой код:
|
| Автор: maxim1000 17.11.2006, 21:49 |
| перебором можно для примера можно посмотреть задачу расстановки ферзей на доске так, чтобы они друг друга не били полный перебор будет порядка 64^12, но можно сделать несколько шагов по оптимизации: 1. отдельно решать задачу для белых клеток и для чёрных, т.к. они независимы, это приведет к 2*(32^6), что уже неплохо 2. прекращать просмотр ветки, если количество оставшихся безопасных клеток меньше, чем количество коней*8 (т.к. конь не может бить больше 8 клеток) - на сколько это ускорит не знаю, возможно, стоит делать это отсечение более "интеллектуально" |
| Автор: Dov 17.11.2006, 22:20 |
| TuttiFrutti, пойди в алгоритмы, там эта задача точно есть. Я лично мучился, переводил с паскаля, абсолютно им не владея, на С++. Ладно, вот я уже сам нашёл.http://forum.vingrad.ru/topic-85228/hl/%25D0%25BA%25D0%25BE%25D0%25BD%25D0%25B5%25D0%25B9/20.html |
| Автор: TuttiFrutti 18.11.2006, 12:42 |
| maxim1000, вам спасибо за содействие..попробую сам написать, у4тя советы! Dov, спасибо!!!...все работает!...я спасен! |