Блог

Итак, я работаю над заданием, в котором мне нужно найти n-е число Фибоначчи, и я наткнулся на эту идею, показанную ниже, однако это возвращает список, и я просто хотел бы вернуть окончательное число, поэтому, например, фибо 3 даст мне [0,1,1,2,3,5,8,13], за исключением того, что я просто хочу, чтобы 13 вернулось, есть ли способ, которым я мог бы это сделать? Это мой первый раз, когда я использую Haskell, и я вроде как изучаю функциональное программирование, а также в первый раз, любая помощь приветствуется. Спасибо

 fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n
fiboHelper :: Integral x => [x]->x->x->x->[x]
fiboHelper l x y 0 = l
fiboHelper l x y n = fiboHelper (l    [y x]    [y x y]) (x y) (y x y) (n-1)
 

Да, вы можете отслеживать последние 2 шага по мере продвижения вниз по рекурсивному стеку.

 fibo :: Integral x => x -> x
fibo a
  | a < 3      = 1
  | otherwise  = go 2 1 1 where
    go a' b' c'
       | a' == a    = c'
       | otherwise  = go (a' 1) (c') (b' c')
 

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

 fibs = 1 : scanl ( ) 1 fibs
 

сочетая это с take и last вы можете достичь любого решения, которое вы ищете.

 take 5 fibs
-- produces [1,1,2,3,5]

last $ take 5 fibs
-- produces 5
 

Вы можете работать со вспомогательной функцией, которая содержит две переменные: первый и второй элемент, и каждая

 fibo :: (Integral a, Integral b) => a -> b
fibo 0 = 0
fibo n = fiboHelper 0 1 (n-1)

fiboHelper :: (Integral a, Integral b) => a -> a -> b -> a
fiboHelper si si1 n
    | n <= 0 = si1
    | otherwise = fiboHelper si1 (si si1) (n-1)
 

Это затем приводит к:

 Prelude> fibo 7
13
 

Что касается алгоритма в вашем вопросе, обычно добавление в правой части списка не является хорошей идеей, поскольку оно выполняется в линейном времени с размером левого операнда. Таким образом, это означает, что ваш алгоритм выполняется за O(n ²) времени. Вы можете реализовать это следующим образом:

 fibo :: (Integral a, Integral b) => a -> [b]
fibo 0 = [0]
fibo n = 0 : fiboHelper 0 1 (n-1)

fiboHelper :: (Integral a, Integral b) => a -> a -> b -> [a]
fiboHelper si si1 n
  | n < 0 = []
  | otherwise = si1 : fiboHelper si1 (si si1) (n-1)
 

это приведет к:

 Prelude> fibo 7
[0,1,1,2,3,5,8,13]
 

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

 -- replace a and b with (a b) and a, respectively, forgetting b.
helper a b n == fiboHelper (a b) a (n-1)
helper a b 1 == a
helper _ b 0 == b
 

(Второй случай не является строго необходимым, но позволяет избежать ненужного добавления.)

По мере n уменьшения желаемое значение «накапливается» во втором параметре, причем значение при n == 0 этом является конечным результатом.

Обратите внимание, что вы можете получить разные ряды, указав разные начальные значения для a и b . Например fibo = helper 1 0 , в то время как числа Лукаса определяются lucas = helper 1 2 :

 lucas 5 = helper 1 2 5
        == helper 3 1 4
        == helper 4 3 3
        == helper 7 4 2
        == helper 11 7 1
(       == helper 18 11 0)
        == 11