小数到小数的转换

我在面试中遇到了以下问题：

将小数更改为最接近的分数的程序。

示例：0.12345=>2649/20000

0.34=>17/50

解决这个问题的最佳方法是什么？

我最近想到的一种方法是去掉小数：

0.12345=0.12345/1=12345/100000

然后找到最大公约数并将其除以。

十进制数是分母为10的幂的分数（对于任何基数也是如此）。因此0.34是34/100。现在只需取消公约数，即分子和分母除以它们的最大公约数。

你可以用标准算法找到GCD，我让你自己去找。

http://homepage.smc.edu/kennedy_john/DEC2FRAC.PDF

简而言之：

设X是我们的十进制值。Z₁=X、D₀==0和D_{1_==1。}

Z_i+1==1/（Z_i-IntPart（Z_i））

D_i+1=D_i*IntPart（Z_i+1）+D₁

N_i+1==圆形（X*D_i+1）

当算法发现，通过从定点Z₁迭代这些Z、D和N序列，该序列的索引i产生N_i和D_i，使得N_i/D_i=X，我们就完成了。如果存在最小误差（epsilon），在该误差范围内可以接受较低项近似，则该误差可以合并到工作分数与输入的比较中。

在满足该条件之前，序列Z跟踪十进制值的连续分数，并且算法使用该因子来增加分数的分母，直到获得足够的精度。

请理解，输入值最好存储为decimal类型，N/D的计算也应产生十进制类型，以避免浮点舍入误差。

解决方案：

public struct Fraction
{
    public int Numerator { get; private set; }
    public int Denominator { get; private set; }
    public Fraction(int num, int denom) 
    {
        Numerator = num;
        Denominator = denom;
    }
    public decimal DecimalValue 
    { 
        get { return ((decimal)Numerator) / Denominator; } 
    }
    public override string ToString()
    {
        return Numerator.ToString() + "/" + Denominator.ToString();
    }
    public static Fraction FromDecimal(decimal x, decimal epsilon = 0.0000001m)
    {
        decimal z = x;
        decimal dPrev = 0;
        decimal dCur = 1;
        decimal dTemp = dCur;
        decimal n = 0;
        while ((Math.Abs(n / dCur) - x) > epsilon)
        {
            z = 1 / (z - (int)z);
            dTemp = dCur;
            dCur = (dCur * (int)z) + dPrev;
            dPrev = dTemp;
            n = Math.Round(x * dCur);
        }
        return new Fraction((int) n, (int) dCur);
    }
}

该算法能够找到"；真"；由于精度限制而被人为终止的有理数的分数值（即3333333将是1/3，而不是3333333/1000）；它通过评估每个候选分数来产生一个值，该值将受到与输入相同的精度限制。它实际上取决于这一点；向该算法提供pi的真实值（如果可以的话）将导致无限循环。然而，当期望任意低的ε（包括零）时，这种行为在算法中造成了弱点；无理数的表示，或者不完全等于分数中固有除法产生的值的十进制值的表示，可能会产生意想不到的结果。

天真的解决方案。。

0.12345=12345/100000
求最大公约数
用GCD划分分数的两部分
利润

首先，通过连续乘以10使分子和分母积分。

因此，0.34/1变为34/100，0.12345/1变为12345/100000

然后使用GCD计算得到这两个数字的最大公约数，并将它们除以。

34和100的GCD是2，这是17/50。12345和1000000的GCD为5，即2469/20000。

C中的递归GCD函数是：

int gcd (int a, int b) {
    return (b == 0) ? a : gcd (b, a%b);
}

Kerrek SB的答案是正确的，但使用连续分数很容易找到任何实数（表示为浮点或非浮点）的最佳有理逼近，对于任何给定的最大分母。该方法的最佳性质如下所述：http://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems，定理4和5。

示例结果：分母小于或等于23的近似sqrt（2）：

findapprox(math.sqrt(2),23)
          (3, 2)  new error frac: 6.0660e-02 
          (7, 5)  new error frac: 1.0051e-02 
        (17, 12)  new error frac: 1.7346e-03 
        (41, 29)  new error frac: 2.9731e-04 
result: (17, 12)

示例：近似23.1234，分母<20000:

findapprox(23.1234,20000)
            (185, 8)  new error frac: 6.9194e-05 
          (1688, 73)  new error frac: 4.8578e-06 
          (1873, 81)  new error frac: 2.4560e-06 
         (3561, 154)  new error frac: 1.0110e-06 
         (5434, 235)  new error frac: 1.8403e-07 
        (19863, 859)  new error frac: 3.0207e-08 
       (25297, 1094)  new error frac: 1.5812e-08 
       (45160, 1953)  new error frac: 4.4287e-09 
       (70457, 3047)  new error frac: 2.8386e-09 
      (115617, 5000)  new error frac: 0.0000e+00 
result: (115617, 5000) (exact)

连分式有一些古怪的特点。例如，sqrt（2）可以写成1,2,2，，。。。意思是1+1/（2+1/（2+1/…）。所以我们可以找到sqrt（2）的最优有理逼近：

rewrap([1]+[2]*30) gives 367296043199 / 259717522849, 
all correct: 1.4142135623730951

这是代码（python）。

# make a+1/(b+1/(c+1/...)) cont fraction of a float
# no special care taken to accumulation of float truncation errors.
def contfrac(v):
    nums=None
    while nums==None or len(nums)<20:
        if not nums:
            nums=[]
        vi=int(v)
        v=v-vi
        nums.append(vi)
        if v<=0 : 
            return nums
        v=1.0/v
    return nums

# make tuple representing a rational number based on a cont f list 
# this is exact
def rewrap(v):
    rat=(0,1)
    first=1
    for k in reversed(v):
        if first:
            first=0
            rat=(k,1)
        else:            
            rat=(k*rat[0]+rat[1],rat[0])        
    return rat
# float evaluate a ratio
def makefloat(v):
    return v[0]*1.0/v[1]
# find the best rational approximation with denominator <=maxdenom
def findapprox(flt,maxdenom):
    flt=1.0*flt
    cf=contfrac(flt)
    best=(cf[0],1)
    errfrac=1e9
    for i in range(2,len(cf)):
        new=rewrap(cf[:i])        
        newerrfrac=abs((flt-makefloat(new))/flt)
        print "%20s"%(str(new)),
        print(" new error frac: %5.4e " %(newerrfrac))
        if new[1]>maxdenom or newerrfrac>errfrac:
            return best
        best=new
        errfrac=newerrfrac
        if newerrfrac ==0: 
            return best
    return best

首先，将数字转换为明显分数

0.34 => 34/100

和

0.12345 => 12345/100000

现在减少分数。你需要找到分子和分母的GCD。34和100的GDC是2。把两个数字都除以2，得到17/50。

请参阅维基百科上的最大公约数。你还可以在那里找到一个GCD算法的简要描述。

去掉点：（0.a₁..a_n*10ⁿ）/（1*10ⁿ.）
x=GCD（a₁.a_n，10ⁿ）
（a₁..a_n/x）/（10ⁿ/x

foo(double a) {
    int digits = (int)log(a, 10);
    int x = GCD((int)(a * 10^digits) , 10^digits);
    return ((int)(a * 10^digits) / x) + " / " + (10^digits / x);    
}

相关内容

最新更新

热门标签：