Числа Фибоначчи — бескочечная числовая последовательность , в которой каждое число есть сумма двух предыдущих: Первые два элемента последовательности, нужные для затравки — ноль и единица: , . Вот числа Фибоначчи из первой сотни: .
Последовательности, где каждый элемент, за исключением первых штук, вычисляется через предшествующих ему элементов, называются рекуррентными порядка . В нашем случае мы имеем дело с рекуррентной последовательностью второго порядка. К тому же эта рекуррентность линейная, потому что её элемент выражается через два предыдущих линейным образом. Для любой линейной рекуррентной последовательности можно написать явную формулу для вычисления её -го элемента.
Требуется написать программу, вычисляющую и выводящую на экран число Фибоначчи с заданным номером в последовательности. Номер передаётся в программу через командную строку:
%
./fibonacci.pl 6
8
%
./fibonacci.pl 11
89