给定两个正整数范围x：[1 ... n]和y：[1 ... m]和从0到1的随机实数R，我需要找到x和x的元素对（i，j） y使得xi / yj最接近R.
找到这对的最有效方法是什么？
给定两个正整数范围x：[1 ... n]和y：[1 ... m]和从0到1的随机实数R，我需要找到x和x的元素对（i，j） y使得xi / yj最接近R.
找到这对的最有效方法是什么？
使用 Farey序列。
这在O（1）空间，O（M）时间最差情况和O（log M）平均值中找到最佳近似值。
用有理数逼近实数的标准方法是计算 继续分数系列 （见[1]）。在计算系列的部分时限制分母和分母，并且在打破限制之前的最后一个值是非常接近实数的分数。
这将非常快速地找到非常好的近似值，但我不确定这总是会找到最接近的近似值。众所周知
任何收敛[连续分数展开的部分值]比分数小于收敛分数的任何其他分数更接近连续分数
但是可能存在较大分母（仍然低于极限）的近似值，这些近似值是更好的近似值，但不是收敛值。
鉴于R是一个实数，这样 0 <= R <= 1，整数 x: [1 ... n] 和整数 y: [1 ... m]。假设是 n <= m，因为如果 n > m 然后 x[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()
Prolly变得火热，但是在我们计算每个可能值的所有小数值时查找可能是最好的。因此，简单地索引通过小数部分索引的2d数组，其中数组元素包含实际等价物。我想我们有离散的X和Y部分所以这是有限的，它不会是相反的方式....啊，是的，实际的搜索部分....呃reet ....
而不是完全强力搜索，在最短的列表上进行线性搜索，使用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 “优化”将更快......
解决方案： 你可以这样做 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）检查数字并对其进行类似的二元搜索以找到最小的数字。
应该为所有项目执行此循环，因此它将完成 米 时间。并且每次都需要O（log（n））。这个函数可以通过一些数学规则来改进，但它会很复杂，我跳过它。