мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версияПоследняя версияСледующая версия справа и слева | ||
haskell:fibb [19/02/2014 18:39] – vlasov | haskell:fibb [15/10/2014 18:54] – vlasov | ||
---|---|---|---|
Строка 5: | Строка 5: | ||
<code haskell> | <code haskell> | ||
fib :: Int -> Int | fib :: Int -> Int | ||
+ | -- fib :: Integer -> Integer избыточно, | ||
fib 1 = 1 | fib 1 = 1 | ||
fib 2 = 1 | fib 2 = 1 | ||
Строка 16: | Строка 17: | ||
Однако данный способ вычисления является хоть и простым, | Однако данный способ вычисления является хоть и простым, | ||
+ | |||
+ | Согласно сайту [[http:// | ||
+ | возможно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов: | ||
+ | |||
+ | <code haskell> | ||
+ | import Data.MemoTrie | ||
+ | |||
+ | -- Naive binary recursion: F(n) = F(n-1) + F(n-2) with | ||
+ | -- using memotrie from http:// | ||
+ | fib :: Integer -> Integer | ||
+ | fib 0 = 0 | ||
+ | fib 1 = 1 | ||
+ | fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib | ||
+ | </ | ||
+ | |||
+ | Эксперименты показывают, | ||
+ | |||
+ | Рассмотрим императивное решение с циклом на Паскале: | ||
+ | |||
+ | <code pascal> | ||
+ | program fibb; | ||
+ | var | ||
+ | f1,f2,f3: Int64; | ||
+ | n,i: integer; | ||
+ | begin | ||
+ | f1:=1; f2:=1; | ||
+ | write (' | ||
+ | read(n); | ||
+ | for i:=1 to (n-2) do | ||
+ | begin | ||
+ | f3 := f2 + f1; | ||
+ | f1 := f2; | ||
+ | f2 := f3 | ||
+ | end; | ||
+ | writeln (' | ||
+ | end. | ||
+ | </ | ||
+ | |||
+ | Сделаем аналог его, но уже с рекурсией вместо цикла. Рекурсия получится линейной, | ||
+ | |||
+ | <code haskell> | ||
+ | f a b 0 = b | ||
+ | f a b n = f b (a+b) (n-1) | ||
+ | fib n = f 1 1 n | ||
+ | </ | ||
+ | |||
+ | запуск осуществляется так: | ||
+ | <code haskell> | ||
+ | fib n | ||
+ | </ | ||
+ | |||
+ | Этот вариант уже не имеет проблемных мест и позволяет вычислять даже 100000-й элемент последовательности за 0.5-1.5 минуты на ноутбуке. | ||
+ | |||
+ | Другой вариант из сайта [[http:// | ||
+ | |||
+ | <code haskell> | ||
+ | {-# LANGUAGE BangPatterns #-} | ||
+ | fib n = go n (0,1) | ||
+ | where | ||
+ | go !n (!a, !b) | n==0 = a | ||
+ | | otherwise = go (n-1) (b, a+b) | ||
+ | </ | ||
+ | |||
+ | Вот // | ||
+ | |||
+ | <code haskell> | ||
+ | import Control.Monad.State | ||
+ | fib n = flip evalState (0,1) $ do | ||
+ | forM [0..(n-1)] $ \_ -> do | ||
+ | (a,b) <- get | ||
+ | put (b,a+b) | ||
+ | (a,b) <- get | ||
+ | return a | ||
+ | </ | ||
+ | |||
+ | А статья [[http:// | ||
+ | |||
+ | <code haskell> | ||
+ | fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ] | ||
+ | </ | ||
+ |