Вот задача про "Минное поле чудес" (постил Я) брутальная задачка
Меня интересует просто алгоритм. Честно говоря я не представляю, как её можно сделать.

Конечно, сперва надо действовать как в игре Сапёр - с этим проблем нету.
Проблема - как потом считать вероятности?

Сообщение отредактировано: hardcase - 25.01.2006 18:20

Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..
Вот тут я решал задачу про расстановку мин, но правда не в прямоугольнике, а линейную (причем, по требованию клиента, решил двумя способами..). Думаю, переделать в двумерный вариант не очень сложно.

Далее, по мере просмотра вариантов нужно просто считать количество мин для каждой клетке. Поясняю. Сначала заводим массив целых чисел размером с поле. Когда найден очередной вариант расстановки, инкрементим те клетки этого массива, где в найденном варианте стоят мины. В конце получим массив, показывающий суммарное число появлений мин в каждой клетке. Осталось поделить эти числа на количество вариантов - все вероятность готова, извольте кушать! Только не забудьте разложить по риал-тарелкам..

Беда только в том, что задача либо довольно долго считается (для нормальных размеров, типа 20) - так как прибавление одного поля даже в линейном варианте удваивает (кажется) количество вычислений, либо жрет памяти немеряно (мой гигабайт ушел играючи на длину массива, кажется, меньше 30). Короче, не все так просто..

Извиняюсь за серость, это об оперативной памяти речь идет ?

Короче идея мне ясна.
Брутфорс расстановок....
Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20...
Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми.

Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ.

Сообщение отредактировано: hardcase - 25.01.2006 21:24

О ней, родимой. Динамическое программирование (ДП) заключается в том, что ты запоминаешь промежуточные результаты, которые не нужны собственно для окончательно ответа, но потребуются при продолжении расчетов. Поскольку надобятся они в произвольном порядке, то класть это в файл на диск нельзя. Но это ускоряет вычисления (пока хватает памяти). Простейший пример: допустим, тебе в расчетах нужен факториал. Ты пишешь функцию с обычным перемножением чисел. Сначала тебе нужен 20!, потом 15!, потом типа 30! ... Можно все вычислять честно, но тогда на каждом вычислении нужно производить все умножения. А можно иначе: вычислил, скажем, 20! - и запомнил.. Потом, когда понадобился 30! - вынул и домножил на десять чисел. И тоже запомнил - пригодится, когда будет вычисляться типа 33! Это, конечно, очень простой пример..


Мне так не сдается. Условия слишком специфические, никаких общих принципов тут не присобачишь. Подумай, конечно - может, я что упустил.. Но, судя по тому, что она давалась setare как объект для ДП, я все же прав..

Перебор есть перебор, и перебирать надо все. Там все слишком завязано на нижнем уровне, оптимизировать не получается (у меня). Для того, чтобы в этом убедиться (или меня разубедить), нужно поиграть с условиями в уме.

Значит, решать нужно без ДП. Но 20х20 - терпимо. На моей машинке (двойной Athlon MP 2200+) этот размер пролетал за секунды. Введение двумерности усложнит расчет раза в три-четыре (не больше порядка, это точно) на каждой строке, да умножить на кол-во строк.. Короче, вполне терпимо еще, на ночь оставлять не потребуется
Задачка действительно неплохая, респект!

У меня ещё есть.
С контестов в CBOSS =)

У меня тут под монитором есть целый склад таких задач (кипа бумаг) - половина решена, правда файлы *.pas утеряны...

hardcase, а отсканить и залить есть возможность ?

Отсканить возможность есть - сканер и OCR имеюЦа. Дело в том, что где-то были pdf-эквиваленты, но я не знаю, где. А так могу десяток-другой пропостить.

Кстит часть задач на инглише формулируется - они с международных турниров по программированию.

Сообщение отредактировано: hardcase - 26.01.2006 18:07

Сюда ходим:
CBOSS Open Cup - раздел "Задачи", открывается PDF с задачками...

Спасибо