javascript - 计算达到目标数量所需的最少操作

Question

我目前正在使用 JavaScript 编写一个函数，它接受一个数字数组，例如:[5, 10, 18, 25, 30] 然后返回一个包含计数的数组只需添加 1 或乘以 2 即可从 0 到目标数字所需的最少操作数。

例如，从数组中，数字 5 将返回 4，因为您将执行 0 + 1 = 1 x 2 = 2 x 2 = 4 + 1 = 5。

如果传入的数组是 [5,5,5]，则输出数组将为 [4,4,4]。

我查看过这个问题的潜在解决方案，其中一些使用迭代，另一些使用递归。我在这里找到了类似问题的答案 Code Review - Find sequence by adding 5 or multiplying by 3 .

唯一的区别是这是加 5 或乘以 2，它从 1 而不是 0 开始。我试图调整这个解决方案以满足我的需要，但是，出于某种原因，代码只会永远加 1，永远不要乘以 2。所以，对于输入 5 我返回 0 + 1 = 1 + 1 = 2 + 1 = 3 + 1 = 4 + 1 = 5 这显然不是最短的解决方案。

最终我确实需要它来返回一个数组，因为输入也将是一个数组，但是我正在努力使上述答案的改编工作起作用，只是将单个整数作为参数。

当我将 5 传递给此函数时，返回的是 5 而不是最短的解决方案 4，因为它只 加 1。

我现在的代码是:

function findSequence(goal) {
  function find(start, history) {
    if (start == goal) {
      return history;
    }
    if (start > goal) {
      return null;
    }
    return find(start + 1, "(" + history + " + 1)") ||
             find(start * 2, "(" + history + " * 2)");
  }
  return find(0, "0");
}

我怎样才能使这项工作？我需要通过仅加 1 或乘以 2

来返回从 0 到目标数的 最短序列计数

Answer 1

这样的事情怎么样:

function findMoves(target)
{
    arr = [];
    while (target != 1)
    {
        if (target %2 == 0)
        {
            target /= 2;
            arr.unshift(target + " x " + 2);
            continue;
        }
        target -= 1;
        arr.unshift(target + " + " + 1);
    }
    arr.unshift("0 + 1");
    return arr;
}

res = findMoves(9);

console.log(
    "TotalMoves: " + res.length + "\n" + 
    "What moves: " + res.join(', '));

打印:

TotalMoves: 5
What moves: 0 + 1, 1 x 2, 2 x 2, 4 x 2, 8 + 1