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

Различия

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

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

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
haskell:fibb [15/10/2014 18:47] – Владимир Власовhaskell:fibb [15/10/2014 18:59] (текущий) – Владимир Власов
Строка 32: Строка 32:
 </code> </code>
  
-Эксперименты показывают, что вычисления с мемоизацией не ускоряют бинарную рекурсию, лавиноообразное число вызовов с ростом n становится слишком велико.+(Эксперименты показывают, что вычисления с мемоизацией не ускоряют бинарную рекурсию, лавиноообразное число вызовов с ростом n становится слишком велико).
  
 Рассмотрим императивное решение с циклом на Паскале: Рассмотрим императивное решение с циклом на Паскале:
Строка 43: Строка 43:
 begin begin
 f1:=1; f2:=1; f1:=1; f2:=1;
-write ('please, input n='); +write ('please, input n='); read(n);
-read(n);+
 for i:=1 to (n-2) do  for i:=1 to (n-2) do 
 begin begin
- f3 := f2 + f1; + f3 := f2 + f1;  f1 := f2;  f2 := f3
- f1 := f2; +
- f2 := f3+
 end; end;
 writeln ('f=', f3); writeln ('f=', f3);
Строка 55: Строка 52:
 </code> </code>
  
-Более интересно превращение в линейную рекурсию с аккумулятором:+Эта программа позволяет быстро вычислять до 92-го члена последовательности (дальше возникают проблемы с превышением числового диапазона Int64). 
 + 
 +Сделаем аналог его, но уже с рекурсией вместо цикла. Рекурсия получится линейной, и добавится новый параметр "__//аккумулятор//__":
  
 <code haskell> <code haskell>
-fib a b 0     = a +f a b 0 = b 
-fib a b (c+1) = fib (a+b) a c+f a b n = f b (a+b) (n-1) 
 +fib n = f 1 1 n
 </code> </code>
  
 запуск осуществляется так: запуск осуществляется так:
 <code haskell> <code haskell>
-fib 0 1 n+fib n
 </code> </code>
 +
 +Этот вариант уже не имеет проблемных мест и позволяет вычислять даже 100000-й элемент последовательности за 0.5-1.5 минуты на ноутбуке.
  
 Другой вариант из сайта [[http://www.haskell.org/haskellwiki/The_Fibonacci_sequence|The Fibonacci sequence]] с аккумулятором и //хвостовой рекурсией// (используя расширения языка): Другой вариант из сайта [[http://www.haskell.org/haskellwiki/The_Fibonacci_sequence|The Fibonacci sequence]] с аккумулятором и //хвостовой рекурсией// (используя расширения языка):