Ermittlung des nächstgelegenen ganzzahligen Bruchs zu einem gegebenen zufälligen reellen Wert zwischen 0..1 bei gegebenen Bereichen von Zähler und Nenner

Question

Gegeben sind zwei Bereiche positiver ganzer Zahlen x: [1 ... n] y y: [1 ... m] und einem zufälligen reellen Wert R von 0 bis 1 muss ich das Paar von Elementen (i,j) aus x und y finden, so dass x_i / y_j am nächsten an R liegt.

Wie kann ich dieses Paar am effizientesten finden?

Answer 1

Führen Sie eine lineare Suche über die kürzeste Ihrer Listen durch und verwenden Sie round, um die beste Übereinstimmung für jedes Element zu finden. Vielleicht so etwas wie dies:

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)

Ich bin mir nicht sicher, ob die gcd "Optimierung" wird immer schneller sein...

Answer 2

Wenn der Nenner von R größer ist als m dann die Farey-Methode anwenden (die die Fraction.limit_denominator Methode implementiert) mit einer Grenze von m um einen Bruch zu erhalten a/b donde b kleiner ist als m sonst lassen a/b = R . Mit b <= m entweder a <= n und Sie sind fertig, oder lassen Sie M = math.ceil(n/R) und führen Sie die Farey-Methode erneut durch.

def approx2(a, b, n, m):
    from math import ceil
    from fractions import Fraction
    R = Fraction(a, b)
    if R < Fraction(1, m):
        return 1, m
    r = R.limit_denominator(m)
    if r.numerator > n:
        M = ceil(n/R)
        r = R.limit_denominator(M)
    return r.numerator, r.denominator

>>> approx2(113, 205, 50, 200)
(43, 78)

Es könnte möglich sein, die Farey-Methode nur einmal durchzuführen und dabei einen begrenzten Nenner von min(ceil(n/R), m) aber ich bin mir da nicht sicher:

def approx(a, b, n, m):
    from math import ceil
    from fractions import Fraction
    R = Fraction(a, b)
    if R < Fraction(1, m):
        return 1, m
    r = R.limit_denominator(min(ceil(n/R), m))
    return r.numerator, r.denominator