给定两个正整数范围x: [1 ... n]和y: [1 ... m]从 0 到 1 的随机实数 R，我需要从 x 和 y 中找到一对元素 (i,j)，使得 x_i / y_j 最接近 R。
找到这对最有效的方法是什么？
问问题
10721 次
7 回答
15
使用Farey 序列
这是一个简单且数学上漂亮的算法来解决这个问题：运行二进制搜索，在每次迭代中，下一个数字由中值公式（如下）给出。根据法雷数列的性质，该数是该区间内分母最小的数。因此，这个序列将始终收敛，并且永远不会“错过”一个有效的解决方案。
在伪代码中：
input: m, n, R
a_num = 0, a_denom = 1
b_num = 1, b_denom = 1
repeat:
-- interestingly c_num/c_denom is already in reduced form
c_num = a_num + b_num
c_denom = a_denom + b_denom
-- if the numbers are too big, return the closest of a and b
if c_num > n or c_denom > m then
if R - a_num/a_denom < b_num/b_denom - R then
return a_num, a_denom
else
return b_num, b_denom
-- adjust the interval:
if c_num/c_denom < R then
a_num = c_num, a_denom = c_denom
else
b_num = c_num, b_denom = c_denom
goto repeat
即使它的平均速度很快（我有根据的猜测它是O(log max(m,n))），但如果 R 接近分母小的分数，它仍然可能很慢。例如，找到1/1000000与 with的近似值m = n = 1000000将需要一百万次迭代。
于 2010-12-08T08:59:58.553 回答
6
用有理数逼近实数的标准方法是计算连分数级数（参见 [1]）。在计算部分系列时对提名者和分母设置一个限制，并且在您突破限制之前的最后一个值是非常接近您的实数的分数。
这将很快找到一个非常好的近似值，但我不确定这是否总能找到一个最接近的近似值。众所周知
任何收敛的[连分数展开的部分值]比分母小于收敛的任何其他分数更接近连分数
但可能存在具有较大分母（仍低于您的极限）的近似值，它们是更好的近似值，但不是收敛的。
于 2010-12-08T09:00:04.683 回答
1
鉴于 R 是一个实数，使得0 <= R <= 1, 整数x: [1 ... n]和整数y: [1 ... m]。假设n <= m, 因为 if n > mthenx[n]/y[m]将大于1, 这不能是最接近 的近似值R。
因此，分母为 d 的 R 的最佳近似值将是floor(R*d) / d或ceil(R*d) / d。
问题可以在O(m)时间和O(1)空间上解决（在Python中）：
from __future__ import division
from random import random
from math import floor
def fractionize(R, n, d):
error = abs(n/d - R)
return (n, d, error) # (numerator, denominator, absolute difference to R)
def better(a, b):
return a if a[2] < b[2] else b
def approximate(R, n, m):
best = (0, 1, R)
for d in xrange(1, m+1):
n1 = min(n, int(floor(R * d)))
n2 = min(n, n1 + 1) # ceil(R*d)
best = better(best, fractionize(R, n1, d))
best = better(best, fractionize(R, n2, d))
return best
if __name__ == '__main__':
def main():
R = random()
n = 30
m = 100
print R, approximate(R, n, m)
main()
于 2010-12-08T10:42:58.630 回答
0
Prolly 被激怒了，但是查找可能是最好的，我们计算每个可能值的所有小数值。因此，只需简单地索引通过小数部分索引的二维数组，数组元素包含实际等价物。我想我们有离散的 X 和 Y 部分，所以这是有限的，它不会反过来……啊，是的，实际的搜索部分……erm reet……
于 2010-12-08T08:54:07.167 回答
0
解决方案：您可以这样做O(1)空间和O(m log(n))时间：
无需创建任何列表进行搜索，
伪代码可能是错误的，但想法是这样的：
r: input number to search.
n,m: the ranges.
for (int i=1;i<=m;i++)
{
minVal = min(Search(i,1,n,r), minVal);
}
//x and y are start and end of array:
decimal Search(i,x,y,r)
{
if (i/x > r)
return i/x - r;
decimal middle1 = i/Cill((x+y)/2);
decimal middle2 = i/Roof((x+y)/2);
decimal dist = min(middle1,middle2)
decimal searchResult = 100000;
if( middle > r)
searchResult = Search (i, x, cill((x+y)/2),r)
else
searchResult = Search(i, roof((x+y)/2), y,r)
if (searchResult < dist)
dist = searchResult;
return dist;
}
查找索引作为读者的家庭作业。
描述：我想你可以通过代码理解这个想法，但是让我们跟踪一个 for 循环：当 i=1 时：
您应该在以下数字中搜索：1,1/2,1/3,1/4,....,1/n 您使用 (1,1/cill(n/2)) 和 (1/ floor(n/2), 1/n) 并对其进行类似的二进制搜索以找到最小的那个。
应该为所有项目执行此 for 循环，因此将在m时间完成。并且每次都需要 O(log(n))。这个函数可以通过一些数学规则来改进，但是会很复杂，我跳过它。
于 2010-12-08T08:58:52.473 回答
0
与其进行完全的蛮力搜索，不如对最短的列表进行线性搜索，使用 round 为每个元素找到最佳匹配。也许是这样的：
best_x,best_y=(1,1)
for x in 1...n:
y=max(1,min(m,round(x/R)))
#optional optimization (if you have a fast gcd)
if gcd(x,y)>1:
continue
if abs(R-x/y)<abs(R-bestx/besty):
best_x,best_y=(x,y)
return (best_x,best_y)
完全不确定gcd“优化”是否会更快......
于 2010-12-08T09:00:27.367 回答
0
如果分母R大于m则使用 Farey 方法（该方法实现的） ，Fraction.limit_denominator限制为m以获得小于else let的分数。使用, 要么你就完成了，要么让并重新运行 Farey 方法。a/bbma/b = Rb <= ma <= nM = math.ceil(n/R)
def approx2(a, b, n, m):
from math import ceil
from fractions import Fraction
R = Fraction(a, b)
if R < Fraction(1, m):
return 1, m
r = R.limit_denominator(m)
if r.numerator > n:
M = ceil(n/R)
r = R.limit_denominator(M)
return r.numerator, r.denominator
>>> approx2(113, 205, 50, 200)
(43, 78)
使用限制分母可能只运行一次 Farey 方法，min(ceil(n/R), m)但我不确定：
def approx(a, b, n, m):
from math import ceil
from fractions import Fraction
R = Fraction(a, b)
if R < Fraction(1, m):
return 1, m
r = R.limit_denominator(min(ceil(n/R), m))
return r.numerator, r.denominator
于 2021-06-28T20:16:46.927 回答