0

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

给定问题:从 1 开始,编写一个给定数字的函数,该函数返回一个操作序列,该操作序列仅由其中一个"+5""*3"产生所讨论的数字组成。

我的基本算法:

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

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

4

3 回答 3

1

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

例如,13 不能被 3 整除,因此目标 13 的后向问题的第一步必须是“-5”,而不是“/3”。

它不会改变复杂性,但可以使算法在实践中更快地解决小问题。

于 2013-08-02T14:27:43.090 回答
0

你本质上想要做一个广度优先的二叉搜索树。你可以使用递归,或者只是一些while循环。每一步都取当前数字并加 5 或乘以 3。进行测试,如果找到输入值,则返回 0 或其他值(您没有指定)。

这里的关键是关于数据结构以及如何搜索它。你明白为什么它应该首先是广度吗?你明白为什么它是二叉树吗?

回应评论:首先我很佩服你的努力。独立于语言解决这类问题是解决问题的好方法。这与 Javascript(或任何其他语言)中的愚蠢技巧无关。

所以第一个概念是你“寻找”一个解决方案,如果你没有找到一个返回-1。

其次,您应该对二叉树进行一些研究。它们是一个非常重要的概念!

第三,您应该进行广度优先搜索。然而,这是最不重要的。它只是使问题更有效率。

于 2013-08-02T14:18:27.410 回答
0

what about the number 13 which can be found by a MIXTURE of BOTH paths?? I can only do one thing or the other!

好吧,实际上你可以两者都做。正如您提到的本书第 3 章中的示例一样,您会看到该函数find在其内部被调用了两次——该函数在任何选择点尝试两条路径并返回第一个正确的解决方案(您也可以尝试改变整体功能,使其返回所有正确的路径)。

How would I know which path to take and how many times I should take that path? How would I bounce back and forth between paths?

基本上,在路径之间来回弹跳是通过同时移动它们来实现的。如果函数达到目标数字,您就知道它是否是正确的路径。

于 2013-08-02T17:07:50.407 回答