Binäre Suche nach einem Bruch

Nov 24 2020

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

btilly Nov 25 2020 at 16:48

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)))