| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
На доске (8х8) расставлено 8 ферзей [WinXP]
RiP © (2006-02-21 12:34:00)На доске (8х8) расставлено 8 ферзей (ферзь бьет по вертикали, горизонтали и диагонали). Убрать часть из них так, чтобы оставшиеся не били друг друга. Число оставшихся ферзей должно быть максимально.
хотя бы Подскажите кто нить алгоритм
TUser (2006-02-21 14:51:00) [1]Строим граф G = (V, E), где V - это ферзи. (v1, v2) in E, тогда если ферзь v1 не бъет ферзя v2 и наоборот. Искомое множество ферзей - это максимальная клика в графе. В общем случае задача нерешаема (она NP-полная), но при таком размере я бы решил перебором.
См. также ссылки на тему 'задача о вершинном покрытии'.
Ega23 (2006-02-21 12:41:00) [2]Яндекс рулит.
А вообще - самостоятельно такие задачи надо решать. Их тебе в ВУЗе не просто так задают.
| |
