在给定的分子和分母范围内，找到与0..1之间的给定随机实数最接近的整数分数 [英] Finding the closest integer fraction to a given random real between 0..1, given ranges of numerator and denominator

问题描述

给定两个范围的正整数x: [1 ... n]和y: [1 ... m]以及从0到1的随机实数R，我需要从x和y中找到一对元素(i，j)，使得x_i/y_j最接近R.

Given two ranges of positive integers x: [1 ... n] and y: [1 ... m] and random real R from 0 to 1, I need to find the pair of elements (i,j) from x and y such that x_i / y_j is closest to R.

找到这对眼镜最有效的方法是什么?

What is the most efficient way to find this pair?

推荐答案

使用 Farey序列 .

1. 从a = 0，b = 1和A = {a和b与R的最接近值}开始.
2. 让c为a和b之间的下一个Farey分数，由c =(num(a)+ num(b))/(denom(a)+ denom(b))给出(确保除以num(c )和denom(c)通过gcd(num(c)，denom(c))):
3. 如果c的分子或分母超出您的输入范围，则输出A并停止.
4. 如果c比A更接近R，则将A设置为c.
5. 如果R在[a，c]中，则设置b = c，否则设置a = c.
6. 转到2.

1. Start with a = 0, b = 1 and A = {the closest of a and b to R}.
2. Let c be the next Farey fraction between a and b, given by c = (num(a) + num(b))/(denom(a) + denom(b)) (make sure to divide num(c) and denom(c) by gcd(num(c), denom(c))):
3. If c's numerator or denominator is out of your input range, output A and stop.
4. If c is closer to R than A, set A to c.
5. If R is in [a, c] set b = c, otherwise set a = c.
6. Go to 2.

这将找到O(1)空间中的最佳近似值，O(M)时间最坏情况和平均O(log M).

This finds the best approximation in O(1) space, O(M) time worst-case, and O(log M) on average.

这篇关于在给定的分子和分母范围内，找到与0..1之间的给定随机实数最接近的整数分数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！