結構以允許@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當多個遞歸調用被調用

回答

相關問題