10

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

杰克从数轴上的 0 开始，向任一方向跳跃一个单位。他的每一次连续跳跃都比前一次长 1 个单位，并且可以在任一方向进行。编写一个程序，接受一个数字并返回 Jack 为达到该数字所进行的最小跳跃次数。

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

4

6 回答 6

8

对于任意数量的跳跃，可以轻松计算出千斤顶可以行进的最大正距离。翻转正跳的极性总计任何特定值k将导致千斤顶最终比其他情况低 2k 计数。对于任何最大距离t和任何小于或等于该距离的相同奇偶校验的非负n（即使t为偶数；如果t为奇数则为奇数）小于或等于该距离，将有可能找到总和为n的跳跃组合. 因此，人们不必担心树木、背包或任何其他类似的东西——只要一定数量的跳跃就足够了，以及它是否会产生正确的“奇偶性”。

于 2013-03-14T18:12:08.660 回答
8

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

算法

找到最小整数 k 使得 t_k := 1 + 2 + 3 + ... + k >= |n| 并且 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}^ki - 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 都成立，并且假设 A_k 中有一个数 d。反复减去：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 时停止。然后通过归纳假设，对于 {0, 1} 中的一些 b_i，r_j = sum_{i=0}^j b_i i。然后 d = r_j + sum_{i=j+1}^k a_k i，根据需要。相反，对于 a_i 在 {0,1} 中的和 s := sum_{i=1}^k a_i i 满足 0 <= s <= sum_{i}^ki = t_k，因此 s 在 A_k 中。

算法时间复杂度

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

于 2013-03-27T00:04:45.037 回答
2

n个连续整数之和的公式是n(n+1)/2。例如1+2+3+4=10= 4*5/2=10。这是达到目标数量所需的最少步数。但可能有过冲。说目标是11。四跳会让你到达10（我们刚刚计算过），但5会让你到达5*6/2=15。现在我们只注意到在 11 的情况下，当步长为 时我们跳回2，并且我们正确到达11。稍后我们将更详细地处理超调。回到最开始如何计算跳跃次数。我们的公式是目标数字n(n+1)/2 = x在哪里。二次方程x告诉我们这个问题的解是

(-1+/-sqrt(-1+8x)))/2

或者

(-1-/+(sqrt(9x))/2

负的“版本”总是会产生一个虚数，这在这里无关紧要，所以我们有

(sqrt(9x) + 1)/2

取该数字的上限，您就有了必要的初始跳跃次数。

过冲有点复杂。在我们到达的11例子中，超调是4( 15-11=4)，所以我们只需要将+2跳跃变成-2跳跃，这就是“存放”4 个超调的地方。然而，事情并不总是那么简单：12可以通过-1-2+3+4-5+6+7: 它需要一些7步骤，而不是5像预期的那样。基本观察是超调必须是偶数，否则没有超调/2 步可采取。这是我们如何找到步骤数的方法12

  1. 使用上述算法，我们发现最小步数是5，这让我们15
  2. 计算超调：我们有3.
  3. 如果超调是奇数（在这种情况下是这样），请尝试下一个步骤并返回第 2 步，直到找到偶数超调。这是您的步数

因此，对于 12，我们尝试5步骤、屈服15和超调3。然后我们尝试六步屈服21和9. 最后，我们尝试7让步28和超调16. 这是我们的最小步数。但是，这可能可以通过公式计算。

于 2013-03-14T19:03:57.023 回答
1

您可以将 Jack 的进度建模为二叉树，其中左节点表示向后跳转，右节点表示向前跳转。

每个节点的值就是杰克的当前位置。

节点的深度对应于当前的跳跃长度。

编辑- 您不能修剪与树中较高节点具有相同值的节点，因为它的子节点的值会不同，因为它处于不同的深度。

为了防止搜索空间增长过快，您需要积极修剪其值与前一个节点重复的任何节点。

此外，可以修剪根下方的整个左子树，因为所有值都是右子树中相应值的否定。例如：

右子树：0 + 1 + 2 + 3 - 4 = 2

左子树中的镜像：0 - 1 - 2 - 3 + 4 = -2

幸运的是，这棵树似乎生成了很多重复项。例如，在 depth = 7 时，而不是 32 个节点（64/2，因为我们只处理右子树），似乎只有 6 个不同的节点：

4 = 0 + 1 + 2 + 3 + 4 - 5 + 6 - 7
14 = 0 + 1 + 2 + 3 + 4 + 5 + 6 - 7
16 = 0 + 1 + 2 + 3 + 4 + 5 - 6 + 7 
18 = 0 + 1 + 2 + 3 + 4 - 5 + 6 + 7
20 = 0 + 1 + 2 + 3 - 4 + 5 + 6 + 7
28 = 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7

32 种可能的组合中的所有其余部分似乎要么是已经在树上更高的正数，要么是来自镜像左子树的负数。

所以我会进行广度优先搜索，直到找到我要找的号码。

于 2013-03-14T17:53:47.710 回答
0

问题如下：

k找到满足 $k(k+1)/2 = a + b$的第一个正自然数之和的最小值k，其中 $n = a - b$。

我们有一个方程组：

  • k(k+1)/2 = a + b
  • n = a - b
  • a, b, k是正整数

有三个未知数，只有两个方程。我们可以结合得到一个目标方程来满足：

  • k(k+1) + 2n = 4a

我们需要找到最小的正数k，使得这个解决方案可以满足给定的整数n，假设它a必须是某个正整数。让我们注意一些事情：

  1. 如果n是偶数，则要么 要么k必须k+1能被 4 整除；即，k = 0 or 3 mod 4。
  2. 如果n是奇数，则既不能被 4 整除，也不能被 4 整除k；k+1即，k = 1 or 2 mod 4。

这处理了关于所有数字都是整数的部分。为了处理关于k和a积极的部分，我们需要规定

  • k >= floor(sqrt(2n))

呸。现在，举个例子：

假设 n = 7。那么我们既不知道也k不可k+1被 4 整除。类似地，我们知道k >= 4。我们可以立即跳过k = 4，因为我们知道k不能被 4 整除。我们可以尝试k = 5；我们进入我们的系统：

n = 7
k = 5
a = 11
b = 4

这些数字都有效，所以我们有一个有效的解决方案。我们以这样一种方式选择解决方案，即我们必须首先找到最小的解决方案k。如果你愿意，你甚至可以重建 Jack 使用的跳跃顺序。在这种情况下，这很简单：杰克向右跳 11 次，向左跳 4 次。向左跳 4 的唯一方法是向左跳 1 和向左跳 3。所以杰克跳如下：

----------J------N---
---------J-------N--- -1
-----------J-----N--- +2
--------J--------N--- -3
------------J----N--- +4
-----------------J--- +5

但是，对于您的问题，一旦找到k可行的方法，您就完成了。k在找到一个有效的值之前，您不需要尝试许多值。

于 2013-03-14T19:57:19.287 回答
0

我们正在寻找所需的 j 数量，以便从 1 到 j 的总和大于目标数并且具有相同的奇偶性。

这是 python 2.7 中的一个简单的工作代码：

def numberOfJumps(n):
    n = abs(n)
    j = 0
    while True:
        s = j*(j+1)/2
        if s >= n and not (s - n)%2:
            break
        j += 1
    return j

for i in range(10):
    print i, numberOfJumps(i)

问题可以简化为正数，只是因为 -n 和 n 需要相同数量的跳转。对于序列中的每个数字，我们只需要朝相反的方向跳跃即可。

然后，为了达到 n，我们必须确保只有正跳跃的总和达到 n 或更多。

我们还必须使和的奇偶性与目标数相同，因为在负方向上跳跃会在和上产生偶数差异，因此不会改变其奇偶性。

假设您跳 1+2+3+4+5 = 15，将序列中的任何数字组合反转都会产生一个奇数，因此差是偶数。

于 2013-03-24T00:39:40.730 回答