Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.11.2010, 22:37
Новичок

Отправить личное сообщение для Invader Посмотреть профиль Найти все сообщения от Invader
 
Регистрация: 26.07.2007
Сообщений: 4

Построение оптимального дерева игры
Доброе время суток!

Есть задание С3 из егэ по информатике. Заключается оно в следующем:

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2,–1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Задача: нужен алгоритм построения оптимального дерева игры.

Т.к. данный алгоритм требуется для виртуального тренажера, то пусть 1й угрок - человек, 2й игрок - компьютер. Собственно оптимальное дерево игры нужно для компьютера.

Есть некоторые задумки: Строим полное дерево игры.
Листьям, в которых выигрывает компьютер, ставим некий коэффициент в 1. Если выигрывает человек - "-1". Далее, возвращаясь в рекурсии вверх в каждом узле суммируем коэффициенты потомков.

Будет ли правильным такой алгоритм и можно ли его как-то оптимизировать?
  #2  
Старый 30.11.2010, 23:33
гость

 
Сообщений: n/a

какое нахер дерево?! обычная игра для двух игроков на графе. размечаешь вершины как выигрышные/проигрышные по обычным рекурсивным правилам (из выигрышной есть ход в проигрышную, из проигрышной все ходвы в выигрыщную) и все. даже набумажке можно зделать
  #3  
Старый 01.12.2010, 23:29
Новичок

Отправить личное сообщение для Invader Посмотреть профиль Найти все сообщения от Invader
 
Регистрация: 26.07.2007
Сообщений: 4

Суть задания и заключается в том, что ученик должен построить дерево игры. а мне его надо проверить.
  #4  
Старый 02.12.2010, 02:07
гость

 
Сообщений: n/a

Сообщение от Invader Посмотреть сообщение
Суть задания и заключается в том, что ученик должен построить дерево игры. а мне его надо проверить.
а вы что его составитель? ну и рисуй свое дерево до следующего прихода христа. а я лучше за пять минут нарисую граф и пойду пить чай
  #5  
Старый 02.12.2010, 17:42
Новичок

Отправить личное сообщение для Invader Посмотреть профиль Найти все сообщения от Invader
 
Регистрация: 26.07.2007
Сообщений: 4

Сообщение от гость Посмотреть сообщение
а вы что его составитель? ну и рисуй свое дерево до следующего прихода христа. а я лучше за пять минут нарисую граф и пойду пить чай
Ну можно так сказать. Я виртуальный тренажер по егэ программирую, для дистанционного обучения. Поэтому нужно дерево.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Модификация игры Ним OwnYou Задачи 15 14.03.2011 19:44
ИИ для игры Кьюбик coddy Искусственный интеллект, нейронные сети 1 12.03.2010 14:50
Задача на поиск оптимального значения Eugene86 Математические алгоритмы (другое) 5 23.01.2010 16:10
вариация игры Ним гость Математические алгоритмы (другое) 3 19.08.2009 18:49
Построение дерева синтаксического разбора Lamer#1 Реализация, исходники, языки 1 05.05.2008 15:05