количество вариантов расположения кораблей на игровом поле, морской бой |
количество вариантов расположения кораблей на игровом поле, морской бой |
LLL |
9.11.2009 12:23
Сообщение
#1
|
Группа: Пользователи Сообщений: 1 Пол: Женский Репутация: 0 |
Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)
на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле. |
RathaR |
9.11.2009 12:41
Сообщение
#2
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
Ну для начала, ты ведь сама говоришь о задаче, следовательно тему надо было розмещать не в разделе игр, а в разделе задач.
Ну а если по теме, то полный перебор наверное... Нужно найти сколькими способами из M*N клеток можна выбрать (1+2+3+4)=10 клеток, да еще и так, чтобы сохранялись правила розстановки, и прямолинейность кораблей... Хотя, если честно, то я сам слабовато себе это представляю... Сообщение отредактировано: RathaR - 9.11.2009 17:27 -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
andriano |
9.11.2009 13:25
Сообщение
#3
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
На самом деле, раз корабли не могут соприкасаться, при переборе просто нужно вместе с установкой корабля, делать занятыми клетки вокруг него.
Ну и сам перебор, естественно вести в диапазоне (M-1, N-2) клеток. Для увеличения скорости перебора я бы каждому полю ставил в соответствие 1 бит, тогда, учитывая, что максимальные 15 клеток укладываются в 16-разрядный регистр, просмотр всего поля состоял бы всего из 10 операций сравнения. Можно, использую 32-разрядные регистры, сократить количество операций до 5 или MMX - до трех. |
RathaR |
9.11.2009 17:24
Сообщение
#4
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
А почему бы не пойти "в лоб"...
Допустим у нас есть функция, которой передаються 4 параметра(координаты, направление корабля,количество палуб), и которая возвращает булевый результат, можна ли розместить корабль заданой величины в заданых координатах и заданом направлении. Под координатами корабля подразумиваем координаты его верхней левой клетки. И вот таким образом пробегаемся этой функцией 4 вложеных друг в друга цыкла(первый по 4 палубнику, последний по одно палубному) при этом считая кол-во удачных розстановок. Можна и без цыклов, рекурсией - перебор с отходом назад, правда я им слабо владею... Если делать цыклами то поидее будет (M*N)^4 итераций, что впринципе возможно... -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
andriano |
9.11.2009 20:18
Сообщение
#5
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями.
Оцениваем: (8*13)^4~117000000. Многовато. В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться. Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением. Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции. |
Lapp |
10.11.2009 5:41
Сообщение
#6
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Это либо 4 32-разрядных числа, либо 2 регистра ММХ. andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом? Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. )) Ответ получился такой: 64998706. Я только не уверен, правильно ли будет выкладывать тут код олимпиадной задачи.. LLL, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
andriano |
10.11.2009 9:44
Сообщение
#7
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом? Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. )) Полминуты в моем представлении - больше двух секунд. Это во-первых. Во-вторых: прежде чем рещать какую-то потенциально ресурсоемкую задачу я пытаюсь оценить максимальное время, которое она может выполняться. На мой взгляд, это естественно. Если программа потенциально ресурсоемка, я сразу пытаюсь написать ее достаточно оптимально по времени. Т.е. архитектура программы строится так, чтобы не было излишних потерь времени в критичных местах. На мой взгляд это также естественно. Гораздо более естественно, чем переписывать программу с нуля, когда окажется, чт она чрезвычайно ресурсоемка, а реализованный подход не позволяет ее существенно ускорить. И вообще, процесс предварительного проектирования (до того, как будет написана первая стргочка кода) - достаточно важный этап, на который молодые программисты обычно не обращают внимание. А зря. PS. А насчет ускорения асфальтового катка - афористично. Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек). Но ведь е любая задача поддается масштабированию. Сообщение отредактировано: andriano - 10.11.2009 9:47 |
Lapp |
10.11.2009 10:00
Сообщение
#8
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Спасибо))
Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек). Я начал с 4x4 при максимальной длине корабля L=1 (одна опечатка в границах была поймана на этом уровне). Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)). Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).Но ведь е любая задача поддается масштабированию. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
andriano |
10.11.2009 10:29
Сообщение
#9
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Спасибо)) Я начал с 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 10:30 |
Lapp |
10.11.2009 10:53
Сообщение
#10
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
> только дочитав:понял, то такое возможно.
)) не только возможно прогнать, но (главное!) возможно предстказать результат)). > А я бы вообще не стал делать проверки на границах. > Во-первых, граничные ячейки вообще рассматривать бессмысленно Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю.. > Почему вслух? Так надежнее, или время быстрее идет? привычка. Я так делаю всегда (например, на кухне, если надо, вместо таймера). Это позволяет некоторую многозадачность - слышишь свой голос и проще не сбиться, даже если отвлечешься)). > О ММХ я лишь упомянул, Я тоже)) Похоже, LLL решила забить на ответы.. Была тут на форуме утром, но.. LLL, уважаемая, ты слышишь, что тут люди, которых ты просила помочь, пытаются с тобой говорить? Ау-у! не понимаю людей, которым жалко лишний раз по клаве пройтись.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
RathaR |
10.11.2009 11:14
Сообщение
#11
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
А может всётаки перенесёте тему в раздел задач, к игре она ведь имеет только косвненное отношение...
А ММХ это что? -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
andriano |
10.11.2009 11:20
Сообщение
#12
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю.. Так и не понял про отсечение.Но все по порядку. "Минус хвост", если я не ошибаюсь, означет, что верхний предел цикла уменьшается на длину хвоста? Или "минус хвост" означает что на этапе конструирования цикла хвост никак не учитывается? Проверка столкновения по всему полю - иначе никак. Здесь чтобы учесть невозможность соприкосновения кораблей нужно что-то снабдить дополнительным рядом граничных клеток, либо новый корабль, либо совокупность уже расставленных. Т.е корабль, скажем, 3-палубный, представляется прямоугольником 3х5 клеток. И что, все-таки, такое - отсечение? Добавлено через 3 мин. А может всётаки перенесёте тему в раздел задач, к игре она ведь имеет только косвненное отношение... А ММХ это что? Отчего же? Здесь рассматриваются алгоритмы характерные именно для игр и подходы характерные для них же. А по поводу ММХ: http://ru.wikipedia.org/wiki/MMX (между прочим, первая же ссылка в Гугле по запросу "MMX") Хотя в статье есть ряд неточностей (если не сказать, откровенно ложных утверждений). Сообщение отредактировано: andriano - 10.11.2009 11:26 |
Lapp |
10.11.2009 11:33
Сообщение
#13
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
"Минус хвост", если я не ошибаюсь, означет, что верхний предел цикла уменьшается на длину хвоста? Или "минус хвост" означает что на этапе конструирования цикла хвост никак не учитывается? Первое. Цикл по координатам "носа корабля".Цитата Т.е корабль, скажем, 3-палубный, представляется прямоугольником 3х5 клеток. При постановке - да, конечно. Потом - нет.Цитата И что, все-таки, такое - отсечение? Это значит при проверке столкновения не залезать на прибрежную зону. Проверка на столкновение ведется в цикле. Соответственно, нужно корректировать границы цикла. Учитывая. что граница пропорциональна примерно корню из площади (количества внутренних клеток), это вряд ли целесообразно.Мммм.. сейчас подумал, что ведь есть же другой способ... думаю, он побыстрее будет. ээ.. Вот, все же интересно - надо еще это автору темы? Цитата Здесь рассматриваются алгоритмы характерные именно для игр и подходы характерные для них же. ... но все же не игра! Думаю, RathaR прав. Возиться лень.. ))(sorry about that mess.. забыл перейти в другое окно и стал нажимать всякие клавиши; эффект был забавный..) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
RathaR |
10.11.2009 11:34
Сообщение
#14
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
Отчего же? Цитата Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс) Помойму если в задаче сказано найти число возможных розстановок фигур или фишек, в какой либо игре, то прямого отношения к самой игре(за исключением правил розстановки, кои должны быть в условии задачи) она не имеет Цитата MMX (Multimedia Extensions — мультимедийные расширения) — коммерческое название дополнительного набора инструкций, выполняющих характерные для процессов кодирования/декодирования потоковых аудио/видео данных действия за одну машинную инструкцию. Ничего связаного с этой задачей в этом определении не обнаружил... И я думал это абривиатура на русском языке... Сообщение отредактировано: RathaR - 10.11.2009 11:34 -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
andriano |
10.11.2009 11:57
Сообщение
#15
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Первое. Цитата При постановке - да, конечно. Потом - нет. Цитата Это значит при проверке столкновения не залезать на прибрежную зону. Проверка на столкновение ведется в цикле. Соответственно, нужно корректировать границы цикла. Учитывая. что граница пропорциональна примерно корню из площади (количества внутренних клеток), это вряд ли целесообразно. Понял.Просто я изначально предположил несколько иной способ сравнения, а именно. 1. Заранее составляется набор масок для каждого корабля и каждого его возможного положения на поле (несколько сотен масок - не так уж много по используемой памяти. Особенно, учитывая, что одна клетка - один бит.) 2. Для какждого из 4-х вложенных циклов используется по отдельному полю. 3. В каждом цикле (кроме самого внутреннего) поле данного цикла сравнивается с маской корабля. При удаче - комбинируется поле следующего уровня и организуется вложенный цикл. На последнем уровне - инкрементируется счетчик удачных позиций. При неудаче данный проход цикла заканчивается. Цитата Мммм.. сейчас подумал, что ведь есть же другой способ... думаю, он побыстрее будет. Добавлено через 7 мин. Помойму если в задаче сказано найти число возможных розстановок фигур или фишек, в какой либо игре, то прямого отношения к самой игре(за исключением правил розстановки, кои должны быть в условии задачи) она не имеет Цитата Ничего связаного с этой задачей в этом определении не обнаружил... Отчего же?ММХ может явиться средством решения этой задачи. |
Lapp |
10.11.2009 12:40
Сообщение
#16
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Может, как раз выше описанный? Нет, совсем другой Я извиняюсь за тормоза, все время отвлекаюь на Star Trek по TV )). Закончился, наконец.. Да, пожалуй, можно попробовать.. 2 RathaR: не обманывайся расшифровкой аббревиатуры MMX - это многофункциональный набор команд, который можно использовать, если он подходит для твоих целей. В конечном итоге, все это всего лишь цифровые комманды. Используй, как нравится )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
10.11.2009 14:43
Сообщение
#17
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Первый способ (через игровое поле)
const Способ второй (через массив координат кораблей) const В обеих программах добавлена ненужная по большому счету процедура вывода текущей конфигурации - ее вызов закомментирован. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
10.11.2009 14:45
Сообщение
#18
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Нет, совсем другой Вот, сделал)). В этом способе совсем нет поля. Есть массив записей, представляющих координаты кораблей. Программа выдает в точности тот же результат (что, впрочем, неудивительно)). И этот способ действительно чуть быстрее, но несильно )).... Да, пожалуй, можно попробовать.. Только вот прямо не знаю, как быть.. Сделал две проги как дурак - и не могу их показать! вот уж lol так lol.. )). Ok, давайте я запощу их в следующем мессадже и скрою его. Если придет LLL и скажет, что все в порядке (или это выяснится другим способом) - volvo, открой этот мессадж, пожалуйста)). Готово, обе программы в предыдущем мессадже . -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
18.11.2009 15:16
Сообщение
#19
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Подумал, что уже можно открыть в любом случае. Жаль, конечно, что так и не пришлось услышать саму LLL - видимо, она стесняется..
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 24.09.2024 10:22 |