有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。输入 输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。输出 输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。样例输入复制 2 1
时间: 2024-03-03 21:50:18 浏览: 29
以下是使用递归的C++代码实现:
```c++
#include <iostream>
using namespace std;
bool f(int a, int b) {
if (a == 0 && b == 0) { // a和b都为0,先手必败
return false;
} else if (a == 0 && b != 0) { // a为0,b不为0,先手必胜
return true;
} else if (a != 0 && b == 0) { // a不为0,b为0,先手必胜
return true;
} else { // a和b都不为0
bool p = !f(a-1, b); // 先手从a中取走1个石子
bool q = !f(a, b-1); // 先手从b中取走1个石子
bool r = !f(a-1, b-1); // 先手从a和b中同时取走1个石子
return p || q || r; // 存在一种取法,先手必胜
}
}
int main() {
int a, b;
while (cin >> a >> b) {
if (f(a, b)) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
}
return 0;
}
```
使用动态规划的方法可以优化递归算法的效率,避免重复计算。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)