结构以允许@tailrec当多个递归调用被调用

下面的逻辑标识整数相加来Ñ产生最大产物的组合：结构以允许@tailrec当多个递归调用被调用

def bestProd(n: Int) = { 
    type AType = (Vector[Int], Long) 
    import annotation._ 
    // @tailrec (umm .. nope ..) 
    def bestProd0(n: Int, accum : AType): AType = { 
    if (n<=1) accum 
    else { 
     var cmax = accum 
     for (k <- 2 to n) { 
     val tmpacc = bestProd0(n-k, (accum._1 :+ k, accum._2 * k)) 
     if (tmpacc._2 > cmax._2) { 
      cmax = tmpacc 
     } 
     } 
     cmax 
    } 
    } 
    bestProd0(n, (Vector(), 1)) 
}

此代码工作：

scala> bestProd(11) 
res22: (Vector[Int], Long) = (Vector(2, 3, 3, 3),54)

现在，我不觉得@tailrec没有工作。在所有的递归调用后，在尾部位置是而不是。有可能重新编写for循环来改为执行适当的单次调用以实现尾递归？

来源

2015-07-12 javadba

评论，因为它没有回答你的问题。因为你需要检查加起来为n的所有序列，所以先产生它们，然后用最大乘积来映射那个序列，并且没有任何可变变量def defProt（m：Int）= def sumTo（n：Int）：Seq [Seq [Int]] = Seq（n）+ :(对于（i <-1直到n; ps < - sumTo（ni））产生i +：ps））; sumTo（m）.maxBy（_。product） } ' –

Thx Paul for the alternative impl。 – javadba

我不认为这是可能的，如果你试图坚持接近规定的算法。重新思考方法，你可以做这样的事情。

import scala.annotation.tailrec 
def bestProd1(n: Int) = { 
    @tailrec 
    def nums(acc: Vector[Int]): Vector[Int] = { 
    if (acc.head > 4) 
     nums((acc.head - 3) +: 3 +: acc.tail) 
    else 
     acc 
    } 
    val result = nums(Vector(n)) 
    (result, result.product) 
}

它配备了相同的结果（据我可以告诉），除了我不拆四成2,2。

来源

2015-07-12 06:09:25 jwvh

所以最高的产品总是（以正则表示法）[2 | 4]？[3] *？很明显，您的解决方案确实可行。请考虑upvote。 – javadba

结构以允许@tailrec当多个递归调用被调用

回答

相关问题