количество вариантов расположения кораблей на игровом поле, морской бой Опции

[LLL]

Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)

на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле.

[andriano]

Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями.
Оцениваем: (8*13)^4~117000000.
Многовато.
В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться.
Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением.
Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции.

[Lapp]

Это либо 4 32-разрядных числа, либо 2 регистра ММХ.

andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом?
Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))

Ответ получился такой: 64998706.
Я только не уверен, правильно ли будет выкладывать тут код олимпиадной задачи.. LLL, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память.

[andriano]

andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом?
Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))

Не знаю, у кого как, но у меня, если программа при отладке выполняется больше некоторого времени, это начинает вызывать дискомфорт. Причем для меня лично этот временной порог составляет около 2-х секунд.
Полминуты в моем представлении - больше двух секунд.
Это во-первых.
Во-вторых: прежде чем рещать какую-то потенциально ресурсоемкую задачу я пытаюсь оценить максимальное время, которое она может выполняться. На мой взгляд, это естественно.
Если программа потенциально ресурсоемка, я сразу пытаюсь написать ее достаточно оптимально по времени. Т.е. архитектура программы строится так, чтобы не было излишних потерь времени в критичных местах. На мой взгляд это также естественно. Гораздо более естественно, чем переписывать программу с нуля, когда окажется, чт она чрезвычайно ресурсоемка, а реализованный подход не позволяет ее существенно ускорить.
И вообще, процесс предварительного проектирования (до того, как будет написана первая стргочка кода) - достаточно важный этап, на который молодые программисты обычно не обращают внимание. А зря.

PS. А насчет ускорения асфальтового катка - афористично.

Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек).
Но ведь е любая задача поддается масштабированию.

Сообщение отредактировано: andriano - 10.11.2009 13:47

[Lapp]

Спасибо))

Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек).
Но ведь е любая задача поддается масштабированию.

Я начал с 4x4 при максимальной длине корабля L=1 (одна опечатка в границах была поймана на этом уровне). Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)). Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).

[andriano]

Спасибо))
Я начал с 4x4

Просто споткнулся об это утверждение.
Даже не дочитав до конца фразы. И только дочитав:

при максимальной длине корабля L=1

понял, то такое возможно.

(одна опечатка в границах была поймана на этом уровне).

А я бы вообще не стал делать проверки на границах.
Во-первых, граничные ячейки вообще рассматривать бессмысленно - в них по условию ничего нельзя поставить, а во-вторых, при определенной длине корабля можно сразу вычислить пределы циклов, в которых его можно двигать.
Например, на поле 7х6 и горизонтальном положении 4-х палубного корабля его можно двигать лишь в пределах от 1 до 2 клетки (нумерация с 0) по горизонтали и от 1 до 4 - по вертикали, а при вертикальном положении - от 1 до 5 по горизонтали, а по вертикали вообще двигать нельзя.

Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)).

Почему вслух? Так надежнее, или время быстрее идет?

Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).

О ММХ я лишь упомянул, все дальнейшие рассуждения исходят из использования 32-разрядных чисел.
И, кстати, это также является примером подхода, которого я придерживаюсь: на этапе проектирования предусматривается возможность перехода на другую систему команд, но сначала задача пишется с использованием лишь стандартных средств и лишь потом, при необходимости, применяется дополнительная ассемблерная оптимизация.

Сообщение отредактировано: andriano - 10.11.2009 14:30

[Lapp]

> только дочитав:понял, то такое возможно.
)) не только возможно прогнать, но (главное!) возможно предстказать результат)).

> А я бы вообще не стал делать проверки на границах.
> Во-первых, граничные ячейки вообще рассматривать бессмысленно
Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю..

> Почему вслух? Так надежнее, или время быстрее идет?
привычка. Я так делаю всегда (например, на кухне, если надо, вместо таймера). Это позволяет некоторую многозадачность - слышишь свой голос и проще не сбиться, даже если отвлечешься)).

> О ММХ я лишь упомянул,
Я тоже))

Похоже, LLL решила забить на ответы.. Была тут на форуме утром, но.. LLL, уважаемая, ты слышишь, что тут люди, которых ты просила помочь, пытаются с тобой говорить? Ау-у! не понимаю людей, которым жалко лишний раз по клаве пройтись..

[andriano]

Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю..

Так и не понял про отсечение.
Но все по порядку.

"Минус хвост", если я не ошибаюсь, означет, что верхний предел цикла уменьшается на длину хвоста? Или "минус хвост" означает что на этапе конструирования цикла хвост никак не учитывается?

Проверка столкновения по всему полю - иначе никак. Здесь чтобы учесть невозможность соприкосновения кораблей нужно что-то снабдить дополнительным рядом граничных клеток, либо новый корабль, либо совокупность уже расставленных. Т.е корабль, скажем, 3-палубный, представляется прямоугольником 3х5 клеток.

И что, все-таки, такое - отсечение?


Добавлено через 3 мин.

А может всётаки перенесёте тему в раздел задач, к игре она ведь имеет только косвненное отношение...
А ММХ это что?

Отчего же?
Здесь рассматриваются алгоритмы характерные именно для игр и подходы характерные для них же.
А по поводу ММХ: http://ru.wikipedia.org/wiki/MMX (между прочим, первая же ссылка в Гугле по запросу "MMX")
Хотя в статье есть ряд неточностей (если не сказать, откровенно ложных утверждений).

Сообщение отредактировано: andriano - 10.11.2009 15:26