步数计算器（编程挑战 2023/21）
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个带有障碍物的网格，我们需要计算在给定步数内可到达的所有地块数量（每次只能水平或垂直移动一个地块）。第一部分中，我们需要计算在64步内可到达的地块数量。使用非递归解决方案，使用一个位置堆栈进行访问。第二部分中，网格会根据需要在外部扩展，步数也会改变。通过观察图表，发现了重复的模式，并测量了重复的周期。最后，通过计算结果而不是生成结果来节省时间。
🎯
关键要点
- 给定一个带有障碍物的网格，需要计算在给定步数内可到达的地块数量。
- 第一部分中，计算在64步内可到达的地块数量，使用非递归解决方案和位置堆栈进行访问。
- 第二部分中，网格会根据需要扩展，步数从64变为26,501,365步。
- 扩展网格的算法性能差，可能需要很长时间才能得到答案。
- 通过生成前500步的输出，观察到图表呈现出递增的函数。
- 绘制相邻数字之间的差异，发现存在重复的模式。
- 测量图表中重复的周期，并将每个模式部分提取为单独的变量。
- 一旦确定周期，就可以轻松生成序列中的下一个元素。
- 通过计算结果而不是生成结果来节省时间，使用公式sum(1 .. x) = x * (x + 1) / 2。
➡️
