Complejidad de algoritmos a través de sus tiempos de ejecución

Práctica propuesta en la UPM para la asignatura “Algorítmica y Complejidad” en el curso 2012-2013:

Link al enunciado de la práctica en formato pdf

Fichero de ejemplo de entradas en formato pdf

Aquí dejo la solución propuesta por un compañero:

with Text_IO;
use Text_IO;
 
with ada.numerics.generic_elementary_functions;
with Ada.Exceptions;
use Ada.Exceptions;
use ada.numerics;
 
 
procedure pb is
   --Tipos definidos
   type coma_fija is delta 0.0000001 digits 18;
   type datos is array (1..20) of coma_fija;
 
   --Packages
   package coma_fija_IO is new decimal_IO (coma_fija);
   package funciones is new generic_elementary_functions (float);
   package enteros is new integer_IO (integer);
   use enteros;
   use funciones;
 
   --Declaración de variables
   D : datos;
   valor : coma_fija;
   fichero_entrada, fichero_salida : File_Type;
   ultimo : Integer := 20;
   error_prc : coma_fija := 0.01;
 
   --Funciones
 
   --------------------------------------------------------
 
   --Lee 20 datos del fichero. Retorna falso si no se han podido leer
   --20 o si el fichero ha acabado.
   function leer_bloque return boolean is
      n : integer := 1;
   begin
      ultimo := 20;
      while n <= 20 and not End_Of_File(fichero_entrada) loop
         coma_fija_IO.Get(File => fichero_entrada, Item => valor);
         D(n) := coma_fija(valor);
         n := n + 1;
      end loop;
      return n = 21;
   end leer_bloque;
 
   --------------------------------------------------------
 
   --Test de igualdad
   function igual(a, b, error : coma_fija) return boolean is
      r : boolean;
   begin
      r := abs(a - b) < abs(a * error);
      return r;
   end igual;
 
   --------------------------------------------------------
 
   --Función para hacer debug
   procedure print is
   begin
      for n in D'Range loop
         coma_fija_IO.Put(D(n));
         new_line;
      end loop;
   end print;
 
   --------------------------------------------------------
 
   --Deriva los datos actuales invalidando el último dato.
   procedure derivar is
   begin
      for n in D'First..D'Last - 1 loop
         D(n) := D(n + 1) - D(n);
      end loop;
      ultimo := ultimo - 1;
   end derivar;
 
   --------------------------------------------------------
 
   --Test constante
   function test_const return boolean is
      n : Integer := 1;
   begin
      while n <= ultimo and then igual(D(n), D(D'First), error_prc) loop
         n := n + 1;
      end loop;
      return n = ultimo + 1;
   end test_const;
 
   --------------------------------------------------------
 
   --Test exponencial
   function test_exp return boolean is
      n : Integer := 1;
      a, b, log2 : coma_fija;
 
   begin
      log2 := 0.6931472;
 
      if D(1) > D(2) then
         return false;
      end if;
 
      a := coma_fija(log(float(0.5 * (D(2)-D(1))))) / log2;
      b := D(1) - coma_fija((2.0)**(float(a + 1.0)));
 
      while n <= ultimo
      and then igual(D(n), coma_fija((2.0)**(float(a + coma_fija(n)))) + b, 3 * error_prc) loop
         n := n + 1;
      end loop;
 
      return n = ultimo + 1;
 
      exception
      when Error : others =>
         return false;
 
   end test_exp;
 
   --------------------------------------------------------
 
   --Test logaritmo
   function test_log return boolean is
      n : Integer := 1;
      a : coma_fija;
   begin
      if D(1) = 0.0 then
         return false;
      end if;
 
      a := (1.0/D(1)) - 1.0;
      while n <= ultimo and then igual(D(n), 1.0/(coma_fija(n) + a), 2.0 * error_prc) loop
         n := n + 1;
      end loop;
 
      return n = ultimo + 1;
 
      exception
      when Error : others =>
         return false;
 
   end test_log;
 
   --------------------------------------------------------
 
   --Calcular el orden
   function calcular_orden return Integer is
   begin
 
      if test_const then
         return 9;
      elsif test_exp then
         return 8;
      end if;
 
      derivar;
 
      if test_log then
         return 7;
      end if;
 
      for orden in 1..6 loop
         if test_const then
            return orden;
         else
            derivar;
         end if;
      end loop;
 
      return 0;
 
   exception
      when Error : others =>
         return 0;
 
   end calcular_orden;
 
   --------------------------------------------------------
 
   --ENTRADA DEL PROGRAMA
begin
   Open(File => fichero_entrada, Mode => In_File, Name => "f1.txt");
   Create(File => fichero_salida, Mode => Out_file, Name => "f2.txt");
 
   while leer_bloque loop
      Put(FILE => fichero_salida, ITEM => Integer'Image(calcular_orden));
   end loop;
 
   Close (File => fichero_salida);
   Close (File => fichero_entrada);
 
   exception
   when Error : others =>
      Close (File => fichero_salida);
      Close (File => fichero_entrada);
      return;
 
end Pb;