Форум программистов, компьютерный форум, киберфорум
Наши страницы
Математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
1

Задача из Шень - игра,стратегия

29.03.2017, 22:08. Просмотров 806. Ответов 6
Метки нет (Все метки)

На столе лежат две кучки спичек. Игроки ходят по очереди. За
один ход можно взять любое число спичек (1, 2, 3, ...) из одной из кучек
(по выбору игрока). При этом не разрешается оставлять поровну спичек в
кучках (за исключением случая, когда спичек не осталось вовсе). Кто не
может сделать ход, проигрывает.
Проверте правильный ли мой алгоритм:
После хода первого, определить большее число спичек из этих куч,
затем убрать столько спичек, чтобы осталось "меньшее + 1", так делать
до тех пор пока не останется 1 и 2 спичек, в одной и другой куче.
Получается 2 всегда выигрывает.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2017, 22:08
Ответы с готовыми решениями:

Покажите, что требования симметричности и транзитивности можно заменить одним (Шень, Верещагин)
Покажите, что требования симметричности и транзитивности можно заменить одним:...

Игра "крестики-нолики" беспроигрышная стратегия
Доброго времени суток! Пишу программу в Pascal "крестики-нолики", осталось 2...

Задача: Игра
Имеется клеточное поле высотой в одну клетку и шириной в N клеток. Поля...

Задача.Игра в числа
Вася очень любит играть в числа. Для этой игры нужна колода из N различных...

Задача.Игра в числа.
Вася очень любит играть в числа. Для этой игры нужна колода из N различных...

6
eropegov
337 / 335 / 65
Регистрация: 30.01.2017
Сообщений: 911
30.03.2017, 00:49 2
Цитата Сообщение от KO0 Посмотреть сообщение
2 всегда выигрывает
Не всегда. Вы уже сами увидели, что ситуация "1+2" проигрышная. Если в стартовой ситуации в одной из кучек 1 или 2 спички (кроме случая "1+2"), то выигрывает первый игрок, потому что первым своим ходом он ставит второго игрока в проигрышную ситуацию "1+2". Если стартовая ситуация "3+3", то первый игрок проигрывает, потому что любым своим ходом он дарит противнику выигрышную ситуацию. Но если стартовая ситуация имеет вид http://www.cyberforum.ru/cgi-bin/latex.cgi?3+n, где http://www.cyberforum.ru/cgi-bin/latex.cgi?n\ge 4, то первый игрок выигрывает, потому что первым своим ходом он может поставить соперника в проигрышную ситуацию "3+3". Ну, и так далее. Что-то у меня складывается такое впечатление, что если на старте кучки равные, то выигрывает второй игрок, а если неравные (кроме "1+2") - то первый.
1
SSC
Эксперт по математике/физике
2198 / 1350 / 386
Регистрация: 09.04.2015
Сообщений: 3,702
30.03.2017, 08:34 3
Цитата Сообщение от eropegov Посмотреть сообщение
то первый игрок выигрывает, потому что первым своим ходом он может поставить соперника в проигрышную ситуацию "3+3".
неверное рассуждение, так как
Цитата Сообщение от KO0 Посмотреть сообщение
При этом не разрешается оставлять поровну спичек в
кучках (за исключением случая, когда спичек не осталось вовсе).
1
SSC
Эксперт по математике/физике
2198 / 1350 / 386
Регистрация: 09.04.2015
Сообщений: 3,702
30.03.2017, 09:12 4
Цитата Сообщение от KO0 Посмотреть сообщение
Получается 2 всегда выигрывает.
Далеко не всегда так.
В случае когда количество спичек , которые берутся из кучки неограничено, то таблица состояний для игрока делающего ход приведена на первом рисунке.
По горизонтали и вертикали на зеленом фоне количество спичек в кучках, на пересечении состояние позиции для игрока выполняющего ход: 1-позиция выйгрышная, 0-позиция пройгрышная.
Как видим ситуация очень простая и в большинстве позиций начинающий выйгрывает, причем игра длится 3 хода.
А вот если ввести ограничение на число спичек которые берутся из кучки, допустим можно взять 1,2,3, тогда игра становится более интересной.
Таблица состояний для игрока делающего ход приведена на втором рисунке.
0
Миниатюры
Задача из Шень - игра,стратегия   Задача из Шень - игра,стратегия  
eropegov
337 / 335 / 65
Регистрация: 30.01.2017
Сообщений: 911
30.03.2017, 10:20 5
Цитата Сообщение от SSC Посмотреть сообщение
неверное рассуждение, так как
Да, виноват!

Добавлено через 8 минут
Цитата Сообщение от SSC Посмотреть сообщение
выйгрышная (...) пройгрышная (...) выйгрывает
й, й, й...

Добавлено через 14 минут
Исправлю своё рассуждение. Рассмотрим стартовую ситуацию 3+4. Поскольку 1-й игрок не имеет права своим ходом переводить в ситуацию 3+3, он вынужден переводить в ситуацию http://www.cyberforum.ru/cgi-bin/latex.cgi?0+n, http://www.cyberforum.ru/cgi-bin/latex.cgi?1+n или http://www.cyberforum.ru/cgi-bin/latex.cgi?2+n, из которой выигрывает игрок 2. Значит, ситуация 3+4 проигрывает. Но если стартовая ситуация http://www.cyberforum.ru/cgi-bin/latex.cgi?3+n или http://www.cyberforum.ru/cgi-bin/latex.cgi?4+n (http://www.cyberforum.ru/cgi-bin/latex.cgi?n \ge 4), то 1-й игрок своим ходом может поставить соперника в проигрывающую ситуацию 3+4.
0
SSC
Эксперт по математике/физике
2198 / 1350 / 386
Регистрация: 09.04.2015
Сообщений: 3,702
30.03.2017, 11:07 6
Лучший ответ Сообщение было отмечено KO0 как решение

Решение

Тоже ошибся в анализе задачи варианта ТС.
Вот исправленная таблица состояний для игрока делающего ход

Цитата Сообщение от eropegov Посмотреть сообщение
й, й, й...
Отсутствие системы проверки грамотности иногда приводит к таким печальным последствиям.
Была еще у меня стабильная проблема с "гостинница"
1
Миниатюры
Задача из Шень - игра,стратегия  
eropegov
337 / 335 / 65
Регистрация: 30.01.2017
Сообщений: 911
30.03.2017, 11:44 7
Цитата Сообщение от SSC Посмотреть сообщение
Была еще у меня стабильная проблема с "гостинница"
А у меня - с бессонницей. Но "й" - это просто бич нашего времени. Ещё 5-10 лет назад такого не было, а теперь это "й" пихают во все слова подряд. А началось всё с "Тайланда".

А табличка похожа на правду.
0
30.03.2017, 11:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2017, 11:44

Задача Компьютерная игра C++
Здравствуйте! Помогите решить задачку на тему Динамическое программирование....

Задача Простая игра
ПРОСТАЯ ИГРА. Дед Мазай и заяц играют в очень простую игру. Перед ними...

Задача в Excel: матричная игра.
Я уже давала сюда объявление - мол необходимо решить задачки в екселе... в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru