Databases
StackOverflow2013
Postsdbo
POapply window function to get a recursive list, how can I do?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POapply window function to get a recursive list, how can I do?
    text
    copied!<p>I just come across a challenging problem (from programming competition practice) that contain <strong>recursive sequence</strong> as following</p> <p>given 3 numbers <strong>m n k</strong> find element a[k] where</p> <pre><code>a[0] = m a[1] = n a[i] = a[i-1] + a[i-2] ; if floor(i/2) mod 2 = 1 a[i] = a[i-1] - a[i-4] ; if floor(i/2) mod 2 = 0 </code></pre> <p>example case: for m=2 n=3 k=6 answer would be 9</p> <pre><code>a[0] = 2 a[1] = 3 a[2] = 3 + 2 = 5 a[3] = 5 + 3 = 8 a[4] = 8 - 2 = 6 a[5] = 6 - 3 = 3 a[6] = 3 + 6 = 9 ... </code></pre> <p>this is how I generate the sequence (which obviously consume lots of stack and super slow even for the first 100 element)</p> <pre><code> 1 fbm :: Int → Int → Int → Int 2 fbm m n 0 = m 3 fbm m n 1 = n 4 fbm m n x = let a = fbm m n (x-1) 5 b = fbm m n (x-2) 6 c = fbm m n (x-4) 7 in case (x `div` 2) `mod` 2 of 8 1 → a + b 9 0 → a - c 10 11 fbs m n = map (λx→fbm m n x) [0..] </code></pre> <p>Since the problem required to find element at big (~1000+) index. I try to do a different approach by trying to limit computation only on <strong>function with 4 inputs</strong> and apply the function with <strong>4 element window</strong> recursively on the list but can't success implementing any of them (<em>something</em> mean I can't figured out how to do it)</p> <pre><code>fs1 = map fst $ iterate next (a,b) where next (a,b) = something fs2 = m:n:scanl (gen) 2 fs2 where gen [a,b,c,d] = something fs3 = scanl (genx m n 0 0) (repeat 0) where genx a b c d = something </code></pre> <p><strong>Question 1:</strong> Does any of my approach the good way to solve this problem? (+ please show me an example of how to do it)</p> <p><strong>Question 2:</strong> How would you solve this kind of problem if I am in the wrong way?</p>
 

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