| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Вопрос про ладьи и доску (комбинаторика). |
| Автор: .talisman 15.5.2005, 11:10 |
| Сколькими способами можно расставить n ладей на доске n*n так, чтобы они держали под угрозой все поля доски? заранее спасибо. |
| Автор: .talisman 15.5.2005, 12:42 |
| блин, ну вы мне идейку подкиньте, а я напишу код и выложу. |
| Автор: segmentation_fault 16.5.2005, 08:10 |
| Ну вот наверное самый простой алгоритм: Перебрать все возможные расстановки n ладей на доске n*n. Для каждой расстановки проверить если все клетки под боем если да, то соответственно прибавляешь 1 к количеству искомых расстановок Нахождение возможных расстановок частный случай проблемы нахождения всех подмножеств определённого множества. В данном случае ты ишеш подмножества размера n в множестве размера n^2. Будешь ето решать лексикографически или по другому дело твоё. Если одна ладья стоит на клетке (x1, y1), 0<= x1 <= n, 0<= y1 <= n, то любая клетка (x2, y2) где x2=x1 или y2 = y1 будет под боем. Дальше просто находишь все такие клетки для всех n ладей. |
| Автор: chipset 16.5.2005, 08:24 | ||
|
| Автор: Alastis 16.5.2005, 11:37 |
| В книге Бадда "ООП" (могу выслать если надо) есть учебный пример - задача о восьми ферзях. Очень похоже на твою задачу, посмотри исходник, решение довольно красивое при помощи чистого ООП. Правда пример про конкретную шахматную доску 8 на 8, но немного подумать и переделать и все. Выкладываю исходник класса Ферзя. |
| Автор: SoWa 16.5.2005, 11:48 |
| Вот какая0то шахматная теория: q[i,j]=(i+j) mod 2; |
| Автор: Akina 16.5.2005, 12:14 |
| Думай вот куда - на доске N*N при расстановке ладей, бьющих ВСЕ поля, ОБЯЗАТЕЛЬНО либо на каждой горизонтали по ладье, либо на каждой вертикали по ладье. Отсюда - расстановок, когда на каждой горизонтали по ладье, N в степени N. Столько же - когда на каждой вертикали. Осталось посчитать и отнять количество дублей - а оно равно количеству расстановок, когда ни одна ладья не бьет другую, т.е. N! (факториал). Результат - 2*N^N-N! |
| Автор: .talisman 18.5.2005, 13:25 |
| Akina, спасибо большое -- это именно то, что нужно. |