我们可以通过递增的跳跃到达所有的石头吗
Can we reach all the stones by incremented jumps
有N块石头排成一圈。一只青蛙坐在第一块石头上。青蛙一直按顺时针方向从一块石头跳到另一块石头。它每次跳跃都会以 1 的增量跳过石头。即，对于第一次跳跃，它将跳过 0 个石头，第二次跳跃将跳过一个石头，第三次跳跃将跳过 2 个石头，依此类推。
任务是，给定石头的数量 N，看看青蛙是否能到达所有的石头。
例如：
N=1 ---> 真
N=2 ---> 真 --> 跳跃=(1,2)
N=3 ---> 假 --> 跳跃=(1,2,1,1,2,1,1,2,1.....)
N=4 ---> 真 --> 跳跃=(1,2,4,3)
我已经尝试了不同的 N 值。我所能看到的是，如果 N 是 2 的幂，那么所有的石头都可以到达。此外，如果在访问所有石头之前不止一次访问了任何石头，则答案为假。我找不到观察结果的推理，因此无法证明。
我认为您的思考方式有误。不要误会我的意思，进行数学分析并得出一个简单的结果是很酷的，比如，“当且仅当 N 是 2 的幂时，所有的石头都可以到达。 “ （事实上，我相信那个结果是正确的。）但是你不需要找到那种结果来编写可以回答问题的算法。
相反，您的算法可以只模拟青蛙的跳跃（您显然已经知道该怎么做），并查看它是否击中了所有石头。唯一棘手的部分是青蛙计划永远继续跳跃，显然您希望您的算法在有限的时间内完成。关键的见解是青蛙的跳跃序列总是以循环结束，因此您只需要继续模拟该序列足够长的时间以确保您已进入循环并完成一次循环。
我们怎么知道的？
想知道为什么，假设我们知道青蛙刚从石头#i跳到石头#j。这足以告诉我们青蛙下一步会跳到哪里吗？答案是肯定的；我们不知道青蛙是否 认为 它跳过了 j−i−1 石头与 N+j−i−1 石子对 2N+j−i−1 石头之类的，但这没关系，因为它落在的下一块石头不依赖于下一次跳跃是否跳过 j−i stones vs. N+j−i石子对2N+j−i 石头 — 这些都是等价的。因此，如果我们知道它的最后一跳，那么我们就知道它的下一跳，如果我们知道它的下一跳，那么我们就知道下一跳，依此类推：所以这一跳就足以确定石子序列的其余部分。
这意味着至多有 N2 个可能的“状态”，序列可以处于，始终由先验石块决定和下一块石头，其中每个状态完全决定所有后续状态。因此，如果您通过至少 N2 个状态来模拟序列，那么要么您只访问了每个状态一次，要么您访问了某个状态至少两次（根据鸽笼原则），所以你一定会到达你要去的所有州，这意味着你一定会降落在你要去的所有石头上。
在 O(N2) 时间内给你一个算法并且 O(N) space.
您可以通过
来改进它
- 跟踪您已经访问过哪些状态，并在您发现已返回状态后立即终止。
- 跟踪您已经降落了多少石头，并在您发现所有石头都降落后立即终止。
这将在 O(N) 时间内完成，如果你是对的“如果任何石头被访问不止一次在访问所有石头之前，答案是错误的”，同时仍然表现正确（并且仍在 O(N2 ) 时间) 如果那个理论是错误的。
有N块石头排成一圈。一只青蛙坐在第一块石头上。青蛙一直按顺时针方向从一块石头跳到另一块石头。它每次跳跃都会以 1 的增量跳过石头。即，对于第一次跳跃，它将跳过 0 个石头，第二次跳跃将跳过一个石头，第三次跳跃将跳过 2 个石头，依此类推。 任务是，给定石头的数量 N，看看青蛙是否能到达所有的石头。
例如：
N=1 ---> 真
N=2 ---> 真 --> 跳跃=(1,2)
N=3 ---> 假 --> 跳跃=(1,2,1,1,2,1,1,2,1.....)
N=4 ---> 真 --> 跳跃=(1,2,4,3)
我已经尝试了不同的 N 值。我所能看到的是，如果 N 是 2 的幂，那么所有的石头都可以到达。此外，如果在访问所有石头之前不止一次访问了任何石头，则答案为假。我找不到观察结果的推理，因此无法证明。
我认为您的思考方式有误。不要误会我的意思，进行数学分析并得出一个简单的结果是很酷的，比如，“当且仅当 N 是 2 的幂时，所有的石头都可以到达。 “ （事实上，我相信那个结果是正确的。）但是你不需要找到那种结果来编写可以回答问题的算法。
相反，您的算法可以只模拟青蛙的跳跃（您显然已经知道该怎么做），并查看它是否击中了所有石头。唯一棘手的部分是青蛙计划永远继续跳跃，显然您希望您的算法在有限的时间内完成。关键的见解是青蛙的跳跃序列总是以循环结束，因此您只需要继续模拟该序列足够长的时间以确保您已进入循环并完成一次循环。
我们怎么知道的？
想知道为什么，假设我们知道青蛙刚从石头#i跳到石头#j。这足以告诉我们青蛙下一步会跳到哪里吗？答案是肯定的；我们不知道青蛙是否 认为 它跳过了 j−i−1 石头与 N+j−i−1 石子对 2N+j−i−1 石头之类的，但这没关系，因为它落在的下一块石头不依赖于下一次跳跃是否跳过 j−i stones vs. N+j−i石子对2N+j−i 石头 — 这些都是等价的。因此，如果我们知道它的最后一跳，那么我们就知道它的下一跳，如果我们知道它的下一跳，那么我们就知道下一跳，依此类推：所以这一跳就足以确定石子序列的其余部分。
这意味着至多有 N2 个可能的“状态”，序列可以处于，始终由先验石块决定和下一块石头，其中每个状态完全决定所有后续状态。因此，如果您通过至少 N2 个状态来模拟序列，那么要么您只访问了每个状态一次，要么您访问了某个状态至少两次（根据鸽笼原则），所以你一定会到达你要去的所有州，这意味着你一定会降落在你要去的所有石头上。
在 O(N2) 时间内给你一个算法并且 O(N) space.
您可以通过
来改进它- 跟踪您已经访问过哪些状态，并在您发现已返回状态后立即终止。
- 跟踪您已经降落了多少石头，并在您发现所有石头都降落后立即终止。
这将在 O(N) 时间内完成，如果你是对的“如果任何石头被访问不止一次在访问所有石头之前，答案是错误的”，同时仍然表现正确（并且仍在 O(N2 ) 时间) 如果那个理论是错误的。