Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:There are typically two ways to work with Fibonacci numbers. You can either use the formula to generate the nth Fibonacci number, a formula that involves taking powers of the golden ratio $\phi$; or you can just simply start from the beginning and iterate through them.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
For this one, we'll iterate through and accumulate values as we go along. A simple approach here would be to generate the list of Fibonacci numbers that are less than 4 million, filter out the odd ones, then reduce the list. Something like this:
(<<- (gen-fibs-to 4000000) (filter even?) (reduce +))This has a time complexity of O(n), but it also has a space complexity of O(n). We can do better than that. Instead of first generating all the Fibonacci numbers, we can instead just stream through, accumulating values as we need to. A common pattern to do this is to define a local function that accepts an accumulator value, and add the even numbers to it. We quit when we've passed our limit.
(defn sum-even-fibs [n] (letfn [(accum [a b sum n] (if (>= b n) sum ; we've passed the limit, return the total (accum b (+ a b) (+ sum (if (even? b) b 0)) n)))] (accum 1 2 0 n))) (println (sum-even-fibs 4000000))Running this program gives us the correct answer very quickly (note that on my machine the JVM takes about 1.5s to start up):
$ time clj 2.clj 4613732 real 0m1.532s user 0m3.136s sys 0m0.096s
No comments:
Post a Comment