Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/10: Рейтинг темы: голосов - 10, средняя оценка - 5.00
Хамелеон_31
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 31
1

Игра "Спички Бергсона"

02.03.2014, 18:31. Просмотров 2027. Ответов 8
Метки нет (Все метки)

Здравствуйте. Не знаю, правильно ли я выбрал тему, но пока пишу сюда.

Есть такая задача-игра: Играют двое. На столе кучка спичек. На первом ходе игрок может взять 1 или 2 спички. На каждом следующем ходе игрок не может взять спичек больше, чем удвоенное количество спичек, взятое предыдущим игроком. Побеждает тот игрок, который возьмет последние спички.

Помогите с алгоритмом, который поможет выиграть. Перед этим уже искал эту задачу и нашел такое:
первый игрок выигрывает, если придерживается того, что при каждом своем ходе берет количество спичек n1 = (m-1)\3, если m - делится на 3
n1 = m\3, если m не делится на 3, где \ - деление нацело, m - текущий остаток спичек. Соотв вначале m=M
но это работает, если нет условия, что "На каждом следующем ходе игрок не может взять спичек больше, чем удвоенное количество спичек, взятое предыдущим игроком"
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2014, 18:31
Ответы с готовыми решениями:

Задача "Игра", динамическое программирование
Задаётся натуральное число n. Двое играющих называют по очереди числа, меньшие 107, по следующим...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

Какой придумать алгоритм для расстановки фигур в определённом порядке. По-сути это игра "пятнашки"
Нужно придумать алгоритм нахождения оптимального решения, то есть наименьшее количество...

Игра "Быки и коровы"
Сделайте алгоритм пожалуйста а то алгоритмы вообще не понимаю. Только играть нужно до тех пор пока...

Игра "5 в ряд"
Дали задачу по написанию игры "5 в ряд". Крестики-нолики, но на длинном поле, где надо собрать...

8
salam
188 / 169 / 29
Регистрация: 10.07.2012
Сообщений: 784
02.03.2014, 19:02 2
нужно писать анализ игры на графе. из каждого состояния переходите во все допустимые. если есть хоть один переход в проигрышное состояние из текущего, то текущее - выигрышно.
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
02.03.2014, 20:10 3
Цитата Сообщение от Хамелеон_31 Посмотреть сообщение
но это работает, если нет условия, что "На каждом следующем ходе игрок не может взять спичек больше, чем удвоенное количество спичек, взятое предыдущим игроком"
Может это работает если условие ЕСТЬ ? Или вы хотите другое условие ?
0
Хамелеон_31
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 31
02.03.2014, 20:25  [ТС] 4
как-то не понял
например, есть 17 спичек, первый игрок берет 2, тогда второй должен взять от 1 до 4, но используя тот алгоритм:
1.) 17 не делиться на 3
2.) n1 = 17/3 = 5

5>4

или Вы не это имеете ввиду?
0
02.03.2014, 20:25
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
02.03.2014, 23:42 5
Цитата Сообщение от Хамелеон_31 Посмотреть сообщение
как-то не понял
например, есть 17 спичек, первый игрок берет 2, тогда второй должен взять от 1 до 4, но используя тот алгоритм:
1.) 17 не делиться на 3
2.) n1 = 17/3 = 5
5>4
или Вы не это имеете ввиду?
Тогда вы не поняли алгоритм.
m это количество оставшихся спичек.
Идея в том, чтобы противник гарантированно не мог взять ВСЕ спички в этом ходу. Пусть игрок берет n спичек, тогда противник максимум может взять 2n спичек. Т.е. как результат одного хода максимум убрали 3n спичек. Следовательно чтобы гарантированно выиграть нужно брать такое количество спичек, чтобы число 3n было меньше чем оставшееся количество спичек, тогда игрок не проиграет в этом ходе. В случае когда 3n совпадает с m (т.е. количество оставшихся спичек делится на 3 без остатка) то тогда противник в этом ходе выиграет, следовательно надо брать на 1 спичку меньше.
Если мы не можем взять число n=m/3 из-за того что m слишком большое - то просто берем максимально возможное n

Добавлено через 5 минут
Если же m делится на 3 с остатком, то число n=m/3 при целочисленном делении даст число 3n < m
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
04.03.2014, 13:27 6
Я бы динамику попробовал. Может ли игрок выиграть, если оталось i спичек и он не может брать больше j.
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
04.03.2014, 15:38 7
Цитата Сообщение от Qwertiy Посмотреть сообщение
Я бы динамику попробовал. Может ли игрок выиграть, если осталось i спичек и он не может брать больше j.
Я считаю, что описанный метод в общем случае приводит к выигрышу(а более ничего не надо). Есть два случая когда гарантированно проигрываешь - если осталось 5 или 3 спичек и игрок не может взять их все. В случае же когда оба игрока играют по выигрышной стратегии, то тут решает только жребий - начальное количество спичек.

Смею предположить что динамическое программирование сведет решение как раз к описанному методу.
0
salam
188 / 169 / 29
Регистрация: 10.07.2012
Сообщений: 784
04.03.2014, 15:53 8
нам ваше предположение куда прикручивать?.. напишите и продемонстрируйте нам.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
04.03.2014, 18:07 9
Цитата Сообщение от wingblack Посмотреть сообщение
В случае же когда оба игрока играют по выигрышной стратегии, то тут решает только жребий - начальное количество спичек.
Это верно для любой ациклической игры. Тем не менее, это утверждение не говорит, для какого количества спичек выигрывает первый игрок, а для какого второй. Ну и стратегии тут тоже вроде как нет...
0
04.03.2014, 18:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2014, 18:07

Игра "Петамино"
Добрый день! Хочу узнать у знатоков, какими бы алгоритмами они воспользовались для решения...

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для &quot;черного ящика&quot;, который на входе принимает 2...

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта &quot;А&quot; приехать в пункт &quot;Б&quot; и показать возможные траектории движения....


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

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

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