Игра "угадай число" для произвольных рациональных чисел?

возьмем рациональные числа, в уменьшенном виде, и запишем их в порядке сначала знаменателя, затем числителя.

1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, ...

наша первая догадка будет 1/2. Затем мы будем идти по списку, пока у нас не будет 3 в нашем диапазоне. Затем мы возьмем 2 догадки для поиска этого списка. Затем мы будем идти по списку, пока у нас не будет 7 в нашем оставшемся диапазоне. Затем мы возьмем 3 догадки для поиска в этом списке. И так далее.

на n шаги мы рассмотрим первые 2O(n) возможности, которые находятся в порядке величины эффективности, которую вы искали.

обновление: люди не поняли причины этого. Рассуждения просты. Мы знаем, как эффективно ходить по двоичному дереву. Есть O(n2) дроби с максимальным знаменателем n. Поэтому мы могли бы искать до любого конкретного размера знаменателя в O(2*log(n)) = O(log(n)) действия. Проблема в том, что у нас есть бесконечное число возможных рациональных решений для поиска. Так мы не можем просто выстроить их всех, заказать и начать поиск.

поэтому моя идея состояла в том, чтобы выстроить несколько, поиск, выстроить больше, поиск и так далее. Каждый раз, когда мы выстраиваемся в очередь, мы выстраиваемся примерно вдвое больше, чем в прошлый раз. Так что нам нужно еще одно предположение, чем в прошлый раз. Поэтому наш первый проход использует 1 догадку, чтобы пересечь 1 возможный рациональный. Наш второй использует 2 догадки для пересечения 3 возможных рациональных значений. Наш третий использует 3 догадки, чтобы пересечь 7 возможных рациональных значений. И наши k ' th использует k догадки, чтобы пересечь 2k-1 возможные рациональные объяснения. Для любого конкретного рационального m/n, в конечном итоге это приведет к тому, что rational будет помещен в довольно большой список, который он знает, как эффективно выполнять двоичный поиск.

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

мы на самом деле делать намного лучше, чем это. С нашей первой догадкой мы исключаем половину рационалов из нашего списка как слишком большие или маленькие. Наши следующие две догадки не совсем разрезают пространство на четверти, но они не слишком далеко от него. Наши следующие 3 догадки снова не совсем разрезают пространство на восьмые, но они не слишком далеко от него. И так далее. Когда вы складываете его вместе, я убежден, что в результате вы найдете m/n на O(log(n)) действия. Хотя на самом деле у меня нет доказательств.

попробуйте: вот код для генерации догадок, так что вы можете играть и посмотреть, насколько это эффективно.

#! /usr/bin/python

from fractions import Fraction
import heapq
import readline
import sys

def generate_next_guesses (low, high, limit):
    upcoming = [(low.denominator + high.denominator,
                 low.numerator + high.numerator,
                 low.denominator, low.numerator,
                 high.denominator, high.numerator)]
    guesses = []
    while len(guesses) < limit:
        (mid_d, mid_n, low_d, low_n, high_d, high_n) = upcoming[0]
        guesses.append(Fraction(mid_n, mid_d))
        heapq.heappushpop(upcoming, (low_d + mid_d, low_n + mid_n,
                                     low_d, low_n, mid_d, mid_n))
        heapq.heappush(upcoming, (mid_d + high_d, mid_n + high_n,
                                  mid_d, mid_n, high_d, high_n))
    guesses.sort()
    return guesses

def ask (num):
    while True:
        print "Next guess: {0} ({1})".format(num, float(num))
        if 1 < len(sys.argv):
            wanted = Fraction(sys.argv[1])
            if wanted < num:
                print "too high"
                return 1
            elif num < wanted:
                print "too low"
                return -1
            else:
                print "correct"
                return 0

        answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ")
        if answer == "h":
            return 1
        elif answer == "l":
            return -1
        elif answer == "c":
            return 0
        else:
            print "Not understood.  Please say one of (l, c, h)"

guess_size_bound = 2
low = Fraction(0)
high = Fraction(1)
guesses = [Fraction(1,2)]
required_guesses = 0
answer = -1
while 0 != answer:
    if 0 == len(guesses):
        guess_size_bound *= 2
        guesses = generate_next_guesses(low, high, guess_size_bound - 1)
    #print (low, high, guesses)
    guess = guesses[len(guesses)/2]
    answer = ask(guess)
    required_guesses += 1
    if 0 == answer:
        print "Thanks for playing!"
        print "I needed %d guesses" % required_guesses
    elif 1 == answer:
        high = guess
        guesses[len(guesses)/2:] = []
    else:
        low = guess
        guesses[0:len(guesses)/2 + 1] = []

в качестве примера, чтобы попробовать его я попробовал 101/1024 (0.0986328125) и обнаружил, что потребовалось 20 догадок, чтобы найти ответ. Я попробовал 0.98765 и это заняло 45 гадает. Я попробовал 0.0123456789 и ему понадобилось 66 догадок и около секунды, чтобы сгенерировать их. (Обратите внимание, если вы вызываете программу с рациональным числом в качестве аргумента, она заполнит все догадки для вас. Это очень полезное удобство.)

Я понял! Что вам нужно сделать, это использовать параллельный поиск с разделением пополам и продолжение фракций.

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

как вы запускаете их параллельно следующим образом.

на каждом шагу у вас есть l и u будучи нижней и верхней границами бисекция. Идея заключается в том, что у вас есть выбор между разделением пополам диапазона деления пополам и добавлением дополнительного члена в виде представления непрерывной дроби. Когда оба l и u имеют тот же следующий термин, что и непрерывная дробь, затем вы делаете следующий шаг в поиске непрерывной дроби и делаете запрос с использованием непрерывной дроби. В противном случае вы делите диапазон пополам с помощью деления пополам.

так как оба метода увеличивают знаменатель по крайней мере на постоянный коэффициент (деление идет по факторам 2, непрерывные фракции идут по крайней мере на коэффициент phi = (1+sqrt(5))/2), это означает, что ваш поиск должен быть O(log(q)). (Могут быть повторены вычисления непрерывной дроби, поэтому он может закончиться как O(log(q)^2).)

наш непрерывный поиск фракций должен округляться до ближайшего целого числа, а не использовать пол (это более ясно ниже).

выше вид handwavy. Давайте воспользуемся конкретным примером r = 1/31:

1. l = 0, u = 1, запрос = 1/2. 0 не выражается как непрерывная дробь, поэтому мы используем двоичный поиск до l != 0.

2. l = 0, u = 1/2, запрос = 1/4.

3. l = 0, u = 1/4, запрос = 1/8.

4. l = 0, u = 1/8, запрос = 1/16.

5. l = 0, u = 1/16, запрос = 1/32.

6. l = 1/32, u = 1/16. Теперь 1 / l = 32, 1 / u = 16, они имеют разные cfrac повторения, поэтому продолжайте делить пополам., запрашивать = 3/64.

7. l = 1/32, u = 3/64, query = 5/128 = 1/25. 6

8. l = 1/32, u = 5/128, query = 9/256 = 1/28. 4444....

9. l = 1/32, u = 9/256, query = 17/512 = 1/30. 1176... (круглый 1/30)

10. l = 1/32, u = 17/512, запрос = 33/1024 = 1/31. 0303... (круг 1/31)

11. l = 33/1024, u = 17/512, запрос = 67/2048 = 1/30. 5672... (круглый к 1/31)

12. l = 33/1024, u = 67/2048. В этот момент и l, и u имеют один и тот же член непрерывной дроби 31, поэтому теперь мы используем предположение о непрерывной дроби. запрос = 1/31.

успехов!

для другого примера давайте использовать 16/113 (=355/113 - 3, где 355/113 довольно близко к pi).

[чтобы продолжить, я должен пойти куда-то]

---

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

Я думаю, что нашел алгоритм O(log^2(p + q)).

чтобы избежать путаницы в следующем абзаце, "запрос "относится к тому, когда гадатель дает претенденту догадку, и претендент отвечает" больше "или"меньше". Это позволяет мне зарезервировать слово "угадать" для чего-то еще, угадать для p + q, который не задается непосредственно претенденту.

идея состоит в том, чтобы сначала найти p + q, используя алгоритм, который вы описываете в своем вопросе: угадайте значение k, если k слишком мало, удвойте его и повторите попытку. Затем, когда у вас есть верхняя и нижняя граница, выполните стандартный двоичный поиск. Для этого требуется o(log (p+q)T) запросов, где T-верхняя граница количества запросов, необходимых для проверки предположения. Давайте найдем т.

мы хотим проверить все фракции r / s с r + s

мы никогда не угадаем значение k больше 2 (p + q). Следовательно, мы можем взять T = O(log (p+q)).

когда мы угадаем правильное значение для k (т. е. k = p + q), мы отправим запрос p/q претенденту в ходе проверки нашей догадки для k и выиграем игру.

общее количество запросов тогда O(log^2 (p + q)).

хорошо, я думаю, что я понял O (lg² Q) алгоритм для этой задачи, основанный на самом превосходном понимании Джейсона S об использовании непрерывных дробей. Я думал, что я бы конкретизировал алгоритм прямо здесь, чтобы у нас было полное решение, а также анализ времени выполнения.

интуиция алгоритма заключается в том, что любое рациональное число p/q в пределах диапазона может быть записано как

a₀ + 1 / (a₁ + 1 / (a₂ + 1 / (a₃ + 1 / ...))

для соответствующих вариантов a_Я. Это называется продолжение фракция. Что еще более важно, хотя эти_Я может быть получен путем выполнения евклидова алгоритма на числителе и знаменателе. Например, предположим, что мы хотим представить 11/14 таким образом. Начнем с того, что 14 переходит в одиннадцать нулевых раз, поэтому грубое приближение 11/14 будет будь

0 = 0

теперь предположим, что мы берем обратную часть этой дроби, чтобы получить 14/11 = 1 ³/₁₁. Так что если мы напишем

0 + (1 / 1) = 1

мы получаем немного лучшее приближение к 11/14. Теперь, когда у нас осталось 3/11, мы можем снова взять взаимное, чтобы получить 11/3 = 3 ²/₃, так что мы можем рассмотреть

0 + (1 / (1 + 1/3)) = 3/4

Что является еще одним хорошим приближением 11/14. Теперь у нас есть 2/3, поэтому рассмотрим обратную величину, которая равна 3/2 = 1 ¹/₂. Если мы пишем

0 + (1 / (1 + 1/(3 + 1/1))) = 5/6

мы получаем еще одно хорошее приближение к 11/14. Наконец, мы остаемся с 1/2, взаимное значение которого равно 2/1. Если мы, наконец, написать

0 + (1 / (1 + 1/(3 + 1/(1 + 1/2)))) = (1 / (1 + 1/(3 + 1/(3/2)))) = (1 / (1 + 1/(3 + 2/3)))) = (1 / (1 + 1/(11/3)))) = (1 / (1 + 3/11)) = 1 / (14/11) = 11/14

Это именно та фракция, которую мы хотели. Кроме того, посмотрите на последовательность коэффициентов, которые мы в конечном итоге использовали. Если вы запустите расширенный евклидов алгоритм на 11 и 14, вы получите это

11 = 0 x 14 + 11 --> a0 = 0 14 = 1 x 11 + 3 --> a1 = 1 11 = 3 x 3 + 2 --> a2 = 3 3 = 2 x 1 + 1 --> a3 = 2

оказывается ,что (используя больше математики, чем я в настоящее время знаю, как это сделать!) что это не совпадение и что коэффициенты в непрерывной фракции p/q всегда формируются с использованием расширенного евклидова алгоритма. Это здорово, потому что это говорит нам две вещи:

1. там может быть не более o(lg (p + q)) коэффициентов, потому что евклидов алгоритм всегда заканчивается на этом много шагов, и
2. каждый коэффициент не более max{p, q}.

учитывая эти два факта, мы можем придумать алгоритм для восстановления любого рационального числа p/q, а не только между 0 и 1, применяя общий алгоритм для угадывания произвольных целых чисел n по одному за раз, чтобы восстановить все коэффициенты в непрерывной дроби для p / q. на данный момент, однако, мы просто будем беспокоиться о числах в диапазоне (0, 1], так как логика для обработки произвольных рациональных чисел может быть легко выполнена подпрограмма.

в качестве первого шага предположим, что мы хотим найти лучшее значение a₁ так что 1 / a₁ как можно ближе к p / q и a₁ - целое число. Для этого мы можем просто запустить наш алгоритм для угадывания произвольных целых чисел, принимая взаимное каждый раз. После этого произойдет одна из двух вещей. Во-первых, мы могли бы по чистой случайности обнаружить, что p/q = 1/k для некоторого целого числа k, и в этом случае мы закончили. Если нет, мы найдем, что p/q зажат между 1 / (a₁ - 1) и 1 / a₀ на₁. Когда мы делаем это, то мы начинаем работать над непрерывной дробью на один уровень глубже, находя a₂ такой, что p/q находится между 1 / (a₁ + 1 / a₂) и 1/(a₁ + 1/(a₂ + 1)). Если мы волшебным образом найдем p / q, это здорово! В противном случае мы затем идем на один уровень ниже в непрерывной фракции. В конце концов, мы найдем номер таким образом, и это не может занять слишком много времени. Каждый бинарный поиск, чтобы найти коэффициент принимает не более o(LG с(Р + Q)) время, и там в лучшем случае за o(LG с(Р + Q)) уровни на поиск, так что нам нужно только o(ГПВ²(p + q)) арифметические операции и зонды для восстановления p/q.

одна деталь, которую я хочу отметить, заключается в том, что нам нужно отслеживать, находимся ли мы на нечетном уровне или на четном уровне при выполнении поиска, потому что когда мы сэндвич p / q между двумя непрерывные фракции, нам нужно знать, был ли коэффициент, который мы искали, верхней или нижней фракцией. Я заявлю без доказательств, что для_Я С I нечетным вы хотите использовать верхний из двух чисел, а с_Я даже вы используете нижний из двух чисел.

Я почти на 100% уверен, что этот алгоритм работает. Я попытаюсь написать более формальное доказательство этого, в котором я заполняю все пробелы в этом рассуждении, и когда я это сделаю Я выложу ссылку здесь.

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

помните, что любое рациональное число в (0, 1) может быть представлено в виде конечной суммы различных (положительных или отрицательных) дробей. Например, 2/3 = 1/2 + 1/6 и 2/5 = 1/2 - 1/10. Вы можете использовать это для выполнения прямого двоичного поиска.

вот еще один способ сделать это. Если есть достаточный интерес, я постараюсь заполнить детали Сегодня вечером, но я не могу прямо сейчас, потому что у меня есть семейные обязанности. Вот заглушка реализации, которая должна объяснить алгоритм:

low = 0
high = 1
bound = 2
answer = -1
while 0 != answer:
    mid = best_continued_fraction((low + high)/2, bound)
    while mid == low or mid == high:
        bound += bound
        mid = best_continued_fraction((low + high)/2, bound)
    answer = ask(mid)
    if -1 == answer:
        low = mid
    elif 1 == answer:
        high = mid
    else:
        print_success_message(mid)

и вот объяснение. Что best_continued_fraction(x, bound) должен сделать, это найти последнее приближение непрерывной дроби к x со знаменателем не более bound. Этот алгоритм будет принимать шаги полилога для завершения и находит очень хорошие (хотя и не всегда лучшие) приближения. Так что для каждого bound мы получим что-то близкое к двоичному поиску через все возможные фракции этого размера. Иногда мы не найдем определенной доли, пока не увеличим границу дальше, чем нужно, но мы не будем далеко.

так что у вас есть. Логарифмическое число вопросов, найденных с полилогом работы.

обновление: и полный рабочий код.

#! /usr/bin/python

from fractions import Fraction
import readline
import sys

operations = [0]

def calculate_continued_fraction(terms):
    i = len(terms) - 1
    result = Fraction(terms[i])
    while 0 < i:
        i -= 1
        operations[0] += 1
        result = terms[i] + 1/result
    return result

def best_continued_fraction (x, bound):
    error = x - int(x)
    terms = [int(x)]
    last_estimate = estimate = Fraction(0)
    while 0 != error and estimate.numerator < bound:
        operations[0] += 1
        error = 1/error
        term = int(error)
        terms.append(term)
        error -= term
        last_estimate = estimate
        estimate = calculate_continued_fraction(terms)
    if estimate.numerator < bound:
        return estimate
    else:
        return last_estimate

def ask (num):
    while True:
        print "Next guess: {0} ({1})".format(num, float(num))
        if 1 < len(sys.argv):
            wanted = Fraction(sys.argv[1])
            if wanted < num:
                print "too high"
                return 1
            elif num < wanted:
                print "too low"
                return -1
            else:
                print "correct"
                return 0

        answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ")
        if answer == "h":
            return 1
        elif answer == "l":
            return -1
        elif answer == "c":
            return 0
        else:
            print "Not understood.  Please say one of (l, c, h)"

ow = Fraction(0)
high = Fraction(1)
bound = 2
answer = -1
guesses = 0
while 0 != answer:
    mid = best_continued_fraction((low + high)/2, bound)
    guesses += 1
    while mid == low or mid == high:
        bound += bound
        mid = best_continued_fraction((low + high)/2, bound)
    answer = ask(mid)
    if -1 == answer:
        low = mid
    elif 1 == answer:
        high = mid
    else:
        print "Thanks for playing!"
        print "I needed %d guesses and %d operations" % (guesses, operations[0])

это кажется немного более эффективным в догадках, чем предыдущее решение, и делает намного меньше операций. Для 101/1024 потребовалось 19 догадок и 251 операция. Для.98765 потребовалось 27 догадок и 623 операции. Для 0.0123456789 потребовалось 66 догадок и 889 операций. А для хихиканья и ухмылок, для 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (то есть 10 копий предыдущего) потребовалось 665 догадок и 23289 оперативный.

вы можете сортировать рациональные числа в заданном интервале, например, по паре (знаменатель, числитель). Тогда играть в игру вы можете

1. найти интервал [0, N] используя подход удвоения шага
2. заданного интервала [a, b] стреляйте по рациональному с наименьшим знаменателем в интервале, который ближе всего к центру интервала

это, однако, вероятно, все еще O(log(num/den) + den) (не знаете, и это слишком рано утром здесь чтобы заставить меня думать ясно ;-) )