Comment convertir des flottants en fractions lisibles par l'homme ?
https://stackoverflow.com/questions/95727
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Disons que nous avons 0,33, nous devons sortir "1/3".
Si nous avons "0,4", nous devons afficher "2/5".
L'idée est de le rendre lisible par l'homme pour que l'utilisateur comprenne « x parties sur y » comme une meilleure façon de comprendre les données.
Je sais que les pourcentages sont un bon substitut mais je me demandais s'il existait un moyen simple de procéder ?
La solution
J'ai trouvé la approximation rationnelle d'un nombre réel donné par David Eppstein C code pour être exactement ce que vous demandez. Son basé sur la théorie des fractions continues et très rapide et assez compact.
J'ai utilisé des versions de cet outil personnalisées pour des limites de numérateur et de dénominateur spécifiques.
/*
** 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]));
}
Autres conseils
À partir de Python 2.6, le module fractions est disponible.
(Citations tirées de la documentation.)
>>> 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)
Si la sortie doit donner au lecteur humain une impression rapide de l'ordre du résultat, cela n'a aucun sens de renvoyer quelque chose comme & 113/211 & ";, donc la sortie doit se limiter utiliser des nombres à un chiffre (et peut-être 1/10 et 9/10). Si tel est le cas, vous pouvez constater qu’il n’ya que 27 fractions différentes .
Etant donné que le calcul sous-jacent pour la génération de la sortie ne changera jamais, une solution pourrait consister à simplement coder en dur un arbre de recherche binaire, afin que la fonction effectue au maximum les comparaisons log (27) ~ = 4 3/4. Voici une version C testée du code
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;
}
Voici un lien expliquant le calcul effectué pour convertir un nombre décimal en fraction:
http://www.webmath.com/dec2fract.html
Et voici un exemple de fonction expliquant comment le faire en utilisant VB (à partir de 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
(à partir des recherches Google: convertir le nombre décimal en fraction, convertir le nombre décimal en code de fraction)
Vous voudrez peut-être lire Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante .
Vous devrez spécifier une précision en multipliant par un grand nombre:
3.141592 * 1000000 = 3141592
alors vous pouvez faire une fraction:
3 + (141592 / 1000000)
et réduisez via GCD ...
3 + (17699 / 125000)
mais il n'y a aucun moyen d'extraire la fraction prévue . Vous voudrez peut-être toujours utiliser des fractions dans tout votre code - rappelez-vous simplement de réduire les fractions lorsque vous le pouvez pour éviter les débordements!
Voici les versions Perl et Javascript du code VB suggéré par 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";
}
Et le javascript presque identique:
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;
}
Une implémentation C #
/// <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://stackoverflow.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);
}
}
L’S arbre de Stern-Brocot induit un moyen assez naturel de se rapprocher des nombres réels par fractions. avec des dénominateurs simples.
Une partie du problème est que tant de fractions ne sont pas réellement faciles à interpréter comme des fractions. Par exemple. 0,33 n'est pas 1/3, c'est 33/100. Mais si vous vous souvenez de votre formation au primaire, vous pouvez convertir les valeurs décimales en fractions. Toutefois, il est peu probable que vous obteniez ce que vous voulez, car la plupart du temps, les nombres décimaux ne sont pas stockés à 0,33, mais à 0,329999999999998.
Faites-vous une faveur et ne vous embêtez pas là-dessus, mais si vous en avez besoin, vous pouvez procéder comme suit:
Multipliez la valeur d'origine par 10 jusqu'à ce que vous supprimiez la partie décimale. Conservez ce nombre et utilisez-le comme diviseur. Faites ensuite une série de simplifications en recherchant des dénominateurs communs.
Donc 0.4 serait 4/10. Vous devriez alors rechercher des diviseurs communs commençant par des valeurs faibles, probablement des nombres premiers. En commençant par 2, vous verriez si 2 divise le numérateur et le dénominateur de manière égale en vérifiant si le plancher de la division est identique à la division elle-même.
floor(5/2) = 2
5/2 = 2.5
Donc 5 ne divise pas 2 de manière égale. Alors, vous vérifiez le nombre suivant, par exemple 3. Vous le faites jusqu'à ce que vous atteigniez ou dépassiez la racine carrée du nombre plus petit.
Après cela, il vous faut
Ce n'est pas un "ient "algorithme &", mais juste une solution Python: http://docs.python.org/library/fractions.html
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)
& "; Disons que nous avons 0,33, nous devons générer &" 1/3 & "; "
Quelle précision attendez-vous de la " solution " avoir? 0,33 n'est pas égal à 1/3. Comment reconnaissez-vous un & "Bon &"; (facile à lire) répondre?
Quoi qu’il en soit, un algorithme possible pourrait être:
Si vous vous attendez à trouver la fraction la plus proche sous une forme X / Y où Y est inférieur à 10, vous pouvez alors boucler les 9 Y possibles, pour chaque Y calculer X, puis sélectionner celle qui est la plus précise.
Une solution intégrée à R:
library(MASS)
fractions(0.666666666)
## [1] 2/3
Ceci utilise une méthode de fraction continue et possède des arguments facultatifs cycles et max.denominator pour ajuster la précision.
Vous devrez déterminer le niveau d'erreur que vous êtes prêt à accepter. Toutes les fractions décimales ne seront pas réduites à une simple fraction. Je choisirais probablement un nombre facilement divisible, comme 60, et déterminerais le nombre de 60ièmes se rapprochant le plus de la valeur, puis simplifierais la fraction.
Vous pouvez le faire dans n’importe quel langage de programmation en procédant comme suit:
- Multipliez et divisez par 10 ^ x, où x est la puissance de 10 requise pour vous assurer qu'il ne reste aucune décimale dans le nombre. Exemple: Multipliez 0,33 par 10 ^ 2 = 100 pour le transformer en 33 et divisez-le par le même résultat pour obtenir 33/100
- Réduisez le numérateur et le dénominateur de la fraction résultante par factorisation jusqu'à ce que vous ne puissiez plus obtenir les entiers du résultat.
- La fraction réduite obtenue devrait être votre réponse.
Exemple: 0,2 = 0,2 x 10 ^ 1/10 ^ 1 = 2/10 = 1/5
Donc, cela peut être lu comme "1 partie sur 5"
Une solution consiste à stocker tous les nombres sous forme de nombres rationnels. Il existe des bibliothèques pour l'arithmétique des nombres rationnels (par exemple, GMP ). Si vous utilisez un langage OO, vous pourrez peut-être simplement utiliser une bibliothèque de classes de nombres rationnelles pour remplacer votre classe de nombres.
Les programmes financiers, entre autres, utiliseraient une telle solution pour pouvoir effectuer des calculs exacts et préserver la précision qui pourrait être perdue à l’aide d’un simple flotteur.
Bien sûr, ce sera beaucoup plus lent, donc ce ne sera peut-être pas pratique pour vous. Cela dépend du nombre de calculs que vous devez effectuer et de l’importance de la précision pour vous.
a = rational(1);
b = rational(3);
c = a / b;
print (c.asFraction) ---> "1/3"
print (c.asFloat) ----> "0.333333"
Je pense que la meilleure façon de faire est de convertir d’abord votre valeur float en une représentation ascii. En C ++, vous pouvez utiliser ostringstream ou en C, vous pouvez utiliser sprintf. Voici à quoi cela ressemblerait 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;
Une approche similaire pourrait être adoptée dans le segment C.
Ensuite, vous devrez vérifier que la fraction est au plus bas. Cet algorithme donnera une réponse précise, c’est-à-dire que 0,33 afficherait & 33; 33/100 & ", Pas &"; 1/3. & "; Cependant, 0.4 donnerait & Quot; 4/10, & Quot; qui, une fois réduits au minimum, serait " 2/5. " Cela n’est peut-être pas aussi puissant que la solution d’EppStein, mais j’estime que cela est plus simple.
Ruby a déjà une solution intégrée:
0.33.rationalize.to_s # => "33/100"
0.4.rationalize.to_s # => "2/5"
Dans Rails, les attributs numériques ActiveRecord peuvent également être convertis:
product.size = 0.33
product.size.to_r.to_s # => "33/100"
Répondez en C ++, en supposant que vous avez une classe 'BigInt', qui peut stocker des entiers de taille illimitée.
Vous pouvez utiliser 'unsigned long long' à la place, mais cela ne fonctionnera que pour certaines valeurs.
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
}
BTW, GetRational (0.0) renverra " +0/1 " ;, de sorte que vous voudrez peut-être traiter ce cas séparément.
P.S .: J'utilise ce code dans ma propre classe 'RationalNum' depuis plusieurs années et il a été testé de manière approfondie.
Cet algorithme par Ian Richards / John Kennedy non seulement renvoie de belles fractions, mais il est également très performant en termes de rapidité. C’est le code C # tiré de cette réponse de ma part.
Il peut gérer toutes les double valeurs sauf les valeurs spéciales comme NaN et +/- infinity, que vous devrez ajouter si nécessaire.
Il retourne un new Fraction(numerator, denominator). Remplacez-le par votre propre type.
Pour plus d'exemples de valeurs et une comparaison avec d'autres algorithmes, cliquez ici
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);
}
Exemple de valeurs renvoyées par cet algorithme:
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
Vous allez avoir deux problèmes de base qui compliqueront la tâche:
1) Le point flottant n'est pas une représentation exacte, ce qui signifie que si vous avez une fraction de & «x / y &»; qui donne une valeur de " z " ;, votre algorithme de fraction peut renvoyer un résultat autre que " x / y ".
2) Il existe à l'infini beaucoup plus de nombres irrationnels que rationnels. Un nombre rationnel est un nombre qui peut être représenté sous forme de fraction. Les êtres irrationnels qui ne peuvent pas.
Cependant, de manière peu coûteuse, comme la virgule flottante a une précision limite, vous pouvez toujours la représenter comme une sorte de faction. (Je pense ...)
Terminé le code ci-dessus et l'a converti 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";
}
Disons que nous avons 0,33, nous devons générer & «1/3 &»; Si nous avons & Quot; 0.4 & Quot ;, nous besoin de générer & "; 2/5 &";.
C'est faux dans le cas commun, à cause de 1/3 = 0.3333333 = 0. (3) De plus, il est impossible de déterminer avec les solutions ci-dessus si son nombre décimal peut être converti en fraction avec une précision définie, car le résultat est toujours une fraction.
MAIS, je suggère ma fonction complète avec de nombreuses options basées sur l'idée de Série géométrique infinie , spécifiquement sur la formule:
Au début, cette fonction essaie de trouver une période de fraction dans la représentation sous forme de chaîne. Après l’application de la formule décrite ci-dessus.
Le code des nombres rationnels est emprunté à Stephen M. McKamey implémentation des nombres rationnels en C #. J'espère qu'il n'est pas très difficile de transférer mon code dans d'autres langues.
/// <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;
}
Il y a quelques exemples d'utilisation:
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;
Votre cas avec le rognage de la partie zéro de la partie droite:
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;
Démonstration de la période minimale:
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.
Arrondi à la fin:
Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r));
// then r == 8 == 9;
Le cas le plus intéressant:
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.
D'autres tests et codes que tout le monde peut trouver dans ma bibliothèque MathFunctions sur github .
Voici une implémentation rapide et incorrecte en javascript qui utilise une approche de force brute. Pas du tout optimisé, il fonctionne dans une plage de fractions prédéfinie: 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));
Ceci est inspiré de l'approche utilisée par JPS.
Comme beaucoup de gens l’ont dit, vous ne pouvez vraiment pas reconvertir une virgule flottante en fraction (à moins que son extrême soit exactement égal à 0,25). Bien sûr, vous pouvez créer un type de recherche pour un grand nombre de fractions et utiliser une sorte de logique floue pour produire le résultat que vous recherchez. Encore une fois, cela ne serait pas exact et vous auriez besoin de définir une limite inférieure de la taille de votre dénominateur.
.32 < x < .34 = 1/3 ou quelque chose comme ça.
Voici l'implémentation pour 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)
Je suis tombé sur une solution Haskell particulièrement élégante utilisant un anamorphisme. Cela dépend du package récursion-schémas .
{-# 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 vous essayez ceci en ghci, ça marche vraiment!
λ:> approximate pi 2
22 % 7
