Re: [轉錄] 益智問題（拈 001,100，1枚~3倍）

看板puzzle作者ACGfans (菜心)時間15年前 (2009/04/20 22:39)推噓8(8推 0噓 6→)

留言14則, 4人參與討論串3/10 (看更多)

原文恕刪以前上演算法時有看過類似的題目只是當時的題目是兩倍我把之前做的題目po出來給大家看看 Consider a variant of Nim game played by two players: Initially, at least two matches are placed on the table between two players. The first player removes as many matches as he likes, except that he must take at least one and he must leave at least one. Thereafter, each player in turn must remove at least one match and at most twice the number of matches his opponent just took. The player who removes the last match wins. Determine a winning strategy for this game. 這題我們後來找出的必勝法跟 Fibonacci數列有關也就是盡量拿完後剩下的數為 Fibonacci數 Fibonacci數列定義 F(n) = F(n-1) + F(n-2) for n>2 F(1) = 1 F(2) = 2 假設目前剩下 N 支火柴則先找最接近 N 且比 N 小的 F(k) 接下來的目標就是拿到剩下 F(k) 支火柴也就是拿掉 N-F(k) 支火柴如果沒辦法一次拿成功則遞迴下去當作剩下 N-F(k) 支火柴的情況下去拿拿完剩下 F(k) 支火柴時接下來又輪到對方拿不管對方拿完剩多少火柴又可以繼續用上述的方法來拿當然如果可以一次全部拿完時就一次拿這樣就直接贏了因此先手要輸的話只有一開始的火柴數剛好為 Fibonacci數時才會輸不過這是兩倍的情形原題目是三倍我想用的技巧應該是差不多才對以上 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.139.132.57

推

FACE90006

04/20 23:05, , 1^F

04/20 23:05, 1^F

推

puzzlez

04/20 23:14, , 2^F

04/20 23:14, 2^F

推

stimim

04/20 23:16, , 3^F

04/20 23:16, 3^F