拿石头子题解答

constant · 发表于 2006-6-11 20:03:21

刚看见拿石头子题，可是觉得有点奇怪。大家记性都不错，特别是husonghu兄，什么犄角旮旯的题都记得，怎么偏偏忘了这个？

这种游戏叫做NIM，要用二进位数来解。把各堆的石头数表成二进位数，每位分别相加，如果至少有一个是奇数，就是胜状态，否则是负状态。例如3，5，7，表成二进位数为11，101，111。每位分别相加，得2，2，3，因此是胜状态，拿的时候给对方留下负状态就行了，可以从任意一堆拿一个。

再比如，7，10，13，表成二进位数为111，1010，1101。每位分别相加，得2，2，2，2，是负状态，不可能赢。

Ein · 发表于 2006-6-11 20:45:59

确是数学高手！思路正确，但解法仍有误。

constant · 发表于 2006-6-12 00:53:29

这是拿最后一个赢的走法，拿最后一个输时有一点不一样。当还剩一堆有多余一块石子时，要剩下奇数个。例如3，1，1时，拿最后一个赢时把3个的一堆拿光，剩下1，1。拿最后一个输时留下一个，剩下1，1，1。

Ein · 发表于 2006-6-12 06:24:10

不仅如此。

husonghu · 发表于 2006-6-12 06:46:15

constant · 发表于 2006-6-12 17:59:34

不是。见这个下面的第二题解法。

这是最有名的题之一，到处都有的，类似的变种也多极了，例如ob贴过的bowling题。

husonghu · 发表于 2006-6-12 20:11:26

啊，我说呢！只记得康大帝了，把大帝加冕之前的姓名给忘了。不过我记得确实有不少这类题

Ein · 发表于 2006-6-17 20:09:57

回复：高手们快顶啊

		自动登录	找回密码
密码			立即注册

动态微博