比较难的博弈问题

拿石子问题

一般考虑两种方法：

1. 思考问题的规律，直接根据某些特性进行判断
2. 递归

0917（Li）

• 两堆石子，你先拿。每次只能从数目多的堆中拿石子，且拿的石子数为另一个堆的整数倍。能拿到某个堆最后一个石子的人获胜。问：你是否能获胜？
  • 思考了很久：方法一 - 直接找出特性 -> 没有想出来
  • 转递归方法：

    bool dfs(int x, int y)
    {
    	if (x < y) swap(x, y);
    	if (x % y == 0) return true;
    	/**
    	* 这一步比较难🤔：
    	* == 1时，必须拿
    	* x / y > 1时，拿的数量可以控制
    	* --> 考虑剩下一个整数倍：如果后续为true，则OK
    	* --> 考虑剩下一个整数倍：如果后续为false，则改变策略
    		* 拿走(x / y -1)个整数倍：则获胜
    	* --> 因此，这种情况下，必胜
    	*/
    	if (x / y > 1) return true;
    	return !dfs(y, x % y);
    }