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

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) => {

  const visited = new Set();

  

  for (const q = [[begin, begin]]; q.length;) {

    const [seq, curr] = q.shift();

    

    if (visited.has(curr)) continue;

    

    visited.add(curr);

    if (curr === target) {

      return `${seq} = ${target}`;

    }

    else if (curr < target) {

      q.push(...[[`(${seq} + ${add})`, curr + add],

                 [`(${seq} * ${mul})`, curr * mul]]);

    }

  }

};

console.log(shortestPathAddMul(24));