Мины, Динамическое программирование |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Мины, Динамическое программирование |
setare |
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 152 Пол: Женский Репутация: 0 |
Здравствуйте! Нам дали задачу на динамическое программирование толком не обьяснив как можно эту тему использовать в решении задач. Мне дали следующую задачу:
Есть строка, которую вводит пользователь, например: 1 2***3*1 После этого надо написать программу, которая бы сосчитала сколькими способами можно поставить мины, как в игре сапере под каждой цифрой. Как можно подойти к этой задаче? И как рассчитать эти способы? А также массив будет двумерный или одномерный только для самых мин? Спасибо за ответ! И я пользовалась поиском, но по-моему такой темы у вас не была. По крайней мере я ничего не нашла. Сообщение отредактировано: setare - -------------------- Ты спрашиваешь, как я переношу длинные бессонные ночи?Как свеча: как только настает утро, я гасну, тем самым, имея возможность заново загореться.
Нима |
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
setare, я извиняюсь за задержку - перед праздниками очень туго со временем . Но если уж пообещал - пришлось сделать . Правда, я сомневаюсь, что у тебя еще есть потребность в решении..
Итак, вот программа и небольшие пояснения к ней. Фактически, вариантом является число, записанное в двоичной форме (1-мина, 0-пусто). Перебор вариантов ведем от 0 до 2^n - 1, где n - разрядность (или число символов в строке), верхние разряды заполняем нулями. В обычном алгоритме честно проверяем каждый вариант. В алгоритме с динамическим программированием (ДП) запоминаем результат проверки варианта и используем его в следующих шагах. Получается быстрее, но нужно много памяти. При длине строки n нужно 2^n байт (точнее - булевских переменных, но в паскале они представляются байтом). Таким образом, при длине строки 30 нужен гигабайт памяти. Программа действительно работает быстрее, но при малой длине строки это мало заметно. Для сравнения я поместил тут оба варианта - с ДП и без ДП (последний - мой, он сильно отличается от того, что предложил Malice). Комментарии самые минимальные. Если нужны подробности - спрашивай. 1. Алгоритм с ДП uses CRT; 2. Алгоритм без ДП uses CRT; -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 23.09.2024 16:53 |