Retos - 013: Fracción irreducible

Nivel de dificultad aproximado (1 a 5): 1  

Enunciado del problema

Crea un programa que dado un número entre 0,0001 y 0,9999 (y de no más de 4 cifras decimales), obtenga y muestre la correspondiente fracción irreducible.

Por ejemplo, el número 0,25 se puede obtener a partir de 25/100, o de 2/8, o de 1/4, entre otros. La fracción irreducible es 1/4, que está formada por un numerador y un denominador que son primos entre sí.

Nota: el programa no debe avisar al usuario con mensajes como "Introduzca un número". Debe leer directamente el número que introduzca el usuario. De igual modo, sólo debe mostrar la fracción irreducible encontrada, nada más. Tampoco debe hacer ninguna pausa antes ni después de la ejecución.

Entradas y salidas de ejemplo 
Entrada 1:
0,25



Salida 1:
1/4



Entrada 2:
0,5



Salida 2:
1/2



Entrada 3:
0,125



Salida 3:
1/8



Entrada 4:
0,002



Salida 4:
1/500



Entrada 5:
0,376



Salida 5:
47/125
Procedencia del reto

Original en: Fase 1 de las Olimpiadas británicas de informática 2005, primera pregunta

Explicación

La solución más simple, ya que sólo hay 10.000 posibles valores, probar todas las soluciones posibles. Para obtener la solución ya simplificada, se puede intentar con todas las divisiones entre 2 (es decir, sólo 1/2), luego entre 3 (1/3 y 2/3), luego entre 4, y así sucesivamente: para cada divisor N, se prueba con todos los números entre 0 y N-1. En cuanto se encuentra una solución, se detiene la búsqueda.

Una solución más elegante podría ser directamente expresar el número en forma de fracción, usando 10.000 como denominador, por eso de que las soluciones sólo tienen 4 cifras (por ejemplo 0,75 sería 7500/10000) y entonces dividir el numerador y en denominador entre su máximo común divisor. En el caso de 7500/1000, el MCD es 2500, de modo que la fracción quedaría como 3/4. El problema de esta solución es que lo habitual es calcular el MCD usando una función auxiliar, de modo que esta solución ya no es de nivel 1.

Una solución alternativa, simple y rápida, y razonable para el nivel 1, aunque necesita un poco de "feliz idea" es partir del número expresado en forma de fracción y dividir numerador y denominador tantas veces como se puedan entre 2 y entre 5 (porque son los únicos números primos entre los que se puede dividir y obtener un resultado con 4 cifras decimales o menos).

Aporta tu solución

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 3 menos dos?
Lenguaje
Fuente:

Ejemplo de solución en C 

/* Solucion al reto 004
 Autor: ptek
 Aportado: 28-10-2014
*/
#include <stdio.h>
int mcd1(int m, int n);
int main()
{
    double decimal;
    int count=10000,i=1,j,mcd;
    double resultado;
    int salir = 1;
 
    int numerador, denominador;
    /* printf("Dame tu numero\n"); */
    scanf("%lf",&resultado);
    while (salir)
    {
        /* code */
        for ( j = 1; j <= count; j++)
        {
            decimal = (double)i/j;
 
                mcd = mcd1(i,j);
            //printf("%.5f",resultado);
            if ((resultado==decimal)&&(mcd==1))
            {
                numerador = i;
                denominador = j;
                salir=0;
            }
        }
        i++;
    }
    printf("%d/%d\n",numerador,denominador);
    return 0;
}
 
int mcd1(int m, int n)
{
   int r;
 
   r= m%n;
   if (r==0)
   {
        return n;
   }
   else
   {
        return mcd1(n,r);
   }
}
 

Ejemplo de solución en C++ 

// Ejemplo de solución para el reto 013 (fracción irreducible)
// Primera aproximación: probar todas las divisiones posibles
//   (lenta pero razonable para el nivel de dificultad 1)
// Por Nacho
// Aportado: 27-06-2015
 
#include <iostream>
#include <string>
using namespace std;
 
int main() 
{
    double n;
    cin >> n;
    int denominador = 2;
    int numerador;
    bool terminado = false;
    while ( (denominador<=10000) && (! terminado) )
    {
        numerador = 1;
        while ( (numerador<denominador) && (! terminado) )
        {
            if (((double) numerador / denominador) == n)
            {
                cout << numerador << "/" << denominador << endl;
                terminado = true;;
            }
            numerador++;
        }
        denominador++;
    }
    return 0;
}

Ejemplo de solución en C++ (2) 

// Ejemplo de solución para el reto 013 (fracción irreducible)
// Segunda aproximación: simplificar numerador y denominador
//   dividiendo entre 2 y entre 5
// Por Nacho
// Aportado: 27-06-2015
 
#include <iostream>
#include <string>
using namespace std;
 
int main() 
{
    double n;
    cin >> n;
 
    int numerador = (int) (n * 10000);        
    int denominador = 10000;
 
    while (numerador % 2 == 0)
    {
        denominador /= 2;
        numerador /= 2;
    }
 
    while (numerador % 5 == 0)
    {
        denominador /= 5;
        numerador /= 5;
    }    
 
    cout << numerador << "/" << denominador << endl;    
    return 0;
}

Ejemplo de solución en C++ (3) 

// Ejemplo de solución para el reto 013 (fracción irreducible)
// Tercera aproximación: simplificar numerador y denominador
//   dividiendo por su máximo común divisor (usa funciones)
// Por Nacho
// Aportado: 27-06-2015
 
#include <iostream>
#include <string>
using namespace std;
 
int maximoComunDivisor(int a, int b)
{
    if (a % b == 0 )
        return b;
    else
        return maximoComunDivisor( b , a%b );
}
 
int main() 
{
    double n;
    cin >> n;
 
    int numerador = (int) (n * 10000);        
    int denominador = 10000;
 
    int mcd = maximoComunDivisor(numerador, denominador);
 
    cout << numerador/mcd << "/" << denominador/mcd << endl;    
    return 0;
}
 

Ejemplo de solución en C++ (4) 

// Ejemplo de solución para el reto 013 (fracción irreducible)
// Por abel mamani
// Aportado: 22-05-2015
 
#include <iostream>
 
using namespace std;
 
int main()
{
    float x,cont,var,cont2=1;
    cin>>x;
    var=x;
    cont=0;
    if(x>0.0001&&x<0.9999)
    {
 
    do
    {
        cont++;
        var=cont*x;
 
        if(var>cont2)cont2++;
    }while(var!=cont2);
    cout<<cont2<<"/"<<cont<<endl;
    }
    return 0;
}

Ejemplo de solución en C# 

// Ejemplo de solución para el reto 013
// Por (Autor desconocido)
// Nota del recopilador: se acerca, pero tiene dos fallos y no se comporta bien en 0,376
 
// Fracción irreducible
// Aportado: 15-10-2012
 
using System;
public class FraccionIrreducible
{
     public static void Main()
     {
        float numero;
        int numerador, denominador = 10000;
        numero=Convert.ToSingle(Console.ReadLine());
        numerador = (int)(numero * 10000);
 
        for(int i = numerador; i>1; i--){
            if(numerador%i==0 && denominador%i==0){
                numerador=numerador/i;
                denominador=denominador/i;
            }
        }
 
        Console.WriteLine("{0}/{1}",numerador,denominador);
     }
}
 

Ejemplo de solución en C# (2) 

// Ejemplo de solución para el reto 013
// Por Luis Angel
 
// Fracción irreducible
// Aportado: 18-10-2014
 
using System;
 
class Irreducible
{
    static void Main(string[] args)
    {
        double n1;
        int dm;
 
        // La versión definitiva no debe avisar al usuario
        // Console.WriteLine("Escribe un numero decimal de no mas de 4 cifras decimales:");
        n1 = double.Parse(Console.ReadLine());
        dm = 10000;
        n1 = n1 * dm;
 
        if (n1 >= 1 & n1 <= 9999)
        {
            while (n1 % 2 == 0)
            {
                n1 = n1 / 2;
                dm = dm / 2;
            }
            while (n1 % 5 == 0)
            {
                n1 = n1 / 5;
                dm = dm / 5;
            }
            // La versión definitiva no debe avisar al usuario
            // Console.WriteLine("Su fraccion irreducible es:" + n1 + "/" + dm);
            Console.WriteLine(n1 + "/" + dm);
        }
    }
}
 

Ejemplo de solución en Java 

/*
 * Reto 013
 * 
 * Crea un programa que dado un número entre 0,0001 y 0,9999 (y de no 
 * más de 4 cifras decimales),
 * obtenga y muestre la correspondiente fracción irreducible.
 * Por ejemplo, el número 0,25 se puede obtener a partir de 25/100, o 
 * de 2/8, o de 1/4, entre otros.
 * La fracción irreducible es 1/4, que está formada por un numerador
 * y un denominador que son primos entre sí.
 */
 
import java.util.Scanner;
 
/**
 * @author Gaston Zarate
 * Aportado: 05-11-2014
 */
 
public class Reto013 {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
 
        // El proyecto definitivo no debe preguntar al usuario
        // System.out.println("Ingrese el numero");
 
        Scanner sc = new Scanner(System.in);
        Float num = sc.nextFloat();
 
        int decimales = (num.toString().length()-2);
        String mult="1";
        for (int i = 0; i < decimales; i++) {
            mult+="0";
        }
 
        int denominador = Integer.parseInt(mult);
        int numerador = (int) (num*denominador);
 
 
        for (int i = 2; i <= denominador+1; i++) {
            if(numerador%i==0 && denominador%i==0)
            {
                numerador/=i;
                denominador/=i;
                i=2;
            }
        }
        System.out.println(numerador+"/"+denominador);
    }
 
}
 

Ejemplo de solución en Python 

# Solucion de ejemplo al reto 013: fraccion irreducible
# Autor: ivan Jara
# Aportado: 15-Jun-2014
 
num = float(raw_input())
denominador = 10000
numerador = int(num * 10000)
i = numerador
while i > 1 :
    if numerador % i == 0 and denominador % i == 0:
        numerador = numerador / i
        denominador = denominador / i
    i =  i - 1
 
print "%d/%d " %(numerador, denominador)