Bubby
Новичок
|
    
Добрый день всем!
Помогите пожайлуста с решением задачки по алгоритмике. Знаю что существует оптимальное решение, но никак не могу найти его.
Проблема состоит в оптимальной стратегии в компетитивном "выращивании" бинарных деревьев. Выигрывает тот у кого в конце игры дерево самое большое (наибольшее количесво уровней).
Цель игры, сконструировать самое высокое бинарное дерево за 1000 ходов, зная что это конкурс с другим игроком.
На каждом ходу, раздаёться 100 очков на два дерева, при этом, только листья деревьев могут каптировать эти очки-энергию.
Листья находящияся на самом выкоком уровне захватывают энергию первыми. Количество захваченной энергии так-же зависит от возраста листа...
(при создании, возраст листа или узла равен нулю, и увеличиваеться на один на каждом ходу).
На каждом ходу, дерево так-же должно заплатить "расходы на техническое обслуживание", которые расщитываються следующим образом:
-если узел = лист
-если его возраст меньше 10 : он ни чего не стоит
-иначе : age-10/990
-если узел не лист
-если его возраст меньше 10
-если у него один сын : его расходы стоят 1 очко
-если у него два сына : 0 очков
-если его возраст находиться между 10 и 499
-если у него один сын : 1-|log500((500-age)/500)
-если у него два сына : sin(age*pi/500)
-если его возраст больше чем 500, он ничего не стоит
Если у игрока осталась энергия после расходов на обслуживание дерева, он может выбрать действие:
-ни чего ни делать
-добавить поддерево на выбранный узел; добавить дерево с н - количеством узлов стоит 2^(н-1)
-удалить поддерево (вместе с выбранным узлом), и стоит это половину обслуживания этого поддерева
Помогите пожайлуста найти оптимальную стратегию констуирования такого дерева!
Такую, чтобы выигрывать каждую игру (такая стратегия существует).
Большое спасибо!!!
|
Форум
Самое высокое дерево выигрыватет! Оптимальная стратегия
