异想天开

What's the true meaning of light, Could you tell me why

取石子问题

日期:2015-01-13 15:51:55
  
最后更新日期:2015-05-18 18:52:37
题目描述:
Yougth和Hrdv玩一个游戏,拿出n个石子摆成一圈,Yougth和Hrdv分别从其中取石子,谁先取完者胜,每次可以从中取一个或者相邻两个,Hrdv先取,输出胜利着的名字。

输入 输入包括多组测试数据。
每组测试数据一个n,数据保证int范围内。
输出 输出胜利者的名字。
样例输入
2
3
样例输出
Hrdv
Yougth
分析:
两个玩这个游戏,每个人最多只能拿2个石子。记录第一个拿石子的人为A,第二个拿石子的人为B。如果总石子数量为1或2,那么A可以第一次拿完,故A会胜利。那么石子数量为n呢?A会怎么拿?A最多拿两个,那么A肯定会综合n-1个石子和n-2个石子的情况来考虑问题。如果n-1个石子和n-2个石子的情况中,出现了后拿的人会胜利,那么n个石子,先拿的人也会胜利。比如石子数量为3的时候,A先拿,若A拿1或2,到了石子数量为1或2的时候,A就是后拿的人了,而石子数量为1或2的情况都是先拿的人胜利,那么石子数量为3的时候,A一定不会胜利。根据这个逻辑,可以依次递推石子数量为4,5...情况。
table
这样递推后,就会发现B胜利只有石子总数是3的倍数才行,其它情况都是A胜利。
1.取石子的问题