在给定的分子和分母范围内，找到与0..1之间的给定随机实数最接近的整数分数

一尘不染

在给定的分子和分母范围内，找到与0..1之间的给定随机实数最接近的整数分数

algorithm

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

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

阅读 288

收藏

2020-07-28

共1个答案

一尘不染

使用Farey序列。

从a = 0，b = 1和A = {a和b最接近R}开始。
令c为a和b之间的下一个Farey分数，由c =（num（a）+ num（b））/（denom（a）+ denom（b））给出（确保将num（c）和denom相除（c）通过gcd（num（c），denom（c）））：
如果c的分子或分母超出您的输入范围，则输出A并停止。
如果c比A更接近R，则将A设置为c。
如果R在[a，c]中，则将b = c，否则将a = c。
转到2。

这样可以在O（1）空间，O（M）时间最坏情况和O（log M）平均情况下找到最佳近似值。

2020-07-28