5

这是我昨天遇到的一个面试问题，我可以想到一个递归的解决方案，但我想知道是否有一个非递归的解决方案。

给定一个数字 N，从数字 1 开始，您只能将结果乘以 5 或将结果加 3。如果无法通过该方法获取N，则返回“Can't generate it”。

前任：

Input: 23
Output: (1+3)*5+3
Input: 215
Output: ((1*5+3)*5+3)*5
Input: 12
Output: Can't generate it.

递归的方法可以很明显也很直观，但是有没有非递归的方法呢？

4

6 回答 6

16

我认为最快的非递归解决方案是（对于 N > 2）：

  • 如果N mod 3 == 1，它可以生成为1 + 3*k。
  • 如果N mod 3 == 2，则可以生成为1*5 + 3*k
  • 如果N mod 3 == 0，则无法生成

最后一个陈述来自这样一个事实，即从 1 (= 1 mod 3) 开始，您只能达到等于 1 或 2 mod 3 的数字：

  • 当您添加 3 时，您不会更改值 mod 3
  • 一个等于 1 mod 3 的数字乘以 5 得到一个等于 2 mod 3 的数字
  • 一个等于 2 mod 3 的数字乘以 5 得到一个等于 1 mod 3 的数字
于 2013-07-15T11:00:17.523 回答
5

这里的关键是向后工作。从您想要达到的数字开始，如果它可以被 5 整除，则再除以 5，因为乘以 5 得到的解比乘以 3 的解更短。唯一的例外是值等于 10，因为除以 5 会产生 2是无解的。如果该数字不能被 5 整除或等于 10，则减去 3。这会产生最短的字符串

重复直到达到 1

这是python代码：

def f(x):
    if x%3 == 0 or x==2:
        return "Can't generate it"
    l = []
    while x!=1:
        if x%5 != 0 or x==10:
            l.append(3)
            x -= 3
        else:
                l.append(5)
                x /=5
    l.reverse()
    s = '1'
    for v in l:
        if v == 3:
            s += ' + 3'
        else:
            s = '(' + s + ')*5'
    return s

归功于先前用于确定给定数字是否可能的解决方案

于 2013-07-15T21:33:35.510 回答
2

将问题建模为图形：

  • 节点是数字
  • 你的根节点是 1
  • 节点之间的链接是*5或+3。

然后运行​​Dijkstra 算法得到最短路径。如果您从节点耗尽所有链接<N而没有到达，N那么您将无法生成N. （或者，使用@obourgain 的答案提前决定问题是否可以解决，只有在可以解决的情况下才尝试解决问题。）

因此，本质上，您将节点（1，空路径）排入队列。您需要一个字典来存储 {node(ie number) => 目前为该节点找到的最佳路径}。然后，只要队列不为空，在循环的每次传递中，您

  • 从队列中取出头（节点，路径）。
  • 如果这个节点的数量是>N，或者你之前已经在路径中看到过这个节点，并且路径中的步骤更少，那么在这个 pass 上不要再做任何事情了。
  • 将 (node => path) 添加到字典中。
  • *5使用和+3（以及将您带到这些节点的路径）从该节点可访问的节点入队

当循环终止时，N在字典中查找以获取路径，或输出“无法生成它”。

编辑：注意，这实际上是广度优先搜索而不是 Dijkstra 算法，因为遍历链接的成本固定为 1。

于 2013-07-15T12:11:33.307 回答
0

您可以使用以下递归（这确实很直观）：

f(input) = f(input/5) OR f(input -3)
base:
f(1) = true
f(x) = false    x is not natural positive number

请注意，它也可以使用动态编程来完成：

f[-2] = f[-1] = f[0] = false
f[1] = true
for i from 2 to n:
   f[i] = f[i-3] or (i%5 == 0? f[i/5] : false)

要获得分数，您需要在构建它之后上桌f[n]并遵循有效的true动作。

DP解的时间和空间复杂度是O(n)[伪多项式]

于 2013-07-15T11:00:44.157 回答
0

所有递归算法也可以使用堆栈来实现。所以，像这样：

bool canProduce(int target){
Stack<int> numStack;
int current;

numStack.push(1);

while(!numStack.empty){
  current=numStack.top();
  numStack.pop();
  if(current==target)
    return true;
  if(current+3 < target)
    numStack.push(current+3);
  if(current*5 < target)
    numStack.push(current*5);
}

return false;
}
于 2013-07-15T11:00:50.760 回答
0

在 Python 中：

智能解决方案：

def f(n):
    if n % 3 == 1:
        print '1' + '+3' * (n // 3)
    elif n % 3 == 2:
        print '1*5' + '+3' * ((n - 5) // 3)
    else:
        print "Can't generate it."

一个天真的但仍然 O(n) 的版本：

def f(n):
    d={1:'1'}
    for i in range(n):
        if i in d:
            d[i*5] = '(' + d[i] + ')*5'
            d[i+3] = d[i] + '+3'

    if n in d:
        print d[n]
    else:
        print "Can't generate it."

当然，您也可以使用堆栈来重现递归调用的行为。

这使：

>>> f(23)
(1)*5+3+3+3+3+3+3
>>> f(215)
(1)*5+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3
>>> f(12)
Can't generate it.
于 2013-07-15T11:23:57.813 回答