algorithm language-agnostic numbers

algorithm - ¿Cómo convertir flotadores a fracciones legibles por humanos?



language-agnostic numbers (26)

Digamos que tenemos 0.33, necesitamos dar salida a "1/3". Si tenemos "0.4", tenemos que generar "2/5".

Está mal en el caso común, debido a 1/3 = 0.3333333 = 0. (3) Además, es imposible averiguar a partir de las soluciones sugeridas anteriormente, es decimal se puede convertir a fracción con precisión definida, porque la salida siempre es una fracción.

PERO, sugiero mi función integral con muchas opciones basadas en la idea de series geométricas infinitas , específicamente en la fórmula:

Al principio, esta función está tratando de encontrar el período de fracción en la representación de cadena. Después de eso, se aplica la fórmula descrita anteriormente.

El código de los números racionales se toma prestado de la implementación de los números racionales de Stephen M. McKamey en C #. Espero que no sea muy difícil portar mi código en otros idiomas.

/// <summary> /// Convert decimal to fraction /// </summary> /// <param name="value">decimal value to convert</param> /// <param name="result">result fraction if conversation is succsess</param> /// <param name="decimalPlaces">precision of considereation frac part of value</param> /// <param name="trimZeroes">trim zeroes on the right part of the value or not</param> /// <param name="minPeriodRepeat">minimum period repeating</param> /// <param name="digitsForReal">precision for determination value to real if period has not been founded</param> /// <returns></returns> public static bool FromDecimal(decimal value, out Rational<T> result, int decimalPlaces = 28, bool trimZeroes = false, decimal minPeriodRepeat = 2, int digitsForReal = 9) { var valueStr = value.ToString("0.0000000000000000000000000000", CultureInfo.InvariantCulture); var strs = valueStr.Split(''.''); long intPart = long.Parse(strs[0]); string fracPartTrimEnd = strs[1].TrimEnd(new char[] { ''0'' }); string fracPart; if (trimZeroes) { fracPart = fracPartTrimEnd; decimalPlaces = Math.Min(decimalPlaces, fracPart.Length); } else fracPart = strs[1]; result = new Rational<T>(); try { string periodPart; bool periodFound = false; int i; for (i = 0; i < fracPart.Length; i++) { if (fracPart[i] == ''0'' && i != 0) continue; for (int j = i + 1; j < fracPart.Length; j++) { periodPart = fracPart.Substring(i, j - i); periodFound = true; decimal periodRepeat = 1; decimal periodStep = 1.0m / periodPart.Length; var upperBound = Math.Min(fracPart.Length, decimalPlaces); int k; for (k = i + periodPart.Length; k < upperBound; k += 1) { if (periodPart[(k - i) % periodPart.Length] != fracPart[k]) { periodFound = false; break; } periodRepeat += periodStep; } if (!periodFound && upperBound - k <= periodPart.Length && periodPart[(upperBound - i) % periodPart.Length] > ''5'') { var ind = (k - i) % periodPart.Length; var regroupedPeriod = (periodPart.Substring(ind) + periodPart.Remove(ind)).Substring(0, upperBound - k); ulong periodTailPlusOne = ulong.Parse(regroupedPeriod) + 1; ulong fracTail = ulong.Parse(fracPart.Substring(k, regroupedPeriod.Length)); if (periodTailPlusOne == fracTail) periodFound = true; } if (periodFound && periodRepeat >= minPeriodRepeat) { result = FromDecimal(strs[0], fracPart.Substring(0, i), periodPart); break; } else periodFound = false; } if (periodFound) break; } if (!periodFound) { if (fracPartTrimEnd.Length >= digitsForReal) return false; else { result = new Rational<T>(long.Parse(strs[0]), 1, false); if (fracPartTrimEnd.Length != 0) result = new Rational<T>(ulong.Parse(fracPartTrimEnd), TenInPower(fracPartTrimEnd.Length)); return true; } } return true; } catch { return false; } } public static Rational<T> FromDecimal(string intPart, string fracPart, string periodPart) { Rational<T> firstFracPart; if (fracPart != null && fracPart.Length != 0) { ulong denominator = TenInPower(fracPart.Length); firstFracPart = new Rational<T>(ulong.Parse(fracPart), denominator); } else firstFracPart = new Rational<T>(0, 1, false); Rational<T> secondFracPart; if (periodPart != null && periodPart.Length != 0) secondFracPart = new Rational<T>(ulong.Parse(periodPart), TenInPower(fracPart.Length)) * new Rational<T>(1, Nines((ulong)periodPart.Length), false); else secondFracPart = new Rational<T>(0, 1, false); var result = firstFracPart + secondFracPart; if (intPart != null && intPart.Length != 0) { long intPartLong = long.Parse(intPart); result = new Rational<T>(intPartLong, 1, false) + (intPartLong == 0 ? 1 : Math.Sign(intPartLong)) * result; } return result; } private static ulong TenInPower(int power) { ulong result = 1; for (int l = 0; l < power; l++) result *= 10; return result; } private static decimal TenInNegPower(int power) { decimal result = 1; for (int l = 0; l > power; l--) result /= 10.0m; return result; } private static ulong Nines(ulong power) { ulong result = 9; if (power >= 0) for (ulong l = 0; l < power - 1; l++) result = result * 10 + 9; return result; }

Hay algunos ejemplos de uso:

Rational<long>.FromDecimal(0.33333333m, out r, 8, false); // then r == 1 / 3; Rational<long>.FromDecimal(0.33333333m, out r, 9, false); // then r == 33333333 / 100000000;

Su caso con el recorte de la pieza de la parte derecha cero:

Rational<long>.FromDecimal(0.33m, out r, 28, true); // then r == 1 / 3; Rational<long>.FromDecimal(0.33m, out r, 28, true); // then r == 33 / 100;

Demostración del período mínimo:

Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.5m)); // then r == 1234 / 9999; Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.6m)); // then r == 123412 / 1000000; because of minimu repeating of period is 0.1234123 in this case.

Redondeo al final:

Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r)); // then r == 8 == 9;

El caso más interesante:

Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 9); // then r == 12345678 / 100000000; Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 8); // Conversation failed, because of period has not been founded and there are too many digits in fraction part of input value. Rational<long>.FromDecimal(0.12121212121212121m, out r, 28, true, 2, 9)); // then r == 4 / 33; Despite of too many digits in input value, period has been founded. Thus it''s possible to convert value to fraction.

Otras pruebas y códigos que todos pueden encontrar en mi biblioteca MathFunctions en github .

Digamos que tenemos 0.33, necesitamos dar salida a "1/3".
Si tenemos "0.4", tenemos que generar "2/5".

La idea es hacer que sea legible para los humanos para que el usuario comprenda "x partes de y" como una mejor forma de entender los datos.

Sé que los porcentajes son un buen sustituto, pero me preguntaba si había una manera simple de hacerlo.

"Digamos que tenemos 0.33, necesitamos producir" 1/3 "."

¿Qué precisión esperas que tenga la "solución"? 0.33 no es igual a 1/3. ¿Cómo se reconoce una respuesta "buena" (fácil de leer)?

No importa qué, un posible algoritmo podría ser:

Si espera encontrar la fracción más cercana en una forma X / Y donde Y es menor que 10, entonces puede recorrer los 9 posibles Ys, para cada Y calcular X, y luego seleccionar la más precisa.

Aquí está la implementación de ruby http://github.com/valodzka/frac

Math.frac(0.2, 100) # => (1/5) Math.frac(0.33, 10) # => (1/3) Math.frac(0.33, 100) # => (33/100)

Aquí están las versiones Perl y Javascript del código VB sugerido por devinmoore:

Perl:

sub dec2frac { my $d = shift; my $df = 1; my $top = 1; my $bot = 1; while ($df != $d) { if ($df < $d) { $top += 1; } else { $bot += 1; $top = int($d * $bot); } $df = $top / $bot; } return "$top/$bot"; }

Y el javascript casi idéntico:

function dec2frac(d) { var df = 1; var top = 1; var bot = 1; while (df != d) { if (df < d) { top += 1; } else { bot += 1; top = parseInt(d * bot); } df = top / bot; } return top + ''/'' + bot; }

Aquí hay un enlace que explica las matemáticas detrás de la conversión de un decimal a una fracción:

http://www.webmath.com/dec2fract.html

Y aquí hay una función de ejemplo de cómo hacerlo realmente usando VB (desde www.freevbcode.com/ShowCode.asp?ID=582):

Public Function Dec2Frac(ByVal f As Double) As String Dim df As Double Dim lUpperPart As Long Dim lLowerPart As Long lUpperPart = 1 lLowerPart = 1 df = lUpperPart / lLowerPart While (df <> f) If (df < f) Then lUpperPart = lUpperPart + 1 Else lLowerPart = lLowerPart + 1 lUpperPart = f * lLowerPart End If df = lUpperPart / lLowerPart Wend Dec2Frac = CStr(lUpperPart) & "/" & CStr(lLowerPart) End Function

(De las búsquedas de Google: convierte decimal a fracción, convierte decimal a código de fracción)

Aquí hay una implementación rápida y sucia en javascript que usa un enfoque de fuerza bruta. No optimizado en absoluto, funciona dentro de un rango predefinido de fracciones: http://jsfiddle.net/PdL23/1/

/* This should convert any decimals to a simplified fraction within the range specified by the two for loops. Haven''t done any thorough testing, but it seems to work fine. I have set the bounds for numerator and denominator to 20, 20... but you can increase this if you want in the two for loops. Disclaimer: Its not at all optimized. (Feel free to create an improved version.) */ decimalToSimplifiedFraction = function(n) { for(num = 1; num < 20; num++) { // "num" is the potential numerator for(den = 1; den < 20; den++) { // "den" is the potential denominator var multiplyByInverse = (n * den ) / num; var roundingError = Math.round(multiplyByInverse) - multiplyByInverse; // Checking if we have found the inverse of the number, if((Math.round(multiplyByInverse) == 1) && (Math.abs(roundingError) < 0.01)) { return num + "/" + den; } } } }; //Put in your test number here. var floatNumber = 2.56; alert(floatNumber + " = " + decimalToSimplifiedFraction(floatNumber));

Esto está inspirado en el enfoque utilizado por JPS.

Como mucha gente ha declarado, realmente no se puede convertir un punto flotante en una fracción (a menos que sea extremadamente exacto como .25). Por supuesto, puede crear algún tipo de búsqueda para una gran variedad de fracciones y utilizar algún tipo de lógica difusa para producir el resultado que está buscando. De nuevo, esto no sería exacto y necesitarías definir un límite inferior de cuán grande quieres que sea el denominador.

.32 <x <.34 = 1/3 o algo así.

Completó el código anterior y lo convirtió en as3

public static function toFrac(f:Number) : String { if (f>1) { var parte1:int; var parte2:Number; var resultado:String; var loc:int = String(f).indexOf("."); parte2 = Number(String(f).slice(loc, String(f).length)); parte1 = int(String(f).slice(0,loc)); resultado = toFrac(parte2); parte1 *= int(resultado.slice(resultado.indexOf("/") + 1, resultado.length)) + int(resultado.slice(0, resultado.indexOf("/"))); resultado = String(parte1) + resultado.slice(resultado.indexOf("/"), resultado.length) return resultado; } if( f < 0.47 ) if( f < 0.25 ) if( f < 0.16 ) if( f < 0.13 ) if( f < 0.11 ) return "1/10"; else return "1/9"; else if( f < 0.14 ) return "1/8"; else return "1/7"; else if( f < 0.19 ) return "1/6"; else if( f < 0.22 ) return "1/5"; else return "2/9"; else if( f < 0.38 ) if( f < 0.29 ) return "1/4"; else if( f < 0.31 ) return "2/7"; else return "1/3"; else if( f < 0.43 ) if( f < 0.40 ) return "3/8"; else return "2/5"; else if( f < 0.44 ) return "3/7"; else return "4/9"; else if( f < 0.71 ) if( f < 0.60 ) if( f < 0.56 ) return "1/2"; else if( f < 0.57 ) return "5/9"; else return "4/7"; else if( f < 0.63 ) return "3/5"; else if( f < 0.66 ) return "5/8"; else return "2/3"; else if( f < 0.80 ) if( f < 0.74 ) return "5/7"; else if(f < 0.78 ) return "3/4"; else return "7/9"; else if( f < 0.86 ) if( f < 0.83 ) return "4/5"; else return "5/6"; else if( f < 0.88 ) return "6/7"; else if( f < 0.89 ) return "7/8"; else if( f < 0.90 ) return "8/9"; else return "9/10"; }

Creo que la mejor manera de hacerlo es convertir primero el valor de flotación a una representación ascii. En C ++ puedes usar ostringstream o en C, puedes usar sprintf. Así es como se vería en C ++:

ostringstream oss; float num; cin >> num; oss << num; string numStr = oss.str(); int i = numStr.length(), pow_ten = 0; while (i > 0) { if (numStr[i] == ''.'') break; pow_ten++; i--; } for (int j = 1; j < pow_ten; j++) { num *= 10.0; } cout << static_cast<int>(num) << "/" << pow(10, pow_ten - 1) << endl;

Un enfoque similar podría tomarse en C.

Luego necesitarás verificar que la fracción esté en los términos más bajos. Este algoritmo dará una respuesta precisa, es decir, 0.33 arrojaría "33/100", no "1/3". Sin embargo, 0.4 daría "4/10", que cuando se reduce a los términos más bajos sería "2/5". Esto puede no ser tan poderoso como la solución de EppStein, pero creo que esto es más sencillo.

Desde Python 2.6 en adelante está el módulo de fractions .

(Citando de los documentos)

>>> from fractions import Fraction >>> Fraction(''3.1415926535897932'').limit_denominator(1000) Fraction(355, 113) >>> from math import pi, cos >>> Fraction.from_float(cos(pi/3)) Fraction(4503599627370497, 9007199254740992) >>> Fraction.from_float(cos(pi/3)).limit_denominator() Fraction(1, 2)

El árbol de Stern-Brocot induce una forma bastante natural de aproximar números reales por fracciones con denominadores simples.

Encontré una solución Haskell especialmente elegante haciendo uso de un anamorfismo. Depende del paquete de recursion-schemes .

{-# LANGUAGE AllowAmbiguousTypes #-} {-# LANGUAGE FlexibleContexts #-} import Control.Applicative (liftA2) import Control.Monad (ap) import Data.Functor.Foldable import Data.Ratio (Ratio, (%)) isInteger :: (RealFrac a) => a -> Bool isInteger = ((==) <*>) (realToFrac . floor) continuedFraction :: (RealFrac a) => a -> [Int] continuedFraction = liftA2 (:) floor (ana coalgebra) where coalgebra x | isInteger x = Nil | otherwise = Cons (floor alpha) alpha where alpha = 1 / (x - realToFrac (floor x)) collapseFraction :: (Integral a) => [Int] -> Ratio a collapseFraction [x] = fromIntegral x % 1 collapseFraction (x:xs) = (fromIntegral x % 1) + 1 / collapseFraction xs -- | Use the nth convergent to approximate x approximate :: (RealFrac a, Integral b) => a -> Int -> Ratio b approximate x n = collapseFraction $ take n (continuedFraction x)

Si pruebas esto en ghci, ¡realmente funciona!

λ:> approximate pi 2 22 % 7

Es posible que desee leer Lo que todo científico informático debería saber sobre la aritmética de punto flotante .

Deberá especificar cierta precisión multiplicando por un número grande:

3.141592 * 1000000 = 3141592

entonces puedes hacer una fracción:

3 + (141592 / 1000000)

y reducir a través de GCD ...

3 + (17699 / 125000)

pero no hay forma de sacar la fracción deseada . Puede usar siempre fracciones en todo su código; ¡simplemente recuerde reducir fracciones cuando pueda para evitar el desbordamiento!

Este algoritmo de Ian Richards / John Kennedy no solo devuelve buenas fracciones, sino que también funciona muy bien en términos de velocidad. Este es el código C # tomado de esta respuesta por mí.

Puede manejar todos los valores double excepto valores especiales como NaN y +/- infinito, que deberá agregar si es necesario.

Devuelve una new Fraction(numerator, denominator) . Reemplace por su propio tipo.

Para obtener más valores de ejemplo y una comparación con otros algoritmos, vaya aquí

public Fraction RealToFraction(double value, double accuracy) { if (accuracy <= 0.0 || accuracy >= 1.0) { throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1."); } int sign = Math.Sign(value); if (sign == -1) { value = Math.Abs(value); } // Accuracy is the maximum relative error; convert to absolute maxError double maxError = sign == 0 ? accuracy : value * accuracy; int n = (int) Math.Floor(value); value -= n; if (value < maxError) { return new Fraction(sign * n, 1); } if (1 - maxError < value) { return new Fraction(sign * (n + 1), 1); } double z = value; int previousDenominator = 0; int denominator = 1; int numerator; do { z = 1.0 / (z - (int) z); int temp = denominator; denominator = denominator * (int) z + previousDenominator; previousDenominator = temp; numerator = Convert.ToInt32(value * denominator); } while (Math.Abs(value - (double) numerator / denominator) > maxError && z != (int) z); return new Fraction((n * denominator + numerator) * sign, denominator); }

Valores de ejemplo devueltos por este algoritmo:

Accuracy: 1.0E-3 | Richards Input | Result Error ======================| ============================= 3 | 3/1 0 0.999999 | 1/1 1.0E-6 1.000001 | 1/1 -1.0E-6 0.50 (1/2) | 1/2 0 0.33... (1/3) | 1/3 0 0.67... (2/3) | 2/3 0 0.25 (1/4) | 1/4 0 0.11... (1/9) | 1/9 0 0.09... (1/11) | 1/11 0 0.62... (307/499) | 8/13 2.5E-4 0.14... (33/229) | 16/111 2.7E-4 0.05... (33/683) | 10/207 -1.5E-4 0.18... (100/541) | 17/92 -3.3E-4 0.06... (33/541) | 5/82 -3.7E-4 0.1 | 1/10 0 0.2 | 1/5 0 0.3 | 3/10 0 0.4 | 2/5 0 0.5 | 1/2 0 0.6 | 3/5 0 0.7 | 7/10 0 0.8 | 4/5 0 0.9 | 9/10 0 0.01 | 1/100 0 0.001 | 1/1000 0 0.0001 | 1/10000 0 0.33333333333 | 1/3 1.0E-11 0.333 | 333/1000 0 0.7777 | 7/9 1.0E-4 0.11 | 10/91 -1.0E-3 0.1111 | 1/9 1.0E-4 3.14 | 22/7 9.1E-4 3.14... (pi) | 22/7 4.0E-4 2.72... (e) | 87/32 1.7E-4 0.7454545454545 | 38/51 -4.8E-4 0.01024801004 | 2/195 8.2E-4 0.99011 | 100/101 -1.1E-5 0.26... (5/19) | 5/19 0 0.61... (37/61) | 17/28 9.7E-4 | Accuracy: 1.0E-4 | Richards Input | Result Error ======================| ============================= 0.62... (307/499) | 299/486 -6.7E-6 0.05... (33/683) | 23/476 6.4E-5 0.06... (33/541) | 33/541 0 1E-05 | 1/99999 1.0E-5 0.7777 | 1109/1426 -1.8E-7 3.14... (pi) | 333/106 -2.6E-5 2.72... (e) | 193/71 1.0E-5 0.61... (37/61) | 37/61 0

Esto no es un "algoritmo", solo una solución de Python: fractions

>>> from fractions import Fraction >>> Fraction(''3.1415926535897932'').limit_denominator(1000) Fraction(355, 113)

He encontrado que la aproximación racional del hallazgo de David Eppstein al código real del número C dado es exactamente lo que estás pidiendo. Está basado en la teoría de fracciones continuas y muy rápido y bastante compacto.

He usado versiones de esto personalizadas para los límites específicos de numerador y denominador.

/* ** find rational approximation to given real number ** David Eppstein / UC Irvine / 8 Aug 1993 ** ** With corrections from Arno Formella, May 2008 ** ** usage: a.out r d ** r is real number to approx ** d is the maximum denominator allowed ** ** based on the theory of continued fractions ** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...))) ** then best approximation is found by truncating this series ** (with some adjustments in the last term). ** ** Note the fraction can be recovered as the first column of the matrix ** ( a1 1 ) ( a2 1 ) ( a3 1 ) ... ** ( 1 0 ) ( 1 0 ) ( 1 0 ) ** Instead of keeping the sequence of continued fraction terms, ** we just keep the last partial product of these matrices. */ #include <stdio.h> main(ac, av) int ac; char ** av; { double atof(); int atoi(); void exit(); long m[2][2]; double x, startx; long maxden; long ai; /* read command line arguments */ if (ac != 3) { fprintf(stderr, "usage: %s r d/n",av[0]); // AF: argument missing exit(1); } startx = x = atof(av[1]); maxden = atoi(av[2]); /* initialize matrix */ m[0][0] = m[1][1] = 1; m[0][1] = m[1][0] = 0; /* loop finding terms until denom gets too big */ while (m[1][0] * ( ai = (long)x ) + m[1][1] <= maxden) { long t; t = m[0][0] * ai + m[0][1]; m[0][1] = m[0][0]; m[0][0] = t; t = m[1][0] * ai + m[1][1]; m[1][1] = m[1][0]; m[1][0] = t; if(x==(double)ai) break; // AF: division by zero x = 1/(x - (double) ai); if(x>(double)0x7FFFFFFF) break; // AF: representation failure } /* now remaining x is between 0 and 1/ai */ /* approx as either 0 or 1/m where m is max that will fit in maxden */ /* first try zero */ printf("%ld/%ld, error = %e/n", m[0][0], m[1][0], startx - ((double) m[0][0] / (double) m[1][0])); /* now try other possibility */ ai = (maxden - m[1][1]) / m[1][0]; m[0][0] = m[0][0] * ai + m[0][1]; m[1][0] = m[1][0] * ai + m[1][1]; printf("%ld/%ld, error = %e/n", m[0][0], m[1][0], startx - ((double) m[0][0] / (double) m[1][0])); }

Implementación de AC #

/// <summary> /// Represents a rational number /// </summary> public struct Fraction { public int Numerator; public int Denominator; /// <summary> /// Constructor /// </summary> public Fraction(int numerator, int denominator) { this.Numerator = numerator; this.Denominator = denominator; } /// <summary> /// Approximates a fraction from the provided double /// </summary> public static Fraction Parse(double d) { return ApproximateFraction(d); } /// <summary> /// Returns this fraction expressed as a double, rounded to the specified number of decimal places. /// Returns double.NaN if denominator is zero /// </summary> public double ToDouble(int decimalPlaces) { if (this.Denominator == 0) return double.NaN; return System.Math.Round( Numerator / (double)Denominator, decimalPlaces ); } /// <summary> /// Approximates the provided value to a fraction. /// http://.com/questions/95727/how-to-convert-floats-to-human-readable-fractions /// </summary> private static Fraction ApproximateFraction(double value) { const double EPSILON = .000001d; int n = 1; // numerator int d = 1; // denominator double fraction = n / d; while (System.Math.Abs(fraction - value) > EPSILON) { if (fraction < value) { n++; } else { d++; n = (int)System.Math.Round(value * d); } fraction = n / (double)d; } return new Fraction(n, d); } }

Parte del problema es que muchas fracciones no se pueden interpretar fácilmente como fracciones. Ej. 0.33 no es 1/3, es 33/100. Pero si recuerda su entrenamiento en la escuela primaria, entonces hay un proceso de conversión de valores decimales en fracciones, sin embargo, es poco probable que le proporcione lo que desea, ya que la mayoría de las veces los números decimales no se almacenan en 0.33, pero 0.329999999999998 o algo así.

Hágase un favor y no se moleste con esto, pero si lo necesita, puede hacer lo siguiente:

Multiplica el valor original por 10 hasta que elimines la parte fraccionaria. Mantenga ese número y úselo como divisor. Luego haga una serie de simplificaciones buscando denominadores comunes.

Entonces 0.4 sería 4/10. Luego buscaría divisores comunes comenzando con valores bajos, probablemente números primos. Comenzando con 2, vería si 2 divide uniformemente el numerador y el denominador al verificar si el piso de la división es el mismo que la división misma.

floor(5/2) = 2 5/2 = 2.5

Entonces 5 no divide 2 de manera uniforme. Entonces, verifica el siguiente número, digamos 3. Haces esto hasta que alcances o superes la raíz cuadrada del número más pequeño.

Después de hacer eso, entonces necesita

Puede hacer esto en cualquier lenguaje de programación usando los siguientes pasos:

  1. Multiplica y divide por 10 ^ x donde x es la potencia de 10 requerida para asegurarte de que el número no tenga decimales restantes. Ejemplo: multiplicar 0,33 por 10 ^ 2 = 100 para que sea 33 y dividirlo por el mismo para obtener 33/100
  2. Reduce el numerador y el denominador de la fracción resultante por factorización, hasta que ya no puedas obtener enteros del resultado.
  3. La fracción reducida resultante debería ser tu respuesta.

Ejemplo: 0.2 = 0.2 x 10 ^ 1/10 ^ 1 = 2/10 = 1/5

Entonces, eso se puede leer como ''1 parte de 5''

Responda en C ++, suponiendo que tiene una clase ''BigInt'', que puede almacenar enteros de tamaño ilimitado.

Puede usar ''unsigned long long'' en su lugar, pero solo funcionará para ciertos valores.

void GetRational(double val) { if (val == val+1) // Inf throw "Infinite Value"; if (val != val) // NaN throw "Undefined Value"; bool sign = false; BigInt enumerator = 0; BigInt denominator = 1; if (val < 0) { val = -val; sign = true; } while (val > 0) { unsigned int intVal = (unsigned int)val; val -= intVal; enumerator += intVal; val *= 2; enumerator *= 2; denominator *= 2; } BigInt gcd = GCD(enumerator,denominator); enumerator /= gcd; denominator /= gcd; Print(sign? "-":"+"); Print(enumerator); Print("/"); Print(denominator); // Or simply return {sign,enumerator,denominator} as you wish }

Por cierto, GetRational (0.0) devolverá "+0/1", por lo que es posible que desee manejar este caso por separado.

PD: He estado usando este código en mi propia clase ''RationalNum'' durante varios años, y ha sido probado a fondo.

Ruby ya tiene una solución integrada:

0.33.rationalize.to_s # => "33/100" 0.4.rationalize.to_s # => "2/5"

En Rails, los atributos numéricos de ActiveRecord se pueden convertir también:

product.size = 0.33 product.size.to_r.to_s # => "33/100"

Si la salida es dar al lector humano una impresión rápida del orden del resultado, no tiene sentido devolver algo así como "113/211", por lo que la salida debería limitarse a usar números de un dígito (y tal vez 1 / 10 y 9/10). Si es así, puedes observar que solo hay 27 fracciones diferentes .

Dado que las operaciones matemáticas subyacentes para generar el resultado nunca cambiarán, una solución podría consistir simplemente en codificar un árbol de búsqueda binario, de modo que la función tenga un rendimiento máximo de log (27) ~ = 4 3/4 comparaciones. Aquí hay una versión C probada del código

char *userTextForDouble(double d, char *rval) { if (d == 0.0) return "0"; // TODO: negative numbers:if (d < 0.0)... if (d >= 1.0) sprintf(rval, "%.0f ", floor(d)); d = d-floor(d); // now only the fractional part is left if (d == 0.0) return rval; if( d < 0.47 ) { if( d < 0.25 ) { if( d < 0.16 ) { if( d < 0.12 ) // Note: fixed from .13 { if( d < 0.11 ) strcat(rval, "1/10"); // .1 else strcat(rval, "1/9"); // .1111.... } else // d >= .12 { if( d < 0.14 ) strcat(rval, "1/8"); // .125 else strcat(rval, "1/7"); // .1428... } } else // d >= .16 { if( d < 0.19 ) { strcat(rval, "1/6"); // .1666... } else // d > .19 { if( d < 0.22 ) strcat(rval, "1/5"); // .2 else strcat(rval, "2/9"); // .2222... } } } else // d >= .25 { if( d < 0.37 ) // Note: fixed from .38 { if( d < 0.28 ) // Note: fixed from .29 { strcat(rval, "1/4"); // .25 } else // d >=.28 { if( d < 0.31 ) strcat(rval, "2/7"); // .2857... else strcat(rval, "1/3"); // .3333... } } else // d >= .37 { if( d < 0.42 ) // Note: fixed from .43 { if( d < 0.40 ) strcat(rval, "3/8"); // .375 else strcat(rval, "2/5"); // .4 } else // d >= .42 { if( d < 0.44 ) strcat(rval, "3/7"); // .4285... else strcat(rval, "4/9"); // .4444... } } } } else { if( d < 0.71 ) { if( d < 0.60 ) { if( d < 0.55 ) // Note: fixed from .56 { strcat(rval, "1/2"); // .5 } else // d >= .55 { if( d < 0.57 ) strcat(rval, "5/9"); // .5555... else strcat(rval, "4/7"); // .5714 } } else // d >= .6 { if( d < 0.62 ) // Note: Fixed from .63 { strcat(rval, "3/5"); // .6 } else // d >= .62 { if( d < 0.66 ) strcat(rval, "5/8"); // .625 else strcat(rval, "2/3"); // .6666... } } } else { if( d < 0.80 ) { if( d < 0.74 ) { strcat(rval, "5/7"); // .7142... } else // d >= .74 { if(d < 0.77 ) // Note: fixed from .78 strcat(rval, "3/4"); // .75 else strcat(rval, "7/9"); // .7777... } } else // d >= .8 { if( d < 0.85 ) // Note: fixed from .86 { if( d < 0.83 ) strcat(rval, "4/5"); // .8 else strcat(rval, "5/6"); // .8333... } else // d >= .85 { if( d < 0.87 ) // Note: fixed from .88 { strcat(rval, "6/7"); // .8571 } else // d >= .87 { if( d < 0.88 ) // Note: fixed from .89 { strcat(rval, "7/8"); // .875 } else // d >= .88 { if( d < 0.90 ) strcat(rval, "8/9"); // .8888... else strcat(rval, "9/10"); // .9 } } } } } } return rval; }

Tendrá que averiguar qué nivel de error está dispuesto a aceptar. No todas las fracciones decimales se reducirán a una fracción simple. Probablemente escogería un número fácilmente divisible, como 60, y descubriría cuántos 60tos están más cerca del valor, luego simplificaría la fracción.

Tendrás dos problemas básicos que lo harán difícil:

1) El punto flotante no es una representación exacta, lo que significa que si tienes una fracción de "x / y" que da como resultado un valor de "z", tu algoritmo de fracción puede devolver un resultado que no sea "x / y".

2) Hay infinitos muchos más números irracionales que racionales. Un número racional es uno que se puede representar como una fracción. Irracionales siendo los que no pueden.

Sin embargo, de una forma barata, dado que el punto flotante tiene una precisión límite, entonces siempre puedes representarlo como una forma de facción. (Creo...)

Una solución es simplemente almacenar todos los números como números racionales en primer lugar. Hay bibliotecas para la aritmética de números racionales (por ejemplo, GMP ). Si utiliza un idioma OO, puede usar una biblioteca de clases de números racionales para reemplazar su clase numérica.

Los programas de finanzas, entre otros, usarían una solución de este tipo para poder hacer cálculos exactos y preservar la precisión que se puede perder usando un flotador simple.

Por supuesto, será mucho más lento, por lo que puede no ser práctico para usted. Depende de la cantidad de cálculos que necesita hacer y de la importancia de la precisión para usted.

a = rational(1); b = rational(3); c = a / b; print (c.asFraction) ---> "1/3" print (c.asFloat) ----> "0.333333"

Una solución incorporada en R:

library(MASS) fractions(0.666666666) ## [1] 2/3

Utiliza un método de fracción continua y tiene cycles opcionales y argumentos de max.denominator para ajustar la precisión.