向高手请问一个初中生需要解决的有关问题
向高手请教一个初中生需要解决的问题.
2006年信息学奥林匹克竞赛初中组试题中如下一道题:
(取石子游戏) 现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取), 取最后一颗石子的一方获胜。甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜)?如果有,甲第一步应该在哪一堆里取多少?请写出你的结果:
和几位同事一起讨论过,也不知究竟.真是惭愧!
诚心向高手请教!!
------解决方案--------------------
http://topic.****.net/u/20071010/21/ccffd8f0-0cfb-45d0-8ed0-47c28eb5d69c.html
------解决方案--------------------
你这个貌似和他的不一样,至少你没有限制每次取多少
------解决方案--------------------
惭愧,我的帖里面有误,题目应该是:m 个棋子为成 n 堆(不一定均匀),每次至多取一堆,至少拿 1 个.拿到最后一个的为赢家. 这样就跟楼主的题一致了.
------解决方案--------------------
如atyuwen所说
具体算法如下:
3=11
5=101
7=111
19=10011
50=110010 然后相加,但没有进位,其本质其实就是2的倍数的问题
如果轮到谁拿的时候,相加结果全为0,则败。
例如本题:
000011
000101
000111
010011
+110010
--------
100000 为了消去1,故110010--->010010所以50中拿去32个
接下来的事,就是根据对手变化而变化,只要让对手行动之时,相加之和全为0即可稳操胜券。
2006年信息学奥林匹克竞赛初中组试题中如下一道题:
(取石子游戏) 现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取), 取最后一颗石子的一方获胜。甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜)?如果有,甲第一步应该在哪一堆里取多少?请写出你的结果:
和几位同事一起讨论过,也不知究竟.真是惭愧!
诚心向高手请教!!
------解决方案--------------------
http://topic.****.net/u/20071010/21/ccffd8f0-0cfb-45d0-8ed0-47c28eb5d69c.html
------解决方案--------------------
你这个貌似和他的不一样,至少你没有限制每次取多少
------解决方案--------------------
惭愧,我的帖里面有误,题目应该是:m 个棋子为成 n 堆(不一定均匀),每次至多取一堆,至少拿 1 个.拿到最后一个的为赢家. 这样就跟楼主的题一致了.
------解决方案--------------------
如atyuwen所说
具体算法如下:
3=11
5=101
7=111
19=10011
50=110010 然后相加,但没有进位,其本质其实就是2的倍数的问题
如果轮到谁拿的时候,相加结果全为0,则败。
例如本题:
000011
000101
000111
010011
+110010
--------
100000 为了消去1,故110010--->010010所以50中拿去32个
接下来的事,就是根据对手变化而变化,只要让对手行动之时,相加之和全为0即可稳操胜券。