Задача № 46. Вывести на экран n-ное число Фибоначчи
Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран n-ное число Фибоначчи.
Примечание: последовательность чисел Фибоначчи задается следующей рекуррентной формулой:
То есть, нулевой член последовательности – это число 0, 1-й член – число 1, а любой другой член, начиная со 2-го, является суммой двух предыдущих. Например, F2 = F1 + F0 = 1 + 0 = 1, F3 = F2 + F1 = 1 + 1 = 2 и т. д.
Решение. Найдем несколько первых чисел Фибоначчи:
F2 = F1 + F0 = 1 + 0 = 1;
F3 = F2 + F1 = 1 + 1 = 2;
F4 = F3 + F2 = 2 + 1 = 3;
F5 = F4 + F3 = 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, которая пойдет на вывод в программе, будет храниться значение Fn. Проверим корректность обработки граничных значений (в частности, когда 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, и при его превышении в вычислениях числа уже будут неправильными).
Код :
Дата добавления: 2018-10-25; просмотров: 231; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!