Форум программистов, компьютерный форум CyberForum.ru

Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
NightVVanderer
1 / 1 / 0
Регистрация: 27.05.2012
Сообщений: 10
09.10.2013, 16:51     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры #1
Здравствуйте! Помогите с написанием программы, пожалуйста.
Задача: есть 2 игрока(1-ый и 2-ой соответственно), перед ними лежи куча камней, в свой ход каждый может либо добавить в кучу 1 камень, либо умножить количество камней на 2. Количество камней у игроков не ограничено. Выигрывает тот игрок, на чьем ходу количество камней превысило заданную отметку. Программа должна выводить выигрышные стратегии для выбранного(или, хотя бы для какого то определенного) игрока. Вывод стратегий возможен в любом варианте, главное что бы они были читаемы.
Использовать можно любые приемы и возможности С++, никаких ограничений нет.

Я думаю можно сделать это с помощью дерева(на картинке), но я не знаю как это реализовать и как потом выдавать стратегии. Как я себе это представляю: создается дерево, в корень записывается начальное количество камней(пусть будет k), дальше создаются потомки от корня, в один записывается k+1, в другой k*2, после каждой записи проверяется не превосходит ли получившееся количество заданную отметку, если превосходит, то все это последний лист этой ветки дерева(то есть победа какого то игрока). Далее от каждого из предыдущих также создаются два потомка(предыдущий результат+1 и предыдущий результат*2) и проверяются не больше ли они заданной отметки и т.д.
Миниатюры
Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2013, 16:51     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры
Посмотрите здесь:

C++ Теория игр, массивы
Мне очень нужна программа для игры gta samp 0.3c для взлома базы данных C++
C++ Программа, которая выдает запрос на ввод значений часов и минут
C++ Программа для определения кода клавиши выдает неверный код кнопок
Программа для игры в покер C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
09.10.2013, 17:25     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры #2
Мне кажется, что тут нужно идти от обратного. Игрок не проиграет в том случае, если после его хода в куче будет count <= max / 2 - 1 камней. При этом нужно учесть, что игрока2 нужно поставить в положение, когда после его хода count >= max / 2 || count == max - 1. Соотстветсвенно выиграет та стратегия, которая позволит игроку после хода оставить в куче count == max / 2 - 1 камней. Вот как то так. Я бы думал в этом направлении.
NightVVanderer
1 / 1 / 0
Регистрация: 27.05.2012
Сообщений: 10
09.10.2013, 19:02  [ТС]     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры #3
По умолчанию считается что игроки делают логичные ходы, то есть если один ход ведет к тому, что на след ходу выиграет другой игрок, а другой ход к этому не ведет, то будет сделан ход, не ведущий к проигрышу. Программа должна выдавать беспроигрышную стратегию(то есть такую, что при любом ходе соперника, другой игрок выиграет), если такая есть, если нет, то она должна выдавать все выигрышные стратегии(то есть последовательность ходов).
eugrita
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 405
28.10.2013, 19:57     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры #4
Подобную задачу я решал.
задача С3 -игра в камушки.
-------------------------------------------
Правила: в куче N камней
2 (несколько)игроков ходят по очереди у каждого есть свой конечный набор ходов (индивидуальный или общий)
Выигрывает тот кто сделал последний ход.
------------------------------------------------------------------------------
Я написал на эту тему несколько программ в порядке усложнения (используют рекурсию).
1)прохождение по листьям дерева, счет кол-ва выигрышей 1-го и 2-го игрока
2)Нахождение выигрышных позиций 1 и 2 игрока
3)Разработка интерактивной игры компьютер играет по стратегии 1 ход вперед.
(Т.е. просмотр вершин следующего уровня переход к выигрышной и уклонение от проигрышной в случ их наличия.
Возможны и более тонкие стратегии.
Очень хотелось бы математического обобщения данной задачи типа типа выбора из конечного числа
альтернатив каждого шага. И нахождения реальных экономических игровых задач под эту модель.
Если рассматривать процесс выбора альтернатив не как игру, а как оптимизацию некоего глобального критерия
-получим задачу динамического программирования.
А можно ли придумать из обл.экономике задачу типа игры с конечным числом стратегий?
Ну ,есть в теории задача о случайном блуждании

Добавлено через 5 минут
Полезно на бумаге построить несколько деревьев игры например для N=30 m1=4, m2=3
или N=40, m1=5,m2=4 Выигрышные позиции 1 игрока заштриховать красным, а 2-го-чернвм.
Если при просмотре следующего уровня для 1-го есть красная вершина - идти туда, если есть черная - не идти. Внизу общего дерева игры могт быть красные и черные поддеревья различной высоты. (какой?)
Yandex
Объявления
28.10.2013, 19:57     Теория игр на примере С3 из ЕГЭ по информатике. Программа, которая выдает стратегии для игры
Ответ Создать тему
Опции темы

Текущее время: 05:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru