How to resolve the algorithm Fibonacci sequence step by step in the Delphi programming language

Published on 12 May 2024 09:40 PM
#Delphi

How to resolve the algorithm Fibonacci sequence step by step in the Delphi programming language

Table of Contents

Problem Statement

The Fibonacci sequence is a sequence   Fn   of natural numbers defined recursively:

Write a function to generate the   nth   Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition: support for negative     n     in the solution is optional.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fibonacci sequence step by step in the Delphi programming language

Source code in the delphi programming language

function FibonacciI(N: Word): UInt64;
var
  Last, New: UInt64;
  I: Word;
begin
  if N < 2 then
    Result := N
  else begin
    Last := 0;
    Result := 1;
    for I := 2 to N do
    begin
      New := Last + Result;
      Last := Result;
      Result := New;
    end;
  end;
end;

function Fibonacci(N: Word): UInt64;
begin
  if N < 2 then
    Result := N
  else
   Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;

function fib(n: Int64): Int64;

  type TFibMat = array[0..1] of array[0..1] of Int64;
	
  function FibMatMul(a,b: TFibMat): TFibMat;
  var i,j,k: integer;
      tmp: TFibMat;
  begin
    for i := 0 to 1 do
      for j := 0 to 1 do
      begin
	tmp[i,j] := 0;
	for k := 0 to 1 do tmp[i,j] := tmp[i,j] + a[i,k] * b[k,j];
      end;
    FibMatMul := tmp;
  end;
	
  function FibMatExp(a: TFibMat; n: Int64): TFibmat;
  begin
    if n <= 1 then fibmatexp := a
    else if (n mod 2 = 0) then FibMatExp := FibMatExp(FibMatMul(a,a), n div 2)
    else if (n mod 2 = 1) then FibMatExp := FibMatMul(a, FibMatExp(FibMatMul(a,a), n div 2));
  end;

var 
  matrix: TFibMat;
	
begin
  matrix[0,0] := 1;
  matrix[0,1] := 1;
  matrix[1,0] := 1;
  matrix[1,1] := 0;
  if n > 1 then
    matrix := fibmatexp(matrix,n-1);
  fib := matrix[0,0];
end;

You may also check:How to resolve the algorithm Monte Carlo methods step by step in the jq programming language
You may also check:How to resolve the algorithm 100 doors step by step in the Onyx programming language
You may also check:How to resolve the algorithm Run-length encoding step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Leonardo numbers step by step in the D programming language
You may also check:How to resolve the algorithm Short-circuit evaluation step by step in the Erlang programming language