Programa para reducir una fracción dada X/Y

En un libro sobre algoritmos, un problema básico es el siguiente: “escribe un programa para reducir una fracción dada x/y (con números x, y enteros) a sus términos más simples”. Piden que el programa sea hecho en Pascal y en C++.

---

Programa en Pascal:

Program ReduceFraction;

Function GCD(a, b: integer): integer;

begin

  if b = 0 then

    Result := a

  else

    Result := GCD(b, a mod b);

end;

Procedure ReduceFraction(var numerator, denominator: integer);

var

  gcd1: integer;

begin

  gcd1 := GCD(numerator, denominator);

  numerator := numerator div gcd1;

  denominator := denominator div gcd1;

end;

var

  x, y: integer;

Begin

    writeln('Ingrese el numerador (x): ');

    readln(x);

    writeln('Ingrese el denominador (y): ');

    readln(y);

    ReduceFraction(x, y);

    writeln('La fraccion reducida es: ', x, '/', y);

    readln;

End.

---

Programa en C++:

#include <iostream>

int GCD(int a, int b) {

    return (b == 0) ? a : GCD(b, a % b);

}

void ReduceFraction(int& numerator, int& denominator) {

    int gcd = GCD(numerator, denominator);

    numerator /= gcd;

    denominator /= gcd;

}

int main() {

    int x, y;

    std::cout << "Ingrese el numerador (x): ";

    std::cin >> x;

    std::cout << "Ingrese el denominador (y): ";

    std::cin >> y;

    ReduceFraction(x, y);

    std::cout << "La fraccion reducida es: " << x << "/" << y << std::endl;

    return 0;

}

---

Eficiencia de las dos soluciones:

En cuanto a la eficiencia, ambos programas hacen uso del Algoritmo de Euclides para calcular el máximo común divisor (GCD) entre el numerador y el denominador de la fracción. 

El algoritmo de Euclides tiene una complejidad de O(log(min(a, b))), donde “a” y “b” son los números para los que se desean obtener su GCD. 

En términos de eficiencia, la diferencia entre Pascal y C++ puede ser mínima o insignificante, especialmente para algoritmos simples. Ambos lenguajes de programación tienen un rendimiento comparable, en particular, para esta tarea específica.

La elección del lenguaje depende en gran medida de la preferencia personal y de los requisitos del proyecto en general. 

En resumen, ambas soluciones son válidas y eficientes para reducir una fracción a sus términos más bajos. El código en C++ y Pascal logra el mismo objetivo utilizando el Algoritmo de Euclides, y la diferencia de eficiencia entre ambos será insignificante para esta tarea específica.

NOTA sobre la complejidad O(log(min(a, b))) mencionada.

El término “complejidad” se refiere a la cantidad de recursos (como tiempo o memoria) que un algoritmo necesita para resolver un problema en función del tamaño de la entrada.

En el caso del algoritmo de Euclides para calcular el máximo común divisor (GCD) de dos números, su complejidad se estima en O(log(min(a, b))), donde “a” y “b” son los dos números para los cuales se desea calcular el GCD.

Ahora, analicemos la complejidad O(log(min(a, b))) paso a paso:

1. «min(a, b)»: Este término representa el número más pequeño entre “a” y “b”. En el algoritmo de Euclides, el número más pequeño se utiliza como divisor en cada paso de la recursión.

2. «log(min(a, b))»: Esta parte de la complejidad surge porque en cada paso de la recursión, los números involucrados se reducen al menos a la mitad. Es decir, en cada llamada recursiva, al menos uno de los números se reduce a la mitad de su valor original. Esto es similar a dividir el número por 2 repetidamente, lo que en términos de complejidad se representa como un logaritmo en base 2 (log₂).

3. «O»: La notación «O» (orden de) indica que estamos hablando de una estimación asintótica del tiempo de ejecución del algoritmo. Es decir, estamos viendo cómo crece el tiempo de ejecución en el peor de los casos a medida que aumenta el tamaño de la entrada.

Resumiendo…

• La complejidad O(log(min(a, b))) del algoritmo de Euclides nos indica que este algoritmo tiene un tiempo de ejecución eficiente y rápido, incluso para números grandes. 
• A medida que los números “a” y “b” aumentan, la cantidad de pasos requeridos para calcular el GCD crece en forma logarítmica, lo que hace que el algoritmo sea muy eficiente. 
• Por esta razón, el algoritmo de Euclides es ampliamente utilizado para calcular el máximo común divisor y otras aplicaciones matemáticas relacionadas.

---

Lenguaje de programación PASCAL | Tipos de errores comunes en programación | Algoritmos de ordenación y análisis de eficiencia | Ejemplo de algoritmo recursivo: Raíz Cuadrada