Внедрение фибоначчи в Clojure с использованием карты/уменьшение

Question

Возможно ли внедрение ряда фибоначчи в Clojure с использованием reduce? Что будет содержать «аккумулятор»?

Я полагаю, что это должно быть лениво. Очевидно, как это сделать, используя рекурсию или цикл/повтор.

Answer 1

Вы можете использовать пару последовательных значений Фибоначчи как аккумулятора, следующим образом:

(reduce 
    (fn [[a b] _] [b (+ a b)]) ; function to calculate the next pair of values 
    [0 1]      ; initial pair of fibonnaci numbers 
    (range 10))     ; a seq to specify how many iterations you want 

=> [55 89] 

Это не особенно эффективно в связи с созданием большого количества промежуточных пар и использование последовательности лишнего диапазона для привода правильное число итераций, но это O (n) с алгоритмической точки зрения (то же самое, что и эффективное итеративное решение, и намного лучше наивного рекурсивного).

Answer 2

Не использовать карту/уменьшить, но повторить также можно избежать рекурсии.

(defn iter [[x y]] 
    (vector y (+ x y))) 

(nth (iterate iter [0 1]) 10000) 

Это занимает 21ms на Intel 2.4 Ghz

На той же машине, уменьшить занимает 61msec. Не знаю, почему итерация происходит быстрее.

(time (reduce 
    (fn [[a b] _] [b (+ a b)]) ; function to calculate the next pair of values 
    [0 1]      ; initial pair of fibonnaci numbers 
    (range 10000))) 

Answer 3

Это даст вам вектор первые 1000 чисел Фибоначчи (размер range + 2), обработку второй аргумент функции (range) в качестве счетчика:

(reduce 
    (fn [a b] (conj a (+' (last a) (last (butlast a))))) 
    [0 1]      
    (range 998))