StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem is similar to "Fibonacci series", but in my opinion, there is a big difference between them.<br/> <strong>Memoization</strong> is a common technique to solve this kind of problems.<br/> For example, we can use it to compute Fibonacci series.<br/> The following is a very simple illustration. It is not as good as that <code>zipWith</code> solution, but it is still a linear operation implementation.</p> <pre><code>fib :: Int -> Integer fib 0 = 1 fib 1 = 1 fib n = fibs !! (n-1) + fibs !! (n-2) fibs :: [Integer] fibs = map fib [0..] </code></pre> <p>If we try to imitate the above <code>fib</code> and <code>fibs</code>, perhaps we would write the following code.</p> <pre><code>fbm :: Int -> Int -> Int -> Int fbm m n 0 = m fbm m n 1 = n fbm m n x = let a = fbs m n !! (x-1) b = fbs m n !! (x-2) c = fbs m n !! (x-4) in case (x `div` 2) `mod` 2 of 1 -> a + b 0 -> a - c fbs :: Int -> Int -> [Int] fbs m n = map (fbm m n) [0..] </code></pre> <p>But the above <code>fbs</code> is also super slow. Replacing list by array makes little difference. The reason is simple, there is no memoization when we call <code>fbs</code>. The answer will be more clear if we compare the type signatures of <code>fibs</code> and <code>fbs</code>.</p> <pre><code>fibs :: [Integer] fbs :: Int -> Int -> [Int] </code></pre> <p>One of them is a list of intergers, while the other is a function.<br/> To let memoization happen, we have to implement fbs in anothing way.<br/> e.g.</p> <pre><code>fbs m n = let xs = map fbm [0..] fbm 0 = m fbm 1 = n fbm x = let a = xs !! (x-1) b = xs !! (x-2) c = xs !! (x-4) in case (x `div` 2) `mod` 2 of 1 -> a + b 0 -> a - c in xs </code></pre> <p><strong>Tail recursion</strong> is anothing common approach for this kind of problems.</p> <pre><code>fbm :: Int -> Int -> Int -> (Int, Int, Int, Int) -- a[0] = m -- a[1] = n -- a[2] = m + n -- a[3] = m + 2 * n fbm m n 3 = (m+2*n, m+n, n, m) fbm m n x = case (x `div` 2) `mod` 2 of 1 -> (a+b, a, b, c) 0 -> (a-d, a, b, c) where (a,b,c,d) = fbm m n (x-1) </code></pre> <p>Last but not least, here is a mathematical solution.</p> <pre><code>a[0] = m a[1] = n a[2] = m + n a[3] = m + 2n a[4] = 2n a[5] = n a[6] = 3n a[7] = 4n a[8] = 2n fbs m n = [m, n, m+n, m+2*n] ++ cycle [2*n, n, 3*n, 4*n] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload