мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версияСледующая версия справа и слева
haskell:fibb [19/02/2014 18:57] – vlasovhaskell:fibb [15/10/2014 18:47] – 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
Строка 18: Строка 19:
  
 Согласно сайту [[http://www.cubbi.org/serious/fibonacci/haskell.html|cubbi.com: fibonacci numbers in haskell]] Согласно сайту [[http://www.cubbi.org/serious/fibonacci/haskell.html|cubbi.com: fibonacci numbers in haskell]]
-возможно существенно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов:+возможно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов:
  
 <code haskell> <code haskell>
Строка 25: Строка 26:
 -- Naive binary recursion: F(n) = F(n-1) + F(n-2) with  -- Naive binary recursion: F(n) = F(n-1) + F(n-2) with 
 -- using memotrie from http://haskell.org/haskellwiki/MemoTrie -- using memotrie from http://haskell.org/haskellwiki/MemoTrie
-fib :: Int -> Integer+fib :: Integer -> Integer
 fib 0 = 0 fib 0 = 0
 fib 1 = 1 fib 1 = 1
 fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib
 +</code>
 +
 +Эксперименты показывают, что вычисления с мемоизацией не ускоряют бинарную рекурсию, лавиноообразное число вызовов с ростом n становится слишком велико.
 +
 +Рассмотрим императивное решение с циклом на Паскале:
 +
 +<code pascal>
 +program fibb;
 +var
 +  f1,f2,f3: Int64;
 +  n,i: integer;
 +begin
 +f1:=1; f2:=1;
 +write ('please, input n=');
 +read(n);
 +for i:=1 to (n-2) do 
 +begin
 + f3 := f2 + f1;
 + f1 := f2;
 + f2 := f3
 +end;
 +writeln ('f=', f3);
 +end.
 </code> </code>