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

Листинг 1.7. 
Fib4.java
package
chapter1;
public class
Fib4 {
private static int
fib4(
int
n) {
int
last = 0, next = 1; // fib(0), fib(1)
for
(
int
i = 0; i < n; i++) {
int
oldLast = last;
last = next;
next = oldLast + next;
}
return
last;
}
public static void
main(String[] args) {
System.
out
.println(
fib4
(20));
System.
out
.println(
fib4
(40));
}
}

---

1.1. Ряд Фибоначчи
31
Суть.в.том,.что.переменной.
last
.присваивается.предыдущее.значение.
next
,.
а.
next
.—.предыдущее.значение.
last
.плюс.предыдущее.значение.
next
..Временная.
переменная.
oldLast
.облегчает.выполнение.этих.действий.
При.таком.подходе.тело.цикла.
for
.будет.выполняться.максимум.
n
.–.1.раз..Другими.
словами,.это.самая.эффективная.версия..Сравните.19.проходов.тела.цикла.
for
.
с.21.891.рекурсивным.вызовом.
fib2()
.для.20-го.числа.Фибоначчи..В.реальных.
приложениях.это.может.серьезно.изменить.ситуацию!
В.рекурсивных.решениях.мы.приступали.к.задаче.с.конца..В.этом.итеративном.
решении.начинаем.с.начала..Иногда.рекурсия.—.это.наиболее.интуитивно.по-
нятный.способ.решения.задачи..Например,.суть.методов.
fib1()
.и.
fib2()
.—.это,.
в.сущности,.просто.механический.перевод.исходной.формулы.Фибоначчи..Однако.
наивные.рекурсивные.решения.могут.значительно.ухудшить.производительность..
Помните,.что.любую.задачу,.которая.может.быть.решена.рекурсивно,.можно.
решить.и.итеративным.способом.