Страницы

Вычисление чисел Фибоначчи без цикла

Всё что угодно можно вычислить без циклов и рекурсивных вызовов, например, числа Фибоначчи.
MODULE Fib;

 VAR i: INTEGER; a, b, c: REAL;

 PROCEDURE L0(): BOOLEAN;
 BEGIN
  c := a + b;
  a := b;
  b := c;
  DEC(i)
 RETURN
  i > 0
 END L0;

 PROCEDURE L1(): BOOLEAN; RETURN L0()&L0()&L0()&L0()&L0()&L0()&L0() END L1;
 PROCEDURE L2(): BOOLEAN; RETURN L1()&L1()&L1()&L1()&L1()&L1()&L1() END L2;
 PROCEDURE L3(): BOOLEAN; RETURN L2()&L2()&L2()&L2()&L2()&L2()&L2() END L3;
 PROCEDURE L4(): BOOLEAN; RETURN L3()&L3()&L3()&L3()&L3()&L3()&L3() END L4;

 PROCEDURE Num*(n: INTEGER): REAL;
 BEGIN
  ASSERT(n >= 0);
  a := 0.0; b := 1.0; c := 0.0;
  i := n - 1;
  ASSERT((i < 0) OR ~L4())
 RETURN
  c
 END Num;

END Fib.

Так как показательная функция растёт очень быстро, то несложно обеспечить сколь угодное количество шагов вычислений, но учитывая диапазон REAL, и 2401 шагов, обеспечиваемых функциями L1,L2,L3,L4 — это более, чем достаточно.

По измерениям, это своеобразное воплощение работает в три раза медленней обычного цикла для вычисления чисел Фибоначчи.

Этот код в песочнице.

Комментариев нет:

Отправить комментарий