作者ACGfans (菜心)
看板puzzle
標題Re: [轉錄] 益智問題（拈之變形）
時間Mon Apr 20 22:39:13 2009
原文恕刪
以前上演算法時有看過類似的題目
只是當時的題目是兩倍
我把之前做的題目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
1F：推 FACE90006:請問n是不是應該大於等於3呀?? 04/20 23:05
2F：推 puzzlez:還真是難懂啊....囧（攤手） 04/20 23:14
3F：推 stimim:可是，如果現在有32個，那拿法應該是32->29而不是32->21 04/20 23:16
4F：→ stimim:如果走32->21的話，對手可以拿11*2=22 > 21個，就贏了 04/20 23:17
5F：→ FACE90006:原PO意思 是如果一開始火柴的個數為Fibonacci數 04/20 23:26
6F：→ FACE90006:對於第一個取的人 是不利的... 04/20 23:26
7F：推 stimim:可是一開始的時候不見得是Fibonacci數啊 04/20 23:28
8F：→ FACE90006:如果一開始火柴的個數"不"為Fibonacci數 則是有利的 04/20 23:31
9F：推 stimim:可是這題的重點不就是在於，你知道對你有利，但你有沒有辦 04/20 23:33
10F：→ stimim:法在合理的時間內找到必勝方法 04/20 23:34
12F：→ FACE90006:game/104.htm 不會縮網址0.0 04/21 00:06
13F：推 stimim:這種方法真妙 04/21 00:10