Binäre Suche nach einem Bruch
Ich versuche eine Übung aus dem Buch Algorithmen aus Sedgewick zu lösen, die wie folgt lautet:
Entwickeln Sie eine Methode, die eine logarithmische Anzahl von Abfragen des Formulars verwendet. Ist die Anzahl kleiner als x? um eine rationale Zahl p / q zu finden, so dass 0 <p <q <N. Hinweis: Zwei Brüche mit Nennern kleiner als N können sich nicht um mehr als 1 / N ^ 2 unterscheiden.
Ich bin mir bewusst, dass das Intervall, in dem ich binäre Suche durchführen muss,] 0, 1 [ist, aber ich bin mir nicht sicher, wonach ich suchen soll und was N ist. Kann es mir bitte jemand erklären?
Antworten
Wenn Sie den Hinweis ignorieren, finden Sie hier eine Lösung für ein viel schwierigeres Problem.
Finden Sie nämlich eine Rationalität durch binäre Suche mit einer logarithmischen Grenze, die an den absoluten Wert des Zählers / Nenners gebunden ist, ohne vorher zu wissen, wie groß diese ist.
Es ist eine binäre Suche des Stern-Brocot-Baums.
class GuessState:
def __init__ (self):
self.direction = None
self.start = [0, 1]
self.bound = [0, 0]
self.multiple_upper = 1
self.multiple_lower = 1
self.is_widening = True
self.is_choosing = None
def next_guess (self):
if self.is_widening:
multiple = self.multiple_upper
else:
multiple = (self.multiple_lower + self.multiple_upper) // 2
return (self.start[0] + multiple * self.bound[0], self.start[1] + multiple * self.bound[1])
def add_response (self, response):
next_level = False
if self.direction is None:
if 0 < response:
self.bound[0] = 1
self.direction = 1
else:
self.bound[0] = -1
self.direction = -1
self.is_choosing = True
return
elif self.is_choosing:
if self.direction * response < 0:
# Reverse direction.
self.direction = - self.direction
(self.start, self.bound) = (self.bound, self.start)
self.multiple_upper = 2
self.is_choosing = False
elif self.is_widening:
if 0 < response * self.direction:
self.multiple_lower = self.multiple_upper
self.multiple_upper += self.multiple_upper
else:
self.is_widening = False
if self.multiple_lower + 1 == self.multiple_upper:
next_level = True
elif self.multiple_lower + 1 < self.multiple_upper:
if 0 < self.direction * response:
self.multiple_lower = (self.multiple_lower + self.multiple_upper) // 2
else:
self.multiple_upper = (self.multiple_lower + self.multiple_upper) // 2
else:
next_level = True
if next_level:
next_start = (self.start[0] + self.multiple_lower * self.bound[0], self.start[1] + self.multiple_lower * self.bound[1])
next_bound = (self.start[0] + self.multiple_upper * self.bound[0], self.start[1] + self.multiple_upper * self.bound[1])
self.start = next_start
self.bound = next_bound
self.multiple_lower = 1
self.multiple_upper = 1
self.is_choosing = True
self.is_widening = True
def guesser (answerer):
state = GuessState()
response = answerer(state.next_guess())
while response != 0:
state.add_response(response)
response = answerer(state.next_guess())
return state.next_guess()
def answerer (answer):
def compare (guess):
val = guess[0] / guess[1]
print(f"Comparing answer {answer} to guess {val} ({guess[0]}/{guess[1]})")
if val < answer:
return 1
elif answer < val:
return -1
else:
return 0
return compare
print(guesser(answerer(0.124356)))