HUX布斯
2022-08-18 10:56:09
我正在通過雄辯的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));
1 回答

牛魔王的故事
TA貢獻1830條經驗 獲得超3個贊
好努力。你正在運行 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));
添加回答
舉報
0/150
提交
取消