Задача № 46. Вывести на экран n-ное число Фибоначчи

Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран n -ное число Фибоначчи.

Примечание: последовательность чисел Фибоначчи задается следующей рекуррентной формулой:

То есть, нулевой член последовательности – это число 0, 1-й член – число 1, а любой другой член, начиная со 2-го, является суммой двух предыдущих. Например, F ₂ = F ₁ + F ₀ = 1 + 0 = 1, F ₃ = F ₂ + F ₁ = 1 + 1 = 2 и т. д.

Решение. Найдем несколько первых чисел Фибоначчи:

F ₂ = F ₁ + F ₀ = 1 + 0 = 1;

F ₃ = F ₂ + F ₁ = 1 + 1 = 2;

F ₄ = F ₃ + F ₂ = 2 + 1 = 3;

F ₅ = F ₄ + F ₃ = 3 + 2 = 5;

Легко заметить, что при их последовательном вычислении нам не нужно «расписывать» слагаемые по определению, и чтобы получить очередной член последовательности, достаточно на каждом шаге складывать два предыдущих полученных результата.

Так как нулевой и первый члены последовательности не вычисляются и даются как часть определения, будем полагать их заранее известными. Обозначим их идентификаторами fib0 и fib1. По примеру нахождения первых членов последовательности посчитаем количество операций, необходимое для вычисления каждого члена (считая, что предыдущие члены неизвестны). Легко увидеть, что для вычисления 2-го члена (при известном 1-ом и нулевом членах) необходима одна операция сложения, 3-го – две операции сложения и т. д. Видно, что по этим же правилам для вычисления n -ного члена необходимо выполнить (n – 1) операций.

Теперь можно начать писать программу. Сначала нам необходимо ввести значение n и выполнить инициализацию значений нулевого и первого чисел Фибоначчи, так как мы считаем их заранее известными:

readln(n);

fib0:= 0;

fib1:= 1;

Далее нам необходимо организовать цикл, в котором на каждом шаге переменные fib0 и fib1 будут получать следующие значения в последовательности чисел Фибоначчи. То есть, например, если в fib0 и fib1 будут находиться значения, соответственно, (n – 2) -го и (n – 1) -го членов последовательности Фибоначчи, то после одного шага цикла они будут содержать значения (n – 1) -го и n -го членов. Для этого можно создать некую вспомогательную переменную fib, в которую поместить результат сложения fib0 и fib1, после чего в fib0 у нас будет значение (n – 2) -го члена, в fib1 – (n – 1) -го, а в fib – n -го. Теперь нужно только скопировать значение fib1 в fib0 и fib в fib1, после чего значение переменной fib на этом шаге уже не имеет значения. С учетом того, что мы уже посчитали необходимое количество повторений для получения необходимого результата, цикл будет выглядеть так:

for i:= 1 to n - 1 do begin

fib:= fib1 + fib0;

fib0:= fib1;

fib1:= fib

end;

Такой метод решения общей задачи, основанный на использовании в ней решений задач с меньшей размерностью исходных данных (в данном случае под размерностью понимается величина n), называется динамическим программированием.

Если говорить конкретнее, то мы применили метод восходящего динамического программирования, основывающийся на решении задач сначала минимальной размерности с постепенным получением решений более обширных задач. Этот метод наиболее оптимален в плане реализации, быстродействия и используемой памяти.

Однако далеко не для всех задач, решаемых с помощью динамического программирования, можно выяснить, решения каких подзадач потребуются для решения данной. Для этого существует метод нисходящего динамического программирования, с которым мы познакомимся позже.

Другой пример нисходящего динамического программирования – вычисление факториала (задача 28). Чтобы вычислить n!, необходим вычисленный (n – 1)! и т. д.

Итак, вернемся к текущей задаче. Ранее было сказано, что по исчерпании n – 1 шагов цикла в переменной fib1, которая пойдет на вывод в программе, будет храниться значение F_n. Проверим корректность обработки граничных значений (в частности, когда n = 0, 1, 2):

1) При n = 0 границы цикла будут в отрезке [1, 0 – 1]. При этом значение правой границы зависит от типа переменной i, так как компилятор, дабы избежать ошибок, при вычислении «расширяет» тип выражений, означающих границы цикла.

Если i будет объявлено типа byte, то выражение 0 – 1 даст в результате 255 (так как все числовые типы в языке Pascal большинство компиляторов считает кольцевыми), что вызовет длинную цепочку вычислений, а это неверно. Конечно, можно объявить i типа integer, и тогда границы цикла будут в отрезке [1, –1] и вход не будет осуществлен, но мы поступим иначе, стараясь сохранить память для переменных.

Так как при вычислении важно лишь количество повторений, мы можем сдвинуть отрезок [1, n – 1] на одну позицию правее на числовой прямой, и тогда цикл будет проходить от 2 до n, что поможет отсеять вход в цикл при вводе 0 в качестве n, так как невозможен цикл по всем i от 2 до 0.

Однако тогда мы столкнемся с другой проблемой: при вводе 0 будет выведено значение fib1, которой было присвоено число 1 при инициализации. Справиться с проблемой можно, присвоив fib1 значение 0, если n = 0:

if n = 0 then fib1:= 0;

2) При n = 1 (с учетом принятых в предыдущем пункте изменений) входа в цикл не будет, и на экран выведется неизменное значение fib1, равное 1;

3) При n = 2 произойдет вход в цикл, где i будет изменяться от 2 до 2 (то есть, в этом случае будет выполнен единственный шаг), в котором будет вычислено значение fib = fib1 + fib0 = 1 + 0 = 1, которое будет скопировано в fib1 и выведено на экран. Нетрудно понять, что дальнейшая подстановка значений не требуется, так как корректность циклической конструкции мы уже доказали.

Верхние значения мы не проверяем, так как не существует наибольшего номера в последовательности чисел Фибоначчи (хотя понятно, что корректность вычислений ограничена «вместимостью» типа integer, и при его превышении в вычислениях числа уже будут неправильными).

Код: