Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Самое высокое дерево выигрыватет! Оптимальная стра 
:(
    Опции темы
Bubby
Дата 23.5.2011, 13:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 23.5.2011

Репутация: нет
Всего: нет



Добрый день всем!

Помогите пожайлуста с решением задачки по алгоритмике. Знаю что существует оптимальное решение, но никак не могу найти его.
Проблема состоит в оптимальной стратегии в компетитивном "выращивании" бинарных деревьев. Выигрывает тот у кого в конце игры дерево самое большое (наибольшее количесво уровней).

Цель игры, сконструировать самое высокое бинарное дерево за 1000 ходов, зная что это конкурс с другим игроком. 
На каждом ходу, раздаёться 100 очков на два дерева, при этом, только листья деревьев могут каптировать эти очки-энергию.
Листья находящияся на самом выкоком уровне захватывают энергию первыми. Количество захваченной энергии так-же зависит от возраста листа...
(при создании, возраст листа или узла равен нулю, и увеличиваеться на один на каждом ходу). 
На каждом ходу, дерево так-же должно заплатить "расходы на техническое обслуживание", которые расщитываються следующим образом:

-если узел = лист
-если его возраст меньше 10 : он ни чего не стоит
-иначе : age-10/990
-если узел не лист
-если его возраст меньше 10
-если у него один сын : его расходы стоят 1 очко
-если у него два сына : 0 очков
-если его возраст находиться между 10 и 499
-если у него один сын : 1-|log500((500-age)/500)
-если у него два сына : sin(age*pi/500)
-если его возраст больше чем 500, он ничего не стоит

Если у игрока осталась энергия после расходов на обслуживание дерева, он может выбрать действие:
-ни чего ни делать 
-добавить поддерево на выбранный узел; добавить дерево с н - количеством узлов стоит 2^(н-1)
-удалить поддерево (вместе с выбранным узлом), и стоит это половину обслуживания этого поддерева


Помогите пожайлуста найти оптимальную стратегию констуирования такого дерева! 
Такую, чтобы выигрывать каждую игру (такая стратегия существует).
Большое спасибо!!!  smile 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0403 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.