微机/数学高手救命啊,小弟快想疯了

来源:百度知道 编辑:UC知道 时间:2024/05/10 12:25:44
输入k及k各整数,n1,n2,n3...nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni,接着便是你和计算机的对弈游戏:轮流取火柴,每次只许从任意一堆中拿取,取的根数不限(但不可不取),谁拿到最后一根谁输。由你决定谁先取。如何保证获胜?
注意:谁拿到最后一根谁输。
例如:针对1,3,5,7 该怎么下手?
这一题已经纠缠我3年了,11月19号我又要参加微机编程竞赛,请大家帮帮忙吧!

我在游戏大航海时代玩过,招一个人,和他玩取金币的游戏,大概也是你这样的问题,不好意思,忘啦,有时间你去玩下大航海就知道了!
:)

很经典的一个问题~

你把所有数写成二进制,然后计算一下它们的(按位的)异或,自己研究一下就可以找到规律了。不算很难,挺有意思~

1,3,5,7的话~

001
011
101
111
————
000(异或说白了就是查下“一”的个数)

结果是零,所以这是个制胜位置,即拿成这个状态的人获胜,现在该谁拿谁输~(汗)~

我当时遇到的问题是谁拿最后一根算赢,如果算输的话,只有一点不同,即N堆火柴,每堆一根的情况。算赢的话N为偶数是制胜位置,输的话是奇数——注意这时不能仅仅简单计算异或~

至于非制胜位置怎样拿成制胜位置,楼主自己思考下吧,让他们异或得零(除掉特殊情况)即可~

PS:跟大航海时代四的那个不同,那个是一堆硬币,每人轮流取,至少一根至多三根,不可不取,谁拿最后一根算输,相比楼主的问题简单的多,制胜位置为:
4k+1(k∈N)
保证每次拿成制胜位置,稳胜~游戏中开始硬币数是随机,若是电脑拿成了制胜位置,哭吧~

PS2:大航海时代四中那个取硬币的游戏是在一个圆桌面上进行的,每次玩总让我想起一个更古老的硬币游戏:两人轮流在桌面上放硬币,每人每次放一个,谁放不下了算输。数学家说:要是我,一定选择先放!——第一枚放圆桌中间,然后每次放在跟对手对称的位置上,若你放得下,我当然也有地方,此一先手正中硬币一枚称为制胜位置——我看的书那么举例的~佩服啊,俺作为数学专业一员,能有此境界,足矣!~

祝快乐及顺利~