Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

out
.println(
fib2
(10));
}
}
Не.пытайтесь.вызывать.метод.
fib2(40)
..Он.будет.выполняться.очень.долго!.По-
чему?.Потому.что.каждый.вызов.
fib2()
.приводит.к.двум.новым.вызовам.
fib2()
.—.
рекурсивным.вызовам.
fib2(n-1)
.и.
fib2(n-2)
.(рис..1.3)..Другими.словами,.дерево.
вызовов.растет.в.геометрической.прогрессии..Например,.вызов.
fib2(4)
.приводит.
к.такой.последовательности.вызовов:
fib2(4) -> fib2(3), fib2(2)
fib2(3) -> fib2(2), fib2(1)
fib2(2) -> fib2(1), fib2(0)
fib2(2) -> fib2(1), fib2(0)
fib2(1) -> 1
fib2(1) -> 1
fib2(1) -> 1
fib2(0) -> 0
fib2(0) -> 0
. .
Рис. 1.3.
Каждый вызов fib2(),
не являющийся базовым случаем,
приводит к еще двум вызовам fib2()

---

1.1. Ряд Фибоначчи
29
Если.посчитать.их.(и.проследить,.добавив.несколько.вызовов.
print
),.то.обнару-
жится,.что.для.вычисления.всего.лишь.четвертого.элемента.нужны.девять.вызовов.
fib2()
!.Дальше.—.хуже..Для.вычисления.пятого.элемента.требуется.15.вызовов,.
десятого.—.177,.двадцатого.—.21.891..Мы.могли.бы.написать.и.что-нибудь.получше.
1.1.3. Спасение — в мемоизации
Мемоизация
.—.это.метод,.при.котором.сохраняются.результаты.выполненных.
вычислений,.так.что.когда.они.снова.понадобятся,.их.можно.найти,.вместо.того.
чтобы.вычислять.во.второй.(или.миллионный).раз.(рис..1.4)
1
.
Рис. 1.4.
Механизм мемоизации для людей
Создадим.новую.версию.метода.Фибоначчи,.которая.использует.словарь.Java.
для.целей.мемоизации.(листинг.1.5).
Листинг 1.5. 
Fib3.java
package
chapter1;
import
java.util.HashMap;