algorithm - 将任何一个数字减少到 0 的最佳方法

Question

给定两个数字 n和 m , 只允许一个操作即

我们只能减去较小数字的倍数并且它不能为零，即每轮至少必须减去 1。

如何找到将任意一个数归为0的最优路径？

我尝试使用以下规则:

• 如果gcd(m, n) == min(m, n)然后转一圈
• 如果(n % (m % n) == 0 and n + (m % n) < m)然后2轮

if(__gcd(a, b) == min(a, b) || __gcd(a, b) == 1 || (n % (m % n) == 0 && n + (m % n) < m))
   cout << "Win";
else
   cout << "Lose";

预期结果显示如果有人从头开始并且有 2 个玩家在玩，无论第一个玩家是赢还是输，考虑到每个人都玩得最好

例如

1 1
Win
4 4
Win
4 6
Lose

Answer 1

根据你的问题陈述，只有两种情况:

1. 如果开始游戏的人数较少，他将在第一步中获胜。
2. 如果大量开始游戏，则如果 gcd(m,n) == min(m,n)
   然后在第一步中更大的胜利别的在第二步中，小者获胜