Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++
Прочтите прежде чем задавать вопрос!1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Аля Сапёр, олимпиадная задача |
| hardcase |
 
Сообщение
#1
|
 code warrior  Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация:  8   |
Вот задача про "Минное поле чудес" (постил Я) брутальная задачка
Меня интересует просто алгоритм. Честно говоря я не представляю, как её можно сделать. Конечно, сперва надо действовать как в игре Сапёр - с этим проблем нету. Проблема - как потом считать вероятности? Сообщение отредактировано: hardcase - -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
   |
 
|
  |
| Lapp |
Сообщение
#2
|
 Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..
Вот тут я решал задачу про расстановку мин, но правда не в прямоугольнике, а линейную (причем, по требованию клиента, решил двумя способами..). Думаю, переделать в двумерный вариант не очень сложно. Далее, по мере просмотра вариантов нужно просто считать количество мин для каждой клетке. Поясняю. Сначала заводим массив целых чисел размером с поле. Когда найден очередной вариант расстановки, инкрементим те клетки этого массива, где в найденном варианте стоят мины. В конце получим массив, показывающий суммарное число появлений мин в каждой клетке. Осталось поделить эти числа на количество вариантов - все вероятность готова, извольте кушать! Только не забудьте разложить по риал-тарелкам..  Беда только в том, что задача либо довольно долго считается (для нормальных размеров, типа 20) - так как прибавление одного поля даже в линейном варианте удваивает (кажется) количество вычислений, либо жрет памяти немеряно (мой гигабайт ушел играючи на длину массива, кажется, меньше 30). Короче, не все так просто.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|
|
|
| hardcase |
Сообщение
#3
|
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Цитата(lapp @ 25.01.2006 14:50)  Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение.. Короче идея мне ясна. Брутфорс расстановок.... Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20... Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми. Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ. Сообщение отредактировано: hardcase - -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
|
|
|
hardcase Аля Сапёр 25.01.2006 18:19
lapp
Извиняюсь за серость, это об оперативной памяти р… 26.01.2006 4:57
klem4
:mega_chok:
Извиняюсь за серость, это об опер… 25.01.2006 20:48 hardcase У меня ещё есть.
С контестов в CBOSS =)
У меня ту… 26.01.2006 17:46 klem4 hardcase, а отсканить и залить есть возможность ? 26.01.2006 18:02 hardcase Отсканить возможность есть - сканер и OCR имеюЦа. … 26.01.2006 18:05 volvo Сюда ходим:
CBOSS Open Cup - раздел "Задачи… 26.01.2006 18:09 klem4 Спасибо :rolleyes: 26.01.2006 20:23 |
|
Текстовая версия | 18.05.2024 17:50 |
