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

Question

我目前正在JavaScript中开发一个函数，该函数接受一个数字数组，例如：[5, 10, 18, 25, 30]，然后返回一个数组，该数组包含从0到目标数字所需的最小运算数，只需将1相加或乘以2。

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

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

我已经研究了这个问题的潜在解决方案，其中一些使用了迭代，另一些使用了递归。我在这里找到了一个类似问题的答案代码审查-通过加5或乘以3来查找序列。

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

最终，我确实需要它来返回一个数组，因为输入也将是一个数组。然而，我甚至很难通过将单个整数作为参数来实现对上述答案的调整。

当我将5传递到此函数时，返回的是5，而不是最短的解4，因为它只包含adds 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

Answer 2

反过来做可能更容易。从你的目标开始，用减去1或除以2，直到你达到零。一旦你找到了这个序列，就反转它，并使用反向操作(加1，乘以2)回到你的目标。

function getNext(num) {
if (num === 0) return "end"
if (num % 2 === 1) return "minus"
return "div"
}
function makeSequence(num, ls) {
const next = getNext(num);
if (next === "end") return ls;
ls.push(next)

if (next === "div") return makeSequence(num/2, ls);
if (next === "minus") return makeSequence(num-1, ls);
}
function reverseSequence(sqn) {
return sqn.reverse().map(x => x === "minus" ? "plus" : "times");
}
var sqn = makeSequence(5, []);
var reversedSqn = reverseSequence(sqn)
console.log("Takes", reversedSqn.length, "steps with target of 5");
console.log("Steps are:", reversedSqn);     
var bigSqn = makeSequence(200, []);
var bigReversedSqn = reverseSequence(bigSqn);
console.log("Takes", bigReversedSqn.length, "steps with target of 200");
console.log("Steps are:", bigReversedSqn);