Что случилось с моей реализацией Фибоначчи?

Question

Я пытаюсь преобразовать свою рекурсивную функцию Фибоначчи в итерационное решение. Я попытался следующие:

fib_itt :: Int -> Int 
fib_itt x = fib_itt' x 0 
where 
    fib_itt' 0 y = 0 
    fib_itt' 1 y = y + 1 
    fib_itt' x y = fib_itt' (x-1) (y + ((x - 1) + (x - 2))) 

Я хочу, чтобы сохранить результат в переменную y и вернуть его, когда xy матчи с 1y, но он не работает, как ожидалось. Для fib_itt 0 и fib_itt 1 он работает правильно, но для n > 1 он не работает. Например, fib_rek 2 возвращает 1 и fib_rek 3 возвращает 2.

Answer 1

Ваш алгоритм неверен: в y + (x-1) + (x-2) вы добавляете только последовательные числа, а не цифры в fib.series.

Похоже, вы пробовали какой-то парного подход (я думаю) - и да, это хорошая идея, и может быть сделано так:

fib :: Int -> Int 
fib k = snd $ fibIt k (0, 1) 

fibIt :: Int -> (Int, Int) -> (Int, Int) 
fibIt 0 x = x 
fibIt k (n,n') = fibIt (k-1) (n',n+n') 

как вы можете видеть: это проходит две необходимые части (последнее и второе-последнее число) вокруг в виде пары чисел и отслеживают итерацию с помощью k.

Тогда он просто возвращает вторую часть этого кортежа в fib (если вы используете первый вы получите 0,1,1,2,3,..., но, конечно, вы можете настроить начальный кортеж, а если вам нравится (fib k = fst $ fibIt k (1, 1)).

---

кстати эта идея непосредственно Leeds в этом славном определение fib.sequence если вы ФАКТОР итерации к iterate;)

fibs :: [Int] 
fibs = map fst $ iterate next (1,1) 
     where 
     next (n,n') = (n',n+n') 

fib :: Int -> Int 
fib k = fibs !! k