2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Игровая задача С3 ЕГЭ по информатике
Сообщение18.04.2012, 00:20 
Игровая задача С3 ЕГЭ по информатике :
в кучке N камней 2 игрока кидают камни по очереди. За 1 ход можно вытянуть m1 или m2 камня.
Выигрывает тот кто берёт последние камни..
Решается эта задача построением и анализом дерева игры.
Естественно вручную школьникам реально анализировать не очень большие деревья. Поэтому написана программа на С выполняющая этот анализ.Т.е
а)построение дерева игры,
б)анализ 4 подслучаев:
1)1 игрок сделал ход m1 и при всех вариантах выиграл 1й (выигрышная позиция 1-го)
2)1 игрок сделал ход m1 и при всех вариантах выиграл 2й (проигрышная позиция 1-го)
3)1)1 игрок сделал ход m2 и при всех вариантах выиграл 1й (выигрышная позиция 1-го)
4)2)1 игрок сделал ход m2 и при всех вариантах выиграл 2й (проигрышная позиция 1-го)
Программа строит дерево рекурсивно и выполняет его анализ также в рекурсивной функции.
Программа для заданного N просматривает всевозможные варианты 1<=m1<m2<=N/2 на предмет выигрышных и проигрышных
позиций. см Изображение
Собственно вопрос по обобщениям этой задачи и практическим применениям, скажем в экономике.
1 часть вопроса - ну скажем куч может быть несколько, игроков может быть 3, 4,...
(правда тогда программа резко усложняется за счет отказа от модели двоичного дерева и замены его n-ичным)

2 часть вопроса понятна - с т.зр. взрослых людей результаты по каким-то камушкам несерьезны

 
 
 
 Re: Игровая задача С3 ЕГЭ по информатике
Сообщение18.04.2012, 15:15 
eugrita в сообщении #561322 писал(а):
Решается эта задача построением и анализом дерева игры.
Вам деревья мешают увидеть лес.
eugrita в сообщении #561322 писал(а):
Естественно вручную школьникам реально анализировать не очень большие деревья
Вручную можно проанализировать любую начальную позицию. И анализ будет по модулю $m_1+m_2$

 
 
 
 Re: Игровая задача С3 ЕГЭ по информатике
Сообщение18.04.2012, 18:20 
А если лень возится с модулями, можно просто. Представим себе масив М[1,N] из N элементов - единички или двойки - у кого выгрышная стратегия. Понятно что при $k\le m_2, M(k)=1$ Дальше для $m_2+1\le k \le N$, если $M(k-m_1)=2 \text { или } M(k-m_2)=2, M(k)=1 \text { иначе } M(k)=2$
Причем масив может быть не из N, а из $m_1+m_2$ элементов - остатки по модулю $m_1+m_2$.

По другому вопросу, если игроков больше 2, то о в выгрышной стратегии не может идти речь. Если у меня нет выгрышной стратегии, то я могу помогать одному или другому игроку, так что...

 
 
 
 Re: Игровая задача С3 ЕГЭ по информатике
Сообщение19.04.2012, 12:19 
Хорошо это все так. А как классифицировать с т.зр. теории игр данные задачи?
Ясно что игры не матричные, не дифференциальные.
Какой самый общий тип такой игры, и где в экономики аналоги задач приводящих к такому или примерно такому типу?

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group