[中譯] ProjectEuler 400 Fibonacci tree game

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者babufong (嗶嗶)時間13年前 (2012/10/31 08:45)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

400. Fibonacci tree game http://projecteuler.net/problem=400 費氏樹是一個二元樹，定義為： ‧T(0) 是空的樹。 ‧T(1) 是二元樹，有一個節點。 ‧T(k) 有一個根節點，底下包含了 T(k-1) 跟 T(k-2)，作為根節點的延伸的枝幹。在這樣成長下的樹，兩個玩家進行了一個"分別拿走"的遊戲。在玩家的回合中，選擇一個節點拿走，若節點下有附掛其他延伸的枝幹，則一併帶走。最後把整株費氏樹拿光的玩家為輸。底下是幾個先手必勝選擇的例子，從 k=1 到 k=6（詳見附圖網址）。 http://projecteuler.net/project/images/p400_winning.png

使 f(k) 為在 T(k) 中，先手必勝選擇的數量（換句話說，後手無論採取什麼策略皆無法取勝）。舉例來說，f(5) = 1，f(10) = 17。請求出 f(10000)。給出末 18 位數作為您的答案。 ------------------------------------------------------------------------------ 遲來的翻譯，50席已經坐滿了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.3.42