二进制搜索分数 [英] Binary search for a fraction

问题描述

我正在尝试解决Sedgewick的《算法》一书中的一个练习，内容如下:

I'm trying to solve an exercise from the book Algorithms from Sedgewick that goes as follows:

设计一个使用对数形式的查询的方法，该数量是否小于x?找出有理数p/q，使得0 ＜0.p ＜q ＜N.提示:分母小于N的两个分数之差不能超过1/N ^ 2.

Devise a method that uses a logarithmic number of queries of the form Is the number less than x? to find a rational number p/q such that 0 < p < q < N. Hint : Two fractions with denominators less than N cannot differ by more than 1/N^2.

我知道我必须进行二分搜索的间隔是[0，1]，但是我不确定我应该看什么，什么是N.有人可以给我解释一下吗?

I'm aware that the interval in which I have to Binary Search is ]0, 1[ but I'm not sure of what I should be looking and what N is. Can somebody please explain it to me?

推荐答案

忽略提示，这是一个更棘手的问题的解决方案.

Ignoring the hint, here is a solution to a much harder problem.

通过二进制搜索找到 any 有理数，在分子/分母的绝对值上有对数界，而无需事先知道它有多大.

Namely find any rational by binary search, with a logarithmic bound on the absolute value of the numerator/denominator, without knowing in advance how big that is.

这是对斯特恩-布罗科树的二进制搜索.

It is a binary search of the Stern-Brocot tree.

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

这篇关于二进制搜索分数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！