In today’s Programming Praxis exercise, our goal is to find a series of non-consecutive fibonacci numbers that sum up to a given number. Let’s get started, shall we?
First, we define the fibonacci sequence:
fibs :: [Integer] fibs = 1 : scanl (+) 1 fibs
The algorithm to find the numbers is pretty trivial as well: take the largest fibonacci number less than or equal to the target value and repeat on the remainder.
zeck :: Integer -> [Integer] zeck 0 = [] zeck n = f : zeck (n - f) where f = last $ takeWhile (<= n) fibs
Some tests to see if everything is working properly:
main :: IO () main = do print $ zeck 100 == [89,8,3] print $ zeck (3^15) == [9227465, 3524578, 1346269, 196418, 46368, 6765, 987, 55, 2] print $ zeck $ 10^100
Tags: bonsai, code, fibonacci, Haskell, kata, praxis, programming, zeckendorf
