algorithm - 查找操作序列

Question

这最终应该用 JavaScript 编写。但是我觉得在我的算法清楚之前我不应该输入任何代码，但事实并非如此!

给定问题:从 1 开始，编写一个函数，给定一个数字，返回仅由 "+5" 或 "*3" 组成的操作序列产生有问题的数字。

我的基本算法:

1. 获取号码
2. 如果数字是1
   返回 1。
3. 否则如果我们超过这个数字
   返回-1。
4. 否则继续尝试 "+5" 或 "*3" 直到达到数字，假设可以达到。

我的问题是第 4 步:我看到有两条路径可以将我带到有问题的数字(目标)，"+5" 或 "*3"，但是可以通过两条路径的 MIXTURE 找到的数字 13 呢？我只能做一件事或另一件事! 我怎么知道要走哪条路以及我应该走那条路多少次？我将如何在路径之间来回反弹？

Answer 1

我同意二叉树中广度优先搜索的概念。但是，我建议扭转问题，看看使用“-5”或“/3”从目标返回到 1 的问题。这允许基于目标进行修剪。

比如13不能被3整除，那么目标13的逆向问题第一步必须是“-5”，而不是“/3”。

它不会改变复杂性，但可能会使算法在实践中对小问题更快。