С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
NightVVanderer
1 / 1 / 0
Регистрация: 27.05.2012
Сообщений: 16
#1

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

09.10.2013, 16:51. Просмотров 1910. Ответов 3
Метки нет (Все метки)

Здравствуйте! Помогите с написанием программы, пожалуйста.
Задача: есть 2 игрока(1-ый и 2-ой соответственно), перед ними лежи куча камней, в свой ход каждый может либо добавить в кучу 1 камень, либо умножить количество камней на 2. Количество камней у игроков не ограничено. Выигрывает тот игрок, на чьем ходу количество камней превысило заданную отметку. Программа должна выводить выигрышные стратегии для выбранного(или, хотя бы для какого то определенного) игрока. Вывод стратегий возможен в любом варианте, главное что бы они были читаемы.
Использовать можно любые приемы и возможности С++, никаких ограничений нет.

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

Написание бота для игры (стратегии) - C (СИ)
Здравствуйте! Нужен желающий которому будет не лень написать бота для игры. Бот нужен для сравнения его с моим ботом. Хотел бы узнать что я...

Подскажите хорошие стратегии для игры по сети - Стратегии
Хотим поиграть с другом по Wi-fi, У него Xp у меня Seven. В WarCraft мы нормально играли, а вот в казаков и крестоносцев не видим друг...

В ближайшие 5-6 часов нужна прога)Игры с природой(теория игр) - Delphi
Здравствуйте, нужно реализовать на delphi Игры с природой (теория игр) Программа нужна уже через 5-6 часов все подробности почта...

Программа которая выдает платформу компьютера выдает ошибку - Delphi
unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls,...

C4 ЕГЭ по информатике - Pascal
Несколько дней пытаюсь понять 1)зачем второй раз дают одно и тоже условие `else if estimate=MaxEstimate2`Ведь оно есть до этого ,и...

ЕГЭ по информатике - C++
Извините если не в ту тему написал, не могу понять куда лучше это написать. На каком языке сдавать ЕГЭ по информатике? Я знаю только...

3
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
09.10.2013, 17:25 #2
Мне кажется, что тут нужно идти от обратного. Игрок не проиграет в том случае, если после его хода в куче будет count <= max / 2 - 1 камней. При этом нужно учесть, что игрока2 нужно поставить в положение, когда после его хода count >= max / 2 || count == max - 1. Соотстветсвенно выиграет та стратегия, которая позволит игроку после хода оставить в куче count == max / 2 - 1 камней. Вот как то так. Я бы думал в этом направлении.
0
NightVVanderer
1 / 1 / 0
Регистрация: 27.05.2012
Сообщений: 16
09.10.2013, 19:02  [ТС] #3
По умолчанию считается что игроки делают логичные ходы, то есть если один ход ведет к тому, что на след ходу выиграет другой игрок, а другой ход к этому не ведет, то будет сделан ход, не ведущий к проигрышу. Программа должна выдавать беспроигрышную стратегию(то есть такую, что при любом ходе соперника, другой игрок выиграет), если такая есть, если нет, то она должна выдавать все выигрышные стратегии(то есть последовательность ходов).
0
eugrita
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 454
28.10.2013, 19:57 #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-го есть красная вершина - идти туда, если есть черная - не идти. Внизу общего дерева игры могт быть красные и черные поддеревья различной высоты. (какой?)
0
28.10.2013, 19:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2013, 19:57
Привет! Вот еще темы с ответами:

ЕГЭ по информатике - Информатика
Всем привет! Я учусь в 10 ом классе, и у меня в школе на уроках информатики мы не заходили дальше переписывания текста в ворд. Сейчас я...

Егэ по информатике - Информатика
Как это решать? И как решить проще В8 и быстрей, вместо того, чтобы всё это писать, писать, писать. Возможно как-то это легко и просто...

ЕГЭ по информатике - C#
Помогите пожалуйста решить задачу. На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на...

ЕГЭ по информатике - Программирование
Объясните, пожалуйста, что означает знак &quot;V&quot; и перевернутая &quot;V&quot; и знак &quot;_&gt;&quot; в следующем задании: Правильный ответ:...


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

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

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