作者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