使数学表达式与目标数字匹配的最短序列

Question

我正在通过雄辩的JavaScript，并且有一个程序检查乘以3和加5的任意组合是否产生目标值：

但是这个函数并没有给我最短的可能（序列）。

我想不出获得尽可能短的解决方案的逻辑。如何更改此代码以为我提供最短路径？

function find_solution(target) {

  function find(current, history) {

    if (target === current) {

      return history;

    } else if (target < current) {

      return null;

    } else {

      return find(current + 5, `(${history} + 5)`) || find(current * 3, `(${history} * 3)`);

    }

  }

  return find(1, '1');

}

console.log(find_solution(24));

Answer 1

好努力。你正在运行 DFS，但 DFS 并不总是为你提供最短路径。BFS是寻找最短路径的一个很好的天真的第一选择。可能需要优化。const shortestPathAddMul = (target, begin=1, add=5, mul=3) => {&nbsp; const visited = new Set();&nbsp;&nbsp;&nbsp; for (const q = [[begin, begin]]; q.length;) {&nbsp; &nbsp; const [seq, curr] = q.shift();&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if (visited.has(curr)) continue;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; visited.add(curr);&nbsp; &nbsp; if (curr === target) {&nbsp; &nbsp; &nbsp; return `${seq} = ${target}`;&nbsp; &nbsp; }&nbsp; &nbsp; else if (curr < target) {&nbsp; &nbsp; &nbsp; q.push(...[[`(${seq} + ${add})`, curr + add],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[`(${seq} * ${mul})`, curr * mul]]);&nbsp; &nbsp; }&nbsp; }};console.log(shortestPathAddMul(24));