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

Question

Однажды в качестве вопроса для интервью я получил следующее:

Я думаю о положительном целом числе n.Придумайте алгоритм, который может угадать его в O (LG N) запросах.Каждый запрос - это число по вашему выбору, и я отвечу либо «ниже», «выше» или «правильно».

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

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

Прямо сейчас, лучшее решение, которое у меня есть, может найти p / q в самое большее O (q) время неявноходить по дереву Штерна-Броко , бинарному дереву поиска по всем рациональным числам.Тем не менее, я надеялся получить время выполнения ближе к времени выполнения, которое мы получили для целочисленного случая, возможно, что-то вроде O (lg (p + q)) или O (lg pq).Кто-нибудь знает способ получения такого рода времени выполнения?

Я изначально рассматривал использование стандартного двоичного поиска в интервале [0, 1], но это позволит найти только рациональные числа с неповторяющимся двоичным представлением., который пропускает почти все рациональные решения.Я также подумал об использовании какого-либо другого способа перечисления рациональных чисел, но я не могу найти способ поиска в этом пространстве, просто сравнивая больше / равно / меньше.

Answer 1

Хорошо, вот мой ответ, используя непрерывные дроби в одиночку.

Для начала давайте разберемся с терминологией.

Пусть X = p / q - неизвестная дробь.

Пусть Q (X, p / q) = знак (X - p / q) - функция запроса: если она равна 0мы угадали число, и если оно равно +/- 1, которое говорит нам знак нашей ошибки.

Условное обозначение для непрерывных дробей - это A = [a ₀ ;a ₁ , a ₂ , a ₃ , ... a _k ]

= a ₀ + 1 / (a ​​ ₁ + 1 / (a ​​ ₂ + 1 / (a ​​ ₃ + 1 / (... + 1 /a _k ) ...)))

---

Мы будем следовать следующему алгоритму для 0

1. Инициализировать Y = 0 = [0], Z = 1 = [1], k = 0.

2. Внешний цикл : предварительные условия являются следующими:

   • Y и Z являются продолженными долями k + 1 членов, которые идентичны, за исключением последнего элемента, где они отличаются на 1, так что Y = [y ₀ ;y ₁ , y ₂ , y ₃ , ... y _k ] и Z = [y ₀ ;y ₁ , y ₂ , y ₃ , ... y _k + 1]

   • (- 1) ^k (YX) <0 <(-1) <sup>k (ZX) или, проще говоря, для четного k, Y

3. Увеличьте степень непрерывной дроби на 1 шаг без изменения значений чисел.В общем, если последние члены имеют вид y _k и y _k + 1, мы меняем его на [... y _k , y _{k+ 1} = ∞] и [... y _k , z _{k + 1} = 1].Теперь увеличьте k на 1.

4. Внутренние циклы : Это по сути то же самое, что и вопрос @ templatetypedef по поводу целых чисел.Мы делаем двухфазный двоичный поиск, чтобы приблизиться:

5. Внутренний цикл 1 : y _k = ∞, z _k = a, а X находится между Y и Z.

6. Последний член двойного Z: вычислить M = Z, но с m _k = 2 * a =2 * z _k .

7. Запросить неизвестное число: q = Q (X, M).

8. Еслиq = 0, у нас есть ответ и перейдем к шагу 17.

9. Если q и Q (X, Y) имеют противоположные знаки, это означает, что X находится между Y и M, поэтому установите Z = M и перейдите к шагу 5.

10. В противном случае установите Y = M и перейдите к следующему шагу:

11. Внутренний цикл 2. y _k =b, z _k = a, а X находится между Y и Z.

12. Если a и b отличаются на 1, поменяйте местами Y и Z, перейдите к шагу 2.

13. Выполнить бинарный поиск: вычислить M, где m _k = floor ((a + b) / 2, и запрос q = Q (X, M).

14. Если q = 0, мы закончили и перейдем к шагу 17.

15. Если q и Q (X, Y) имеютпротивоположные знаки, это означает, что X находится между Y и M, поэтому установите Z = M и перейдите к шагу 11.

16. В противном случае, q и Q (X, Z) имеют противоположные знаки, этоозначает, что X находится между Z и M, поэтому установите Y = M и перейдите к шагу 11.

17. Готово: X = M.

Aконкретный пример для X = 16/113 = 0,14159292

Y = 0 = [0], Z = 1 = [1], k = 0

k = 1:
Y = 0 = [0; &#8734;] < X, Z = 1 = [0; 1] > X, M = [0; 2] = 1/2 > X.
Y = 0 = [0; &#8734;], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 > X.
Y = 0 = [0; &#8734;], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 < X.
Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 > X.
Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 > X.
Y = 1/8 = [0; 8], Z = 1/7 = [0; 7] 
  --> the two last terms differ by one, so swap and repeat outer loop.

k = 2:
Y = 1/7 = [0; 7, &#8734;] > X, Z = 1/8 = [0; 7, 1] < X,
    M = [0; 7, 2] = 2/15 < X
Y = 1/7 = [0; 7, &#8734;], Z = 2/15 = [0; 7, 2],
    M = [0; 7, 4] = 4/29 < X
Y = 1/7 = [0; 7, &#8734;], Z = 4/29 = [0; 7, 4], 
    M = [0; 7, 8] = 8/57 < X
Y = 1/7 = [0; 7, &#8734;], Z = 8/57 = [0; 7, 8],
    M = [0; 7, 16] = 16/113 = X 
    --> done!

На каждом шаге вычисления M, диапазонинтервал уменьшается.Вероятно, довольно легко доказать (хотя я не буду этого делать), что интервал сокращается как минимум в 1 / sqrt (5) на каждом шаге, что показало бы, что этот алгоритм имеет O (log q) шагов.

Обратите внимание, что это можно объединить с первоначальным вопросом интервью templatetypedef и применить к любому рациональному числу p / q, а не только между 0 и 1, путем первого вычисления Q (X, 0),затем для целых положительных / отрицательных целых чисел, ограничивающих два последовательных целых числа, а затем использующих вышеупомянутый алгоритм для дробной части.

Когда у меня появится возможность, я опубликую программу на python, реализующую этот алгоритм.

edit : также обратите внимание, что вам не нужно вычислять непрерывную дробь на каждом шаге (которая будет O (k), есть частичные аппроксимации к непрерывным дробям, которые могут вычислить следующий шаг из предыдущий шаг в O (1).)

edit 2 : рекурсивное определение частичных приближений:

Если A _k = [a ₀ ; a ₁ , a ₂ , a ₃ , ... a _k ] = p _k / q _k , затем p _k = a _k p _k-1 + p _k-2 и q _k = a _k q _k-1 + q _k-2 . (Источник: Niven & Zuckerman, 4-е издание, теоремы 7.3-7.5. См. Также Википедия )

Пример: [0] = 0/1 = p ₀ / q ₀ , [0; 7] = 1/7 = p ₁ / q ₁ ; так [0; 7, 16] = (16 * 1 + 0) / (16 * 7 + 1) = 16/113 = p ₂ / q ₂ .

Это означает, что если две непрерывные дроби Y и Z имеют одинаковые термины, кроме последнего, и непрерывная дробь, исключающая последний член, равна p _k-1 / q _k-1 , тогда мы можем написать Y = (y _k p _k-1 + p _k-2 ) / (y _k q _k-1 + q _k-2 ) и Z = (z _k p _k-1 + p _{k -2} ) / (z _k q _k-1 + q _k-2 ). Из этого следует показать, что | Y-Z | уменьшается по крайней мере в 1 / sqrt (5) на каждом меньшем интервале, производимом этим алгоритмом, но алгебра в данный момент, похоже, находится за пределами моего понимания. : - (

Вот моя программа на Python:

import math

# Return a function that returns Q(p0/q0,p/q) 
#   = sign(p0/q0-p/q) = sign(p0q-q0p)*sign(q0*q)
# If p/q < p0/q0, then Q() = 1; if p/q < p0/q0, then Q() = -1; otherwise Q()=0.
def makeQ(p0,q0):
  def Q(p,q):
    return cmp(q0*p,p0*q)*cmp(q0*q,0)
  return Q

def strsign(s):
  return '<' if s<0 else '>' if s>0 else '=='

def cfnext(p1,q1,p2,q2,a):
  return [a*p1+p2,a*q1+q2]

def ratguess(Q, doprint, kmax):
# p2/q2 = p[k-2]/q[k-2]
  p2 = 1
  q2 = 0
# p1/q1 = p[k-1]/q[k-1]
  p1 = 0
  q1 = 1
  k = 0
  cf = [0]
  done = False
  while not done and (not kmax or k < kmax):
    if doprint:
      print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
# extend continued fraction
    k = k + 1
    [py,qy] = [p1,q1]
    [pz,qz] = cfnext(p1,q1,p2,q2,1)
    ay = None
    az = 1
    sy = Q(py,qy)
    sz = Q(pz,qz)
    while not done:
      if doprint:
        out = str(py)+'/'+str(qy)+' '+strsign(sy)+' X '
        out += strsign(-sz)+' '+str(pz)+'/'+str(qz)
        out += ', interval='+str(abs(1.0*py/qy-1.0*pz/qz))
      if ay:
        if (ay - az == 1):
          [p0,q0,a0] = [pz,qz,az]
          break
        am = (ay+az)/2
      else:
        am = az * 2
      [pm,qm] = cfnext(p1,q1,p2,q2,am)
      sm = Q(pm,qm)
      if doprint:
        out = str(ay)+':'+str(am)+':'+str(az) + '   ' + out + ';  M='+str(pm)+'/'+str(qm)+' '+strsign(sm)+' X '
        print out
      if (sm == 0):
        [p0,q0,a0] = [pm,qm,am]
        done = True
        break
      elif (sm == sy):
        [py,qy,ay,sy] = [pm,qm,am,sm]
      else:
        [pz,qz,az,sz] = [pm,qm,am,sm]     

    [p2,q2] = [p1,q1]
    [p1,q1] = [p0,q0]    
    cf += [a0]

  print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
  return [p1,q1]

и пример вывода для ratguess(makeQ(33102,113017), True, 20):

p/q=[0]=0/1
None:2:1   0/1 < X < 1/1, interval=1.0;  M=1/2 > X 
None:4:2   0/1 < X < 1/2, interval=0.5;  M=1/4 < X 
4:3:2   1/4 < X < 1/2, interval=0.25;  M=1/3 > X 
p/q=[0, 3]=1/3
None:2:1   1/3 > X > 1/4, interval=0.0833333333333;  M=2/7 < X 
None:4:2   1/3 > X > 2/7, interval=0.047619047619;  M=4/13 > X 
4:3:2   4/13 > X > 2/7, interval=0.021978021978;  M=3/10 > X 
p/q=[0, 3, 2]=2/7
None:2:1   2/7 < X < 3/10, interval=0.0142857142857;  M=5/17 > X 
None:4:2   2/7 < X < 5/17, interval=0.00840336134454;  M=9/31 < X 
4:3:2   9/31 < X < 5/17, interval=0.00379506641366;  M=7/24 < X 
p/q=[0, 3, 2, 2]=5/17
None:2:1   5/17 > X > 7/24, interval=0.00245098039216;  M=12/41 < X 
None:4:2   5/17 > X > 12/41, interval=0.00143472022956;  M=22/75 > X 
4:3:2   22/75 > X > 12/41, interval=0.000650406504065;  M=17/58 > X 
p/q=[0, 3, 2, 2, 2]=12/41
None:2:1   12/41 < X < 17/58, interval=0.000420521446594;  M=29/99 > X 
None:4:2   12/41 < X < 29/99, interval=0.000246366100025;  M=53/181 < X 
4:3:2   53/181 < X < 29/99, interval=0.000111613371282;  M=41/140 < X 
p/q=[0, 3, 2, 2, 2, 2]=29/99
None:2:1   29/99 > X > 41/140, interval=7.21500721501e-05;  M=70/239 < X 
None:4:2   29/99 > X > 70/239, interval=4.226364059e-05;  M=128/437 > X 
4:3:2   128/437 > X > 70/239, interval=1.91492009996e-05;  M=99/338 > X 
p/q=[0, 3, 2, 2, 2, 2, 2]=70/239
None:2:1   70/239 < X < 99/338, interval=1.23789953207e-05;  M=169/577 > X 
None:4:2   70/239 < X < 169/577, interval=7.2514738621e-06;  M=309/1055 < X 
4:3:2   309/1055 < X < 169/577, interval=3.28550190148e-06;  M=239/816 < X 
p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577
None:2:1   169/577 > X > 239/816, interval=2.12389981991e-06;  M=408/1393 < X 
None:4:2   169/577 > X > 408/1393, interval=1.24415093544e-06;  M=746/2547 < X 
None:8:4   169/577 > X > 746/2547, interval=6.80448470014e-07;  M=1422/4855 < X 
None:16:8   169/577 > X > 1422/4855, interval=3.56972657711e-07;  M=2774/9471 > X 
16:12:8   2774/9471 > X > 1422/4855, interval=1.73982239227e-07;  M=2098/7163 > X 
12:10:8   2098/7163 > X > 1422/4855, interval=1.15020646951e-07;  M=1760/6009 > X 
10:9:8   1760/6009 > X > 1422/4855, interval=6.85549088053e-08;  M=1591/5432 < X 
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432
None:2:1   1591/5432 < X < 1760/6009, interval=3.06364213998e-08;  M=3351/11441 < X 
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009
None:2:1   1760/6009 > X > 3351/11441, interval=1.45456726663e-08;  M=5111/17450 < X 
None:4:2   1760/6009 > X > 5111/17450, interval=9.53679318849e-09;  M=8631/29468 < X 
None:8:4   1760/6009 > X > 8631/29468, interval=5.6473816179e-09;  M=15671/53504 < X 
None:16:8   1760/6009 > X > 15671/53504, interval=3.11036635336e-09;  M=29751/101576 > X 
16:12:8   29751/101576 > X > 15671/53504, interval=1.47201634215e-09;  M=22711/77540 > X 
12:10:8   22711/77540 > X > 15671/53504, interval=9.64157420569e-10;  M=19191/65522 > X 
10:9:8   19191/65522 > X > 15671/53504, interval=5.70501257346e-10;  M=17431/59513 > X 
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504
None:2:1   15671/53504 < X < 17431/59513, interval=3.14052228667e-10;  M=33102/113017 == X

Поскольку Python с самого начала обрабатывает математику biginteger, а эта программа использует только целочисленную математику (кроме интервальных вычислений), она должна работать для произвольных рациональных чисел.

---

edit 3 : Схема доказательства того, что это O (log q), а не O (log ^ 2 q):

Сначала отметим, что до тех пор, пока не будет найдено рациональное число, число шагов n _k для каждого нового члена с продолженной дробью будет точно 2b (a_k) -1, где b (a_k) количество битов, необходимых для представления a_k = ceil (log2 (a_k)): b (a_k) шагов, чтобы расширить «сеть» двоичного поиска, и b (a_k) -1 шагов, чтобы сузить его). Посмотрите пример выше, вы заметите, что число шагов всегда 1, 3, 7, 15 и т. Д.

Теперь мы можем использовать рекуррентное соотношение q _k = a _k q _k-1 + q _k-2 и индукцию доказать желаемый результат.

Давайте сформулируем это следующим образом: значение q после шагов N _k = sum (n _k ), необходимых для достижения k-го члена, имеет минимум: q> = A * 2 ^cN для некоторых фиксированных констант A, c. (чтобы инвертировать, мы получили бы, что число шагов N равно <= (1 / c) * log <sub>2 (q / A) = O (log q).)

Базовые шкафы:

• k = 0: q = 1, N = 0, поэтому q> = 2 ^N
• k = 1: для N = 2b-1 шагов q = a ₁ > = 2 ^b-1 = 2 ^{(N-1) / 2} = 2 ^{N / 2} / sqrt (2).

Это означает, что A = 1, c = 1/2 может дать желаемые границы. В действительности, q может не удваивать каждый член (контрпример: [0; 1, 1, 1, 1, 1] имеет коэффициент роста phi = (1 + sqrt (5)) / 2), поэтому давайте использовать с = 1/4.

Индукция:

• для термина k, q _k = a _k q _k-1 + q _k-2 . Опять же, для n _k = 2b-1 шагов, необходимых для этого термина, a _k > = 2 ^b-1 = 2 ^{(n _{к * +1361 * -1) / 2 * * тысяча триста шестьдесят два. * * +1363 То есть k q k-1 > = 2 (N k -1) / 2 * q k-1 > = 2 (n k -1) / 2 * A * 2 N k-1 / 4 = A * 2 N k / 4 / sqrt (2) * 2 n k / 4 .}}

Argh - трудная часть здесь в том, что если _k = 1, то q может не сильно увеличиться для этого одного члена, и нам нужно использовать q _k-2 , но это может быть намного меньше, чем q _k-1 .

Answer 2

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

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 шагах мы рассмотрим первые 2<sup>O(n)</sup> возможностей, что соответствует порядку величины эффективности, которую вы искали.

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

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

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

Однако мы на самом деле намного лучше, чем это. С нашим первым предположением мы исключаем половину рациональных чисел из нашего списка как слишком большие или маленькие. Наши следующие две догадки не совсем разрезают пространство на четыре части, но они не слишком далеки от этого. Наши следующие 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 догадок и около секунды, чтобы их сгенерировать. (Обратите внимание, если вы вызываете программу с рациональным числом в качестве аргумента, она заполнит все догадки для вас. Это очень полезное удобство.)

Answer 3

Я понял!Вам нужно использовать параллельный поиск с делением пополам и непрерывные дроби .

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

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

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

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

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

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

1. l = 0, u = 1, query = 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,и = 1/16.Теперь 1 / l = 32, 1 / u = 16, у них разные повторения cfrac, так что делайте пополам, запрос = 3 / 64.

7. l = 1/32, u =3/64, запрос = 5/128 = 1 / 25,6

8. l = 1/32, u = 5/128, запрос = 9/256 = 1 / 28,4444 ....

9. l = 1/32, u = 9/256, запрос = 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 довольноблизко к пи).

[продолжение следует, я должен куда-то идти]

---

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

Answer 4

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

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

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

Для соответствующего выбора _i . Это называется непрерывная дробь . Что еще более важно, хотя эти _i можно получить, запустив евклидов алгоритм на числителе и знаменателе. Например, предположим, что мы хотим представить 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), поскольку логику обработки произвольных рациональных чисел можно легко сделать, учитывая это как подпрограмму.

В качестве первого шага давайте предположим, что мы хотим найти наилучшее значение ₁ , чтобы 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 (p + q)) времени, и для поиска существует не более O (lg (p + q)) уровней, поэтому нам нужен только O (lg ^{) 2} (p + q)) арифметические операции и пробники для восстановления p / q.

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

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

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

Answer 5

Мне кажется, я нашел алгоритм O (log ^ 2 (p + q)).

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

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

Мы хотим проверить все дроби r / s с r + s <= k и удваивать k, пока k не станет достаточно большим. Обратите внимание, что есть O (k ^ 2) дробей, которые вы должны проверить для данного значения k. Создайте сбалансированное бинарное дерево поиска, содержащее все эти значения, затем найдите его, чтобы определить, находится ли p / q в дереве. Требуется O (log k ^ 2) = O (log k) запросов, чтобы подтвердить, что p / q отсутствует в дереве. </p>

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

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

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

Answer 6

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

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,012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012301674567890123456789 (это 10 копий предыдущего) потребовалось 665 догадок и 23289 операций.

Answer 7

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

Answer 8

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

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

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