l**n
发帖数: 88 | 1 前面的帖子说用fibonacci数列，但是没怎么搞明白
两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话 | l******o
发帖数: 144 | 2 不知道是不是想错了, 但觉得和fibonacci没有关系. 这些数目先手必输:
1 2 3 5 8 12 18 27 41 62 93 ...
递推关系是 a_{n+1} = ceil(a_n * 1.5).
其他数目先手必胜, 因为可以拿掉相应的数目让对手面临上面的必输情况.
至于为什么, 我也说不太清楚, 我是从1,2,3往上一个一个推的, 然后归纳出来的. 而
且我也不确定是不是正确.
前面的帖子说用fibonacci数列，但是没怎么搞明白
两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话
【在 l**n 的大作中提到】
: 前面的帖子说用fibonacci数列，但是没怎么搞明白
: 两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
: 1. 第一个人不能一次拿光所有的
: 2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
: 求先拿者必胜策略, 如果有的话
| j******y
发帖数: 3 | 3 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
【在 l******o 的大作中提到】
: 不知道是不是想错了, 但觉得和fibonacci没有关系. 这些数目先手必输:
: 1 2 3 5 8 12 18 27 41 62 93 ...
: 递推关系是 a_{n+1} = ceil(a_n * 1.5).
: 其他数目先手必胜, 因为可以拿掉相应的数目让对手面临上面的必输情况.
: 至于为什么, 我也说不太清楚, 我是从1,2,3往上一个一个推的, 然后归纳出来的. 而
: 且我也不确定是不是正确.
:
: 前面的帖子说用fibonacci数列，但是没怎么搞明白
: 两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
: 1. 第一个人不能一次拿光所有的
| l******o
发帖数: 144 | 4 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
【在 j******y 的大作中提到】
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
| l******o
发帖数: 144 | 5 很好奇, 如果把2倍改成3倍, 结果会是怎么样的?
哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
【在 l******o 的大作中提到】
: 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
:
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
| g*******y
发帖数: 1930 | 6 前几个必输的数:
2,3,4
然后接下来必输的数:
6 = 2+4 2,3,4,6
再接下来：
8 = 2+6 2,3,4,6,8
11= 3+8 2,3,4,6,8,11
15= 4+11 2,3,4,6,8,11,15
21= 6+15 2,3,4,6,8,11,15,21
...
for n>=5:
f(n) = f(n-1) + f(n-4);
有没有一个更general的推广，比如2倍改成n倍。。。
【在 l******o 的大作中提到】
: 很好奇, 如果把2倍改成3倍, 结果会是怎么样的?
:
: 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
| g*******y
发帖数: 1930 | 7 我第一次做这个题的时候，也是犯了这个错误。
13是必败的，那按照你的递推式下一个必败的数是，13*1.5+1 = 20，就错了
事实上，21才是必输的数。
<=k+(int)((k-1)/2)块石头时，我方拿x-k块石头便必胜了。于是有序列： | s********l
发帖数: 648 | 8 先mark一下, 等一下再来做题
【在 l**n 的大作中提到】
: 前面的帖子说用fibonacci数列，但是没怎么搞明白
: 两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
: 1. 第一个人不能一次拿光所有的
: 2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
: 求先拿者必胜策略, 如果有的话
| x***y
发帖数: 633 | 9 Yeah, you are right....all the f(n) for n>2 are losers (1 is not considered
here)....First f(3) f(4) f(5) f(6) are all losers,all the other numbers
less than f(6) are winning and then using mathematical induction, assume for
all n>3, f(n) are all losing positions and other non-fabonacci numbers less than f(n) are winning. For any number k between f(n) and f(n+1) (totally f(n-1)-1 numbers
), if k<=f(n)+f(n-2), diretcly move to f(n) (as f(n)=f(n-1)+f(n-2)>2f(n-2),
the opponent can not take all in
【在 j******y 的大作中提到】
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个， 必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n
| n******h
发帖数: 50 | 10 若倍数限制不是2倍，而是k倍，那么必败数列A为：
A(1)=2，A(2)=3，...，A(k)=k+1，之后有
A(.)=A(i)+A(n), for any i such that i=A(n).
当k=2时，A恰巧为fib series.
【在 g*******y 的大作中提到】
: 前几个必输的数:
: 2,3,4
: 然后接下来必输的数:
: 6 = 2+4 2,3,4,6
: 再接下来：
: 8 = 2+6 2,3,4,6,8
: 11= 3+8 2,3,4,6,8,11
: 15= 4+11 2,3,4,6,8,11,15
: 21= 6+15 2,3,4,6,8,11,15,21
: ...
|
|
