如何解決我在Scala中部分總和的實現？

這是我的previous question的後續行動。我想實現我自己（只是作爲一個練習）如何解決我在Scala中部分總和的實現？

也就是說，我還想寫功能partial_sums，接收流s = s1, s2, s3, ...，併產生一個新的流s1, s1 + s2, s1 + s2 + s3, ...

我實現它如下s.scanLeft(0)(_ + _)：

def add_streams(s1:Stream[Int], s2:Stream[Int]) = 
    (s1 zip s2) map {case (x, y) => x + y} 

def partial_sums(s:Stream[Int]):Stream[Int] = 
    Stream.cons(s.head, add_streams(partial_sums(s), s.tail))

此代碼工作正常。但是看起來好像需要O（n）來得到partial_sums的第n個元素。（即s [1] + s [2] + s [3] ... + s [n]）。我想代碼partial_sums[n] = partial_sums[n-1] + s[n]，這需要O（1）來計算第n個元素。

它是正確的嗎？你將如何修復代碼？

來源

2011-12-28 Michael

的基本思想是保持運行總和，而不是批量添加流

def partialSums(s:Stream[Int]) = if(s.isEmpty) new Stream[Int]() else partialSums(s, 0) 

def partialSums(s:Stream[Int], runningTotal:Int)= Stream.cons(s.head+runningTotal, partialSums(s.tail, s.head+runningTotal)

來源

2011-12-28 14:58:14

你的意思是'S：信息流[INT]'I/O'S：String'？ – Michael 2011-12-28 15:42:20

它是否適用於空流？ – Michael 2011-12-28 15:43:22

修正了這個問題。謝謝。 – 2011-12-28 16:32:34

如何解決我在Scala中部分總和的實現？

回答

相關問題