[algorithm] float를 사람이 읽을 수있는 분수로 변환하는 방법은 무엇입니까?
을 가지고 있다고합시다 . 0.33출력해야합니다 1/3.
우리가 가지고 있다면 0.4, 우리는 출력해야합니다 2/5.
아이디어는 사용자가 데이터를 이해하는 더 나은 방법으로 ” x 부분 y “을 이해하도록 사람이 읽을 수 있도록 만드는 것입니다.
백분율이 좋은 대체물이라는 것을 알고 있지만 이렇게하는 간단한 방법이 있는지 궁금합니다.
답변
나는 David Eppstein의 주어진 실수 C 코드에 대한 합리적인 근사치를 찾는 것이 정확히 당신이 요구하는 것임을 발견했습니다. 연속 분수 이론을 기반으로하며 매우 빠르고 상당히 간결합니다.
특정 분자 및 분모 제한에 맞게 사용자 정의 된 버전을 사용했습니다.
/*
** 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]));
}
답변
Python 2.6부터는 fractions모듈이 있습니다.
(문서에서 인용.)
>>> 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)
답변
출력이 인간 독자에게 결과의 순서에 대한 빠른 인상을주는 것이라면 “113/211″과 같은 결과를 반환하는 것은 의미가 없으므로 출력은 한 자리 숫자를 사용하는 것으로 제한되어야합니다 (1 / 10 및 9/10). 그렇다면, 당신은 단지 27가 있음을 관찰 할 수있는 다른 분수.
출력을 생성하는 기본 수학은 절대 변경되지 않으므로 해결책은 이진 검색 트리를 간단히 하드 코딩하여 함수가 최대 log (27) ~ = 4 3/4 비교를 수행하도록하는 것입니다. 다음은 코드의 테스트 된 C 버전입니다.
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;
}
답변
다음은 소수를 분수로 변환하는 수학을 설명하는 링크입니다.
http://www.webmath.com/dec2fract.html
다음은 VB를 사용하여 실제로 수행하는 방법에 대한 예제 함수입니다 (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
(Google 검색에서 : 소수를 분수로 변환, 소수를 분수 코드로 변환)
답변
모든 컴퓨터 과학자가 부동 소수점 산술에 대해 알아야 할 사항 을 읽고 싶을 수 있습니다 .
큰 수를 곱하여 정밀도를 지정해야합니다.
3.141592 * 1000000 = 3141592
그런 다음 분수를 만들 수 있습니다.
3 + (141592 / 1000000)
GCD를 통해 줄이기 …
3 + (17699 / 125000)
그러나 의도 한 분수 를 얻을 수있는 방법은 없습니다 . 대신 코드 전체 에서 항상 분수를 사용 하고 싶을 수 있습니다 . 오버플로를 방지 할 수있을 때 분수를 줄이는 것을 잊지 마십시오!
답변
다음은 devinmoore가 제안한 VB 코드의 Perl 및 Javascript 버전입니다.
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";
}
그리고 거의 동일한 자바 스크립트 :
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;
}
답변
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://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);
}
}