Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

Задача № 46. Вывести на экран n-ное число Фибоначчи 
Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран 
n-
ное число Фибоначчи. 
Примечание: последовательность чисел Фибоначчи задается следующей рекуррентной фор-
мулой: 
1
2
0,
если 
0
1,
если 
1
,
если 
2
n
n
n
n
F
n
F
F
n
−
−
=


=
=


+
≥

То есть, нулевой член последовательности – это число 0, 1-й член – число 1, а любой другой 
член, начиная со 2-го, является суммой двух предыдущих. Например, F
2
= F
1
+ F
0
= 1 + 0 = 1, F
3
= 
F
2
+ F
1
= 1 + 1 = 2 
и т. д. 
Решение. Найдем несколько первых чисел Фибоначчи: 
F
2
= F
1
+ F
0
= 1 + 0 = 1; 
F
3
= F
2
+ F
1
= 1 + 1 = 2; 
F
4
= F
3
+ F
2
= 2 + 1 = 3; 
F
5
= F
4
+ F
3
= 3 + 2 = 5; 
Легко заметить, что при их последовательном вычислении нам не нужно «расписывать» сла-
гаемые по определению, и чтобы получить очередной член последовательности, достаточно на каж-
дом шаге складывать два предыдущих полученных результата. 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
60 
Так как нулевой и первый члены последовательности не вычисляются и даются как часть опре-
деления, будем полагать их заранее известными. Обозначим их идентификаторами 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)-го и