Здравствуйте. На днях столкнулся с задачей по программированию, в которой перед тем как начать писать код, надо еще хорошо подумать.

Для начала определение дерева Фибоначчи

Дерево Фибоначчи - это двоичное дерево, рекурсивно задаваемое следующим образом:

T(0) - пустое дерево.

T(1) - двоичное дерево с одним узлом.

T(k) состоит из корневого узла, имеющего T(k-1) и T(k-2) в качестве потомков.

А вот сама задача:

Есть дерево Фибоначчи, и из него двое по очереди удаляют узлы. Проигрывает тот, кому приходится удалить последний узел. Удаление узла означает, что удаляется и все, что в него входило (например в узел F(k) входят узлы F(k-1) и F(k-2), при удалении узла F(k) эти два тоже удаляются и то, что входило в них тоже и тд). Вопрос стоит в том, какое количество выигрышных ПЕРВЫХ шагов есть у первого игрока в дереве F(k) (имеется ввиду, что после такого хода, у второго игрока шансов на победу уже не будет).

Мои мысли:

Я пробую решать от поиска выигрышной стратегии у второго игрока, если первый игрок сделает первый ход не выигрышным. Но что-то пока получается не очень. Также как и определить в чем может заключаться стратегия первого игрока.

Самая толковая идея на данный момент: первым ходом первый игрок должен определить четность оставшихся узлов (их должно остаться нечетное количество, в ином случае, его точно ждет проигрыш).

Пожалуйста, помогите понять, в каком направлении думать

задан 30 Окт '20 4:55

изменен 30 Окт '20 11:09

@Airisa: такие понятия как "дерево Фибоначчи" желательно сопровождать определением. Это специальное понятие из довольно узкой области, поэтому не все знают или помнят, что это значит. К тому же оно, наверное, не единственно, а как-то зависит от параметров, поэтому надо уточнить постановку задачи.

(30 Окт '20 6:30) falcao

@falcao: поправил

(30 Окт '20 11:10) Airisa

@Airisa: по-моему, в таком виде получается что-то совсем простое. Может быть, тут какая-то более сложная игра имелась в виду? А так -- по индукции доказывается, что первый проиграет всегда, при любом k. Он или проигрывает первым ходом, или выбирает какую-то вершину из F(k-1) или F(k-2). Второй начинает играть на этом поддереве. Если первый делает ход на другом из поддеревьев, то второй ему отвечает там же. И так далее. В итоге второй дожидается проигрыша первого на одном из поддеревьев, и удаляет верхний узел оставшегося поддерева. Первому остаётся удалить головной узел.

(30 Окт '20 16:46) falcao

@falcao: значит я не смог точно передать формулировку задачи. Вот эта задача: http://euler.jakumo.org/problems/view/400.html

(30 Окт '20 17:23) Airisa
1

@Airisa: там несколько не те деревья, на которые я изначально подумал. В таком виде, конечно, тривиальной стратегии нет. Но это же задаче не по математике, а по программированию. Ясно, что такие подбирают специально, где чисто математического решения нет. С очень высокой вероятностью, искать для такой задачи лёгкую стратегию "олимпиадного" типа бесперспективно.

(30 Окт '20 22:04) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×96
×48
×11

задан
30 Окт '20 4:55

показан
319 раз

обновлен
30 Окт '20 22:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru