algorithm - 决定 'Jumping Jack' 的算法

Question

前一段时间在一次编程比赛中我遇到了一个令人费解的问题，此后一直困扰着我。虽然我没有逐字记住，但我会尽力重现:

Jack starts at 0 on the number line and jumps one unit in either direction. Each successive jump he makes is longer than the previous by 1 unit, and can be made in either direction. Write a program that takes a number and returns the minimum number of jumps Jack makes to reach that number.

如果这不是一个好问题，或者标题被认为具有误导性，我提前道歉。

Answer 1

我想详细说明@supercat 的正确和快速解决方案，并描述一种算法，除了计算这样一个和的长度之外，还计算一个最小长度和。

算法

找到满足 t_k := 1 + 2 + 3 + ... + k >= |n| 的最小整数 k t_k 与 |n| 具有相同的奇偶性。然后系统地将t_k的被加数的符号翻转为总n。

这里是详细信息。注意 t_k = k(k + 1)/2，一个三角数。设置 t_k = |n|求解 k 给出 (-1 + sqrt(1 + 8|n|))/2 的上限。所以 k 等于上限或 1 或 2 加上它，这三个数字中的任何一个与 n 具有相同的奇偶校验并且是最小的。这里我们使用了这样一个事实，即三个连续三角形数的集合 {t, t + s, t + s + (s + 1)} 包含任何正整数 t, s 的偶数和奇数。(只需检查 t 和 s 的所有四种奇偶校验可能性。)

要找到 n 的最小长度和，首先计算 d := (t_k - n)/2。因为 t_k >= |n| t_k 和 n 具有相同的奇偶性，d 位于集合 {0, 1, 2, ..., t_k} 中。现在重复减去:d = a_k(k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., r_2 = a_1 (1) + r_1，选择每个a_i在 {0, 1} 中最大化。根据下面的引理，r_1 = 0。所以 d = sum_{i=1}^k a_i i。因此 n = t_k - 2d = sum_{i=1}^k i - sum_{i=1}^k 2a_i i = sum_{i=1}^k (1 - 2a_i) i 和 1 - 2a_i 位于 {-1 , 1}。所以序列 b_i := 1 - 2a_i 是一条路径，并且根据 k 的最小值，b_i 是一条最小路径。

算法示例

考虑目标数 n=12。根据算法 3，k 的可能性为 5、6 或 7。t_k 的对应值为 15、21 和 28。由于 28 是其中与 n 具有相同奇偶性的最小值，因此我们看到 k=7 .所以d = (t_k - n)/2 = 8，我们按照算法记为1 + 7。因此，到 12 的最短路径是 -1 + 2 + 3 + 4 + 5 + 6 - 7。

我说 最短路径，因为最短路径通常不是唯一的。例如，1 + 2 -3 + 4 - 5 + 6 + 7 也可以。

算法正确性

引理:令 A_k = {0, 1, 2, ..., t_k}。那么一个数在A_k中当且仅当它可以表示为{0, 1}中某个序列a_i的和sum_{i=1}^k a_i i。

证明:通过对 k 的归纳。首先，0 = sum_{i=1}^0 1，空和。现在假设结果对所有 k - 1 >= 0 都成立，并假设数字 d 位于 A_k 中。反复相减:d = a_k(k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., 在{0, 1中选择每个a_i = 0或1最大} 并在第一个 r_j 位于 A_j 中且对于某些 j < k 时停止。然后通过归纳假设，r_j = sum_{i=0}^j b_i i 对于 {0, 1} 中的一些 b_i。然后根据需要 d = r_j + sum_{i=j+1}^k a_ki i。相反，a_i 在 {0,1} 中的和 s := sum_{i=1}^k a_i i 满足 0 <= s <= sum_{i}^k i = t_k，因此 s 位于 A_k 中。

算法时间复杂度

假设算术运算是常数时间，从 n 计算 k 需要 O(1) 时间，因此计算到 n 的最小路径的长度。然后它需要 O(k) 时间来找到 d 的最小长度和，然后 O(k) 时间使用该和来产生 n 的最小长度和。所以 O(k) = O(sqrt(n)) 时间全部结束。