6.2.5 Числа Фибоначчи

Задача. Последовательность чисел Фибоначчи $\Phi(1)$, $\Phi(2)$, $\ldots,$$\Phi(n)$, $\ldots,$ определяется по следующим правилам: $\Phi(1) = \Phi(2) = 1$ и $\Phi(n) = \Phi(n-1) + \Phi(n-2)$ для всех $n > 2$.

Вычислить $\Phi(n)$ для заданного $n$.

Решение. Определение чисел Фибоначчи допускает переписывание в виде функции на языке Zonnon, так что мы сразу получаем первое решение

module ФИБ1;
    var N: integer;
procedure ФИБ(N:integer):integer;
    begin if (N=1) or (N=2) then return 1(* =$\Phi$(N) *)
              else return ФИБ(N-1) + ФИБ(N-2) (*=$\Phi$(N)*)
    end ФИБ;
begin read(N); writeln('$\Phi$(',N,')=', ФИБ(N)) end ФИБ1.

Однако такая программа неэффективна, она даже при небольших N выполняет слишком много сложений (см. п. 7.2.1). Для написания более эффективной программы введем в рассмотрение функцию

$F(n)=(\Phi(n-1), \Phi(n))$,

которая в качестве результата дает пару целых чисел -- двух соседних элементов последовательности Фибоначчи. Это определение можно переписать в следующем виде

$G(x,y) = (y,x+y)$,

если доопределить $\Phi(0) = 0$. Тогда $\Phi(n)$ = Второй$Второй(F(n))$, где Второй$Второй$означает функцию извлечения второго элемента пары.

Такое определение нельзя сразу переписать в виде функций языка Zonnon, поскольку в нем все функции должны иметь скалярные результаты. Однако мы можем хранить эту пару в глобальных переменных A,B.

module ФИБ2;
    var A,B,N : integer;
    procedure ФИБ (N:Integer);
        var C:integer;
    begin
        if N = 1 then
             A := 0; B := 1 (*$\{A = \Phi(N-1), B = \Phi(N)\}$*) end
        else ФИБ(N-1); (*$\{A = \Phi(N-2), B = \Phi(N-1)\}$*)
            C := A+B; A := B; B := C (*$\{A = \Phi(N-1), B = \Phi(N)\}$*)
        end
    end ФИБ ;
begin
    read(N);
    ФИБ(N); (* {A = $\Phi$(N-1), B = $\Phi$(N)}    *)
    writeln('$\Phi$(',N,')=',B)
end ФИБ2.

Можно заметить, что смысл программы не изменится, если локальную переменную С процедуры ФИБ объявить в теле программы. После этого рекурсия процедуры ФИБ будет использоваться исключительно для тогo, чтобы повторять последовательность операторов

begin C := A+B; A := B; B := C end.

Это повторение записывается на языке Zonnon с помощью оператора цикла, так что в нашем третьем решении мы элиминируем рекурсию, программа ФИБ3 вовсе не будет содержать процедур и функций:

module ФИБ3;
    var A,B,C,N,I : Integer;
begin
    Read(N); A := 0; B := 1; (*$\{A = \Phi(0), B = \Phi(1)\}$*)
    for I := 2 to N do
         (* {A=Ф(I-2), B= Ф(I-1)}*)
         C := A+B; A := B; B := C (* {A=Ф(I-1), B= Ф(I)}*)
     end;
     (*{B=C=Ф(N)}*)
    writeln ('Ф(',N,')=',B)
end ФИБ3.

Для получения четвертого решения заметим, что записанное выше определение функции $G(x,y) = (y,x+y)$, преобразующей пары целых чисел снова в пары целых чисел, можно переписать с использованием операции произведения матрицы на вектор, а именно

$G(x,y) = M(_y^x),\mbox{ где } M = (_1^0\mbox{ }_1^1).$

Это значит, что $F(n) = M^{n-1}(_1^0)$, а для возведения матрицы $M$ в целую степень можно использовать, по-существу, тот же самый алгоритм быстрого возведения в степень, что и для возведения в степень обычных чисел.

$E = (_0^1 \mbox{ }_1^0),$
$M = (_1^0 \mbox{ }_1^1).$

Можно заметить, что для $n \geq 2$

$M^n = \left ( \begin{array}{ll}\Phi(n-2) & \Phi(n-1) \\\Phi(n-1) & \Phi(n) \\\end {array} \right ).$

так что мы можем представлять матрицу $M^n$ парой чисел -- ее первой строкой. В таком представлении упрощается операция произведения матриц: $(A,B)*(C,D) = (AC + BD, AD + BC + BD).$ С учетом сказанного получаем следующую программу:

module ФИБ4;
    type MATR = array 2 of Integer;
    var K,N : Integer; X,Y : MATR;
    procedure MULT (X,Y : MATR; var Z : MATR);
        var T : integer;
    begin
        T := X[1] $*$ Y[1]; Z[0]:= X[0]$*$ Y[0]+T;
        Z[1]:= X[0] $*$ Y[1]+ X[1]$*$ Y[0] + T
    end MULT;
begin
    Read(N); X[0]:= 0; X[1]:= 1; Y[0]:= 1; Y[1]:= 0; K := N;
    while N # 0 do
        if odd(N) then MULT(Y,X,Y); N := N-1 else MULT(X,X,X); N := N div 2 end
    end;
    writeln('Ф(',K,')=',Y.B)
end ФИБ4.

Для получения рекурсивного решения без излишних сложений рассмотрим следующую функцию (см. ФИБ3) :

Очевидно, что $\Phi(n)=F(0,1,n)$, и мы приходим к следующему рекурсивному решению, которое в отличие от ФИБ1 уже не содержит повторных вычислений членов последовательности:

module ФИБ5;
    var N: Integer;
    procedure F(X, Y, M, N:Integer):Integer;
        begin if N=1 then return Y else return F(Y, X+Y, N-1) end end F;
begin read(N); writeln('$\Phi$(',N,')=', F(0,1,N)) end ФИБ5.