Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];
ВнизЗадача-2 Найти похожие ветки
← →
Oleg_Gashev (2002-09-08 22:11) [0]В интернете решения не видел. Кто найдет, можете линк бросить, почитаю.
А вот и условие. Всем известна задача о расположении восьми ферзей на шахматной доске. Надо раставить их так, чтобы они не били друг друга. Как известно, на доске 8х8 есть 92 расположения. Причем эти расположения зеркальны. Задача зпключается в нахождении не зеркальных расположений. То есть никакое расположение нельзя получить из другого поворотом доски или его зеркальным отображением.
← →
MBo (2002-09-09 09:28) [1]http://algolist.manual.ru/maths/combinat/queens.php
зеркальность не учитывается, но проверять такие варианты, imho, нетрудно
← →
Kaban (2002-09-09 09:36) [2]Как то странно вы расуждаете
>>Задача зпключается в нахождении не зеркальных расположений.
Допустим, мы нашли такое расположение, которое не может быть получено в результате зеркальных отображений. Повернем доску на 90 градусов. Получим новое расположение ферзей. Таким образом первоначальное расположение получается зеркальным отображением второго.
Скорее всего задача стоит в нахождении базовых расположений. Т.е. тех, которые не являются зеркальными отображениями друг друга. Всего, насколько я помню, существует 92 отображения, из них 13 базовых
← →
RV (2002-09-09 10:22) [3]а вот кто короче сформулирует алгоритм хождения по доске коня,
чтоб попал в каждое поле по одному разу?
← →
SPeller (2002-09-09 10:29) [4]На листе в клетку я такое делал, но непомню уже как.
← →
Kaban (2002-09-09 10:30) [5]1. Встаем в одну из 64 позиций шахматной доски
2. Вызываем рекурсивную функцию
2.1. Будем ходить конем по часовой стрелки
2.2. Если новая клетка не занята переходим к 2
3.2. Если занята или вышли за край доски переходим к 2.1
3.3. Если не возможно сделать ход во всех направлениях возвращаемся
← →
Kaban (2002-09-09 10:31) [6]Если имеется в виду вручную, то проще всего по кругу по всей доске
← →
RV (2002-09-09 10:32) [7]Kaban © (09.09.02 10:30)
так же на олимпиаде делал, но есть короче и красивее!
← →
Kaban (2002-09-09 10:37) [8]Продемонстрируй, я в этом не уверен. На мой взгляд в общем случае залдачу надо решать именно так.
← →
RV (2002-09-09 10:43) [9]не беда
тут действительно надо было знать следующее
Делаем ход конем туда, откуда минимальное число продолжений, но не равное 0.
← →
Kaban (2002-09-09 10:48) [10]да, но чтобы знать это нужно было выполнить некоторые математические исследования и главное ЗНАТЬ. Будет время я обязательно попробую. И главное я по прежнему не уверен, что этот способ быстрее отыщет все решения. Как никак дополнительные затраты на вычисление следующей позиции. И главное не противоречит тому, что если я пойду в другом направлении, то не найду решение.
← →
RV (2002-09-09 10:52) [11]главное ЗНАТЬ
вот вот, я и говорю.
И главное не противоречит тому, что если я пойду в другом направлении, то не найду решение.
я проверял, одно решение всегда есть
причем на разных досках и с разных позиций (ну не 3х3 и 4х4, стествв)
а программка мертва вместе с винтом :(
← →
MBo (2002-09-09 11:56) [12]про коня - рядом с данной мной ссылкой
← →
Oleg_Gashev (2002-09-09 18:55) [13]>Делаем ход конем туда, откуда минимальное число продолжений, но не равное 0.
Ne dlja vseh razmerov doski etot algoritm srabotaet.
← →
RV (2002-09-10 11:12) [14](ну не 3х3 и 4х4, стествв)
+ MBo © (09.09.02 11:56)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.007 c