мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версия | Следующая версияСледующая версия справа и слева | ||
haskell:fibb [19/02/2014 18:40] – vlasov | haskell:fibb [19/02/2014 18:50] – vlasov | ||
---|---|---|---|
Строка 17: | Строка 17: | ||
Однако данный способ вычисления является хоть и простым, | Однако данный способ вычисления является хоть и простым, | ||
- | Согласно сайту [[http:// | + | Согласно сайту [[http:// |
+ | возможно существенно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов: | ||
+ | |||
+ | <code haskell> | ||
+ | import Data.MemoTrie | ||
+ | |||
+ | -- Naive binary recursion: F(n) = F(n-1) + F(n-2) with | ||
+ | -- using memotrie from http:// | ||
+ | fib :: Int -> Integer | ||
+ | fib 0 = 0 | ||
+ | fib 1 = 1 | ||
+ | fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib | ||
+ | </ | ||
+ | |||
+ | Более интересно превращение в линейную рекурсию с аккумулятором: | ||
+ | |||
+ | <code haskell> | ||
+ | fib a b 0 = a | ||
+ | fib a b (c+1) = fib (a+b) a c | ||
+ | </ | ||
+ | |||
+ | запуск осуществляется так: | ||
+ | <code haskell> | ||
+ | fib 0 1 n | ||
+ | </ |