2010-10-14 687 views

回答

5

有一种算法叫做continued fraction algorithm,它会给你一定的意义上的“最佳”有理逼近。当分母超过9999时,可以停止,然后返回到前一个收敛,并比较它是否足够接近。当然,如果小数点是一个足够小的有理数,算法会提前终止。

2

所以,几件事情:

我认为用“十进制X”你指的是一些浮点表示X。也就是说,你打算以某种格式来实现这个功能,而这种格式实际上不能完全代表.1或1/3等。如果你是通过手工或其他方式来表达小数的方式,不适用。

其次,您是否与这些具体的分母和容差相关联?我问,因为如果你对2的幂是可以的(例如分母高达8192,容忍度为2^-35),你可以很容易地利用IEEE-754风格浮点都是有理数的事实。使用指数来确定尾数中的哪个数字对应于2^-13,然后确保尾数的后22位数字为0(或者如果精度不够高,以至于超过该点,则包括22),则最多为22。如果是这样,你就明白了。

现在,如果你不想改变你的算法来使用基2,你至少可以用它来缩小它,并做一些消除。

+0

这对3/7这样的东西有帮助吗? – 2010-10-14 02:17:29

+0

你已经指定你的输入是一个小数(并且我假定了一个有限长度),所以我不确定你的意思究竟是什么(因为3/7是一个重复小数,我想你可以运行它到一些数字的位数,然后测试) – Dusty 2010-10-14 02:44:47

+0

他的意思是0.4285714285714的输入应该返回3/7,因为它在3/7的10^-12之内。 – 2010-10-14 04:18:44

1

我看到你已经接受了一个答案,但我仍然要去响一声。

蛮力法不需要检查每个分母。如果你反向工作,不仅可以消除你刚刚检查的数字,而且可以消除每个因素。例如,一旦你检查了9999,你不需要检查3333,1111,909,303,101,99,33,11,9,3或1;如果数字可以表示为其中一个数字的一​​小部分,那么它也可以表示为9999的一小部分。结果是5000以下的每个数字至少是一个数字5000到9999的因数,所以您已经切割了你的搜索空间减半。

编辑︰我发现这个问题足够有趣的代码在Python解决方案。

def gcd(a, b): 
    if b == 0: 
     return a 
    return gcd(b, a % b) 

def simplify(fraction_tuple): 
    divisor = gcd(fraction_tuple[0], fraction_tuple[1]) 
    return fraction_tuple[0]/divisor, fraction_tuple[1]/divisor 

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False): 
    best_error, best_result = abs(value), (0,1) 
    for denominator in range(max_denominator/2+1, max_denominator+1): 
     numerator = round(value * denominator) 
     error = abs(value - (numerator/denominator)) 
     if error < best_error: 
      best_error = error 
      best_result = int(numerator), denominator 
      if error <= tolerance: 
       break 
    if enforce_tolerance and best_error > tolerance: 
     return None 
    return simplify(best_result)