发现的最接近的整数部分,以一个给定的随机实 [英] Finding the closest integer fraction to a given random real
本文介绍了发现的最接近的整数部分,以一个给定的随机实的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
正整数x的给定两个范围:[1 ... n]和Y:[1 ...米]和0至1个随机真实R,我需要找到一对元件(I,J)从x和y,使得XI / YJ是最接近于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 xi / yj is closest to R.
什么是最有效的方式找到这对?
What is the most efficient way to find this pair?
推荐答案
使用法里数列。
- 启动与a = 0时,B = 1并且A = {最接近的a和b至R}。
- 设C是A和B之间的下一个法里部分,由C =(NUM(一)+ NUM(B))/(DENOM(一)+ DENOM(B))(请务必devide NUM(C给出)和DENOM(C)由GCD(NUM(C),DENOM(C)))。
- 如果C的分子或分母是你的输入电压范围,输出A和停止。
- 如果c是更接近于R比A,集合A到C。
- 如果R是在[A,C]集B = C,否则设置= C。
- 转至2。
这个发现在O(1)空间中的最佳逼近,O(M)的时间最坏的情况下,和O(M)的平均水平。
This finds the best approximation in O(1) space, O(M) time worst-case, and O(log M) on average.
这篇关于发现的最接近的整数部分,以一个给定的随机实的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文