Динамическое программирование

Добрый вечер. Мне задали написать задачи на динамическое программирование, но нам ничего не объясняли, поэтому обращаюсь к профессионалам. Помогите пожалуйста написать программы или объясните как с математической точки зрения решать задачи, чтобы можно было вывести рекуррентную формулу к каждой из задач.

Играют два игрока. Есть полоска шириной 1 на 2010 клеток. Первый может закрасить 2, 4 или 6 рядом стоящих клеток( в любом месте полоски), второй 3, 6 или 9. Выигрывает тот кто закрасит последний( второму не хватит места). Кто выиграет при правильной стратегии? (Опять же первый или второй и почему?)

Есть плитка n на n, но в правом верхнем углу одна клетка вырезана и в левом нижнем тоже. Можно ли на неё разложить доминошки размером 1 на 2, чтобы пустых клеток не осталось и чтобы они не накладывались одна на другую?
Заранее большое спасибо...

0

Вторая задача к программированию отношения не имеет - ответ всегда "нет".

1

Спасибо за помощь, со второй задачей я с вам согласен, если думать по логике, но преподавателю такой ответ не понравится, поэтому нужно что-то написать.

0

Сообщение от ExtazY1991 Есть плитка n на n, но в правом верхнем углу одна клетка вырезана и в левом нижнем тоже. Можно ли на неё разложить доминошки размером 1 на 2, чтобы пустых клеток не осталось и чтобы они не накладывались одна на другую? Заранее большое спасибо...

Раскрасим поля плиты в шахматном порядке. Доминошка 1 на 2 должна покрывать одно белое поле и одно чёрное поле.
Для n- нечётного ответ сразу "нет", потому что вырезав две клетки мы всё равно оставим нечётное количество, которое нельзя покрыть доминушками.
Для чётного n ответ так же будет "нет", потому что вырезаны две клетки одного цвета, значит клеток другого цвета будет на 2 больше и покрыть поле не удастся.

2

За вторую задачу большое спасибо. Хохол подсказал, что первая задача делается с помощью теоремы Шпраг-Гранди, но я не очень ее понял можно ее объяснить другим способом или задачу объяснить другим способом? Спасибо ...

0

1

Возможно у кого еще будут идеи? Я думал на каждой итерации подсчитывать количество ячеек, остались и смотреть, если количество клеток, оставшихся кратное 3, 6 или 9, то первый игрок должен сделать так, чтобы кратность была 2, 4 или 6. Но прикол в том, что они могут закрашивать в любом месте линии ячейки, поэтому данная вариант решения не пройдет.

0

Для 1-ой задачи предлагаю такой вариант:
сначало для каждого игрока вручную заполняем результат от 0 до 9 включительно:
Для первого игрока:
0 1 2 3 4 5 6 7 8 9 <- Если столько рядом стоящих клеточек осталось и начинает 1-ый игрок
0 0 1 1 1 1 1 1 1 1 <- если 0, то значит первый игрок проиграет, если 1- выиграет

Для второго игрока:
0 1 2 3 4 5 6 7 8 9 <- Если столько рядом стоящих клеточек осталось и начинает 2-ой игрок
0 0 0 1 1 1 1 1 1 1 <- если 0, то значит второй игрок проиграет, если 1- выиграет

Теперь начиная с 10 и до 2010 начинаем использовать ДП:
берем 10 и рассматриваем это число для 1-го игрока так:
- берем число 2. - просматриваем соответственно для второго игрока варианты:
0, 8 - здесь 2-ой игрок выиграет (учитывайте ранее полученные результаты 0 и 8 для 1-го и 2-го
игрока)
1, 7 - здесь 2-ой игрок выиграет (учитывайте ранее полученные результаты 1 и 7 для 1-го и 2-го
игрока)
2, 6 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 2 и 6 для 1-го и 2-го
игрока)
и т.д.
- берем число 4. - просматриваем соответственно для второго игрока варианты:
0, 6 - здесь 2-ой игрок выиграет (учитывайте ранее полученные результаты 0 и 6 для 1-го и 2-го
игрока)
1, 5 - здесь 2-ой игрок выиграет (учитывайте ранее полученные результаты 1 и 7 для 1-го и 2-го
игрока)
2, 4 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 2 и 6 для 1-го и 2-го
игрока)
и т.д.
- берем число 6. - и тоже просматриваем соответствующие для второго игрока варианты...
Если хотя бы в одном из просматриваемых вариантов победа 1-го игрока, то продолжаем таблицу для 1-го игрока. После просмотра числа 10, для 1-го игрока получится:
0 1 2 3 4 5 6 7 8 9 10
0 0 1 1 1 1 1 1 1 1 1

Затем похожее делаем для 2-го игрока (для второго игрока делаем эти расчеты только для того, чтобы использовать эти значения в будущем для вычислений 1-го игрока).
берем 10 и рассматриваем это число для 2-го игрока так:
- берем число 3. - просматриваем соответственно для первого игрока варианты:
0, 7 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 0 и 7 для 1-го и 2-го
игрока)
1, 6 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 1 и 6 для 1-го и 2-го
игрока)
2, 5 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 2 и 5 для 1-го и 2-го
игрока)
3, 4 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 3 и 4 для 1-го и 2-го
игрока) - Здесь маленькое уточнение: если рассматриваем варианты, как сейчас для 1-го игрока,
и оба варианта выигрышные для 1-го и 2-го игрока, и хотя бы один вариант больше 3, то всегда
выиграет 1-ый игрок. В остальных случаях и для 1-го и 2-го игрока будет работать такое правило:
если оба варианта выигрышные для 1-го и 2-го игрока, то выиграет противоположный игрок,
рассматриваемому.
- берем число 6. - просматриваем соответственно для первого игрока варианты:
0, 4 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 0 и 4 для 1-го и 2-го
игрока)
1, 3 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 1 и 3 для 1-го и 2-го
игрока)
2, 2 - здесь 1-ый игрок выиграет (учитывайте ранее полученные результаты 2 и 2 для 1-го и 2-го
игрока)
- берем число 9. - просматриваем соответственно для первого игрока варианты:
0, 1 - здесь 2-ой игрок выиграет (учитывайте ранее полученные результаты 0 и 1 для 1-го и 2-го
игрока)
Итак после просмотра числа 10, для 2-го игрока получится:
0 1 2 3 4 5 6 7 8 9 10
0 0 0 1 1 1 1 1 1 1 1

И так далее.
На самом деле можно остановится рассматривать очередные варианты, для любого числа, для 1-го и 2-го игрока, если попался первый вариант в котором этот игрок выигрывает.

1

Спасибо большое Вы меня реально выручили. Держите +1...

0

valeriikozlov, подозрительно простой у вас пересчет. Думаю, он неверен. Почитайте про стратегию игры ним и пример из статьи про функцию шпрага-ганди. В обоих случаях для каждой подигры недостаточно одной лишь информации о том, является ли её позиция выигрышной. Думаю, тут примерно так же.

Добавлено через 2 минуты
Если бы ходы игроков были одинаковыми, задача решалась бы так же как в примере про функцию ш-г, но тут ходы разные и я не понимаю что делать.

1

Хохол, Как с Вами тяжело!
Шучу конечно, все наоборот. Давайте подругому рассмотрим эту задачу.

Сообщение от Хохол но тут ходы разные и я не понимаю что делать.

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

2

Ха, прикольно, так просто решается.
Итого, первая задача с такой формулировкой тоже мало отношения к программированию имеет.

1