Нахождение ближайшей целочисленной дроби к заданному случайному вещественному числу между 0..1, заданным диапазонам числителя и знаменателя

Question

Учитывая два диапазона положительных целых чисел x: [1 ... n] и y: [1 ... m] и случайное вещественное число R от 0 до 1, мне нужно найти пару элементов (i, j) из x и y, такую, чтобы x_i / y_j был ближе всего к R.

Какой самый эффективный способ найти эту пару?

Answer 1

Использование Последовательность Фарея .

1. Начните с a = 0, b = 1 и A = {ближайший из a и b к R}.
2. Пусть c - следующая дробь Фари между a и b, заданная как c = (num (a) + num (b)) / (denom (a) + denom (b)) (обязательно делите num (c) ) и denom (c) через gcd (num (c), denom (c))):
3. Если числитель или знаменатель c выходит за пределы диапазона ввода, выведите A и остановите.
4. Если c ближе к R, чем A, установите A на c.
5. Если R в [a, c], установить b = c, в противном случае установить a = c.
6. Перейти к 2.

Находит наилучшее приближение в пространстве O (1), наихудшем случае времени O (M) и в среднем O (log M).

Answer 2

Стандартным подходом к аппроксимации действительных чисел с помощью рациональных чисел является вычисление непрерывных рядов дробей (см. [1]).При вычислении частей ряда наложите ограничение на знаменатель и знаменатель, и последнее значение перед тем, как вы выйдете за пределы, является дробной частью, очень близкой к вашему действительному числу.

Это очень хорошее приближение очень быстро найдет,но я не уверен, что это всегда найдет самое близкое приближение.Известно, что

любой конвергент [частичное значение продолженного расширения фракции] ближе к непрерывной фракции, чем любая другая фракция, знаменатель которой меньше знаменателя

но могут быть приближения с большим знаменателем (все еще ниже вашего предела), которые являются лучшими приближениями, но не сходятся.

[1] http://en.wikipedia.org/wiki/Continued_fraction

Answer 3

Учитывая, что R является действительным числом таким, что 0 <= R <= 1, целые числа x: [1 ... n] и целые числа y: [1 ... m].Предполагается, что n <= m, так как если n > m, то x[n]/y[m] будет больше, чем 1, что не может быть ближайшим приближением к R.

Следовательно, наилучшее приближение R сзнаменатель d будет 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()

Answer 4

Вместо того, чтобы выполнять поиск методом полного перебора, выполните линейный поиск по самому короткому из ваших списков, используя раунд, чтобы найти лучшее соответствие для каждого элемента.Может быть, что-то вроде этого:

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)

Совершенно не уверен, будет ли "1004 *" оптимизация когда-либо быстрее ...

Answer 5

Решение: Вы можете сделать это 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: когда я = 1:

Вы должны искать по нижеуказанным номерам: 1,1 / 2,1 / 3,1 / 4, ...., 1 / п Вы проверяете число с помощью (1,1 / cill (n / 2)) и (1 / floor (n / 2), 1 / n) и выполняете аналогичный двоичный поиск по нему, чтобы найти наименьшее.

Следует сделать это для цикла для всех предметов, поэтому будет выполнено м раз. и в каждый раз это занимает O (log (n)). эта функция может улучшаться по некоторым математическим правилам, но она будет сложной, я ее пропускаю.

Answer 6

Быстро получить пламя, но поиск может быть лучше, когда мы вычисляем все дробные значения для каждого из возможных значений. Таким образом, просто индексирование двумерного массива, индексированного через дробные части, с элементом массива, содержащим действительный эквивалент.Я предполагаю, что у нас есть отдельные части X и Y, так что это конечно, это не было бы наоборот ... Ах, да, фактическая часть поиска .... эмм reet ....