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

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

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

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

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

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

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

Ответ 1

Хорошо, здесь мой ответ, используя продолжение фракций.

Сначала дадим здесь некоторую терминологию.

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

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

условная нотация для непрерывных дробей: A = [a ₀; a ₁, a ₂, a ₃,... a _k]

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

Мы будем следовать следующему алгоритму для 0 < p/q < 1.

Инициализировать Y = 0 = [0], Z = 1 = [1], k = 0.
Внешняя петля. Предпосылками являются:
- Y и Z - непрерывные доли k + 1 членов, которые идентичны, за исключением последнего элемента, где они отличаются на 1, так что Y = [y ₀; y ₁, y ₂, y ₃,... y _k] и Z = [y _{0суб > ; y ₁, y ₂, y ₃,... y _k + 1]}
- (- 1) ^k (Y-X) 0 < (-1) ^k (Z-X), или в более простых терминах, для k четных, Y < X < Z и для k нечетных, Z < X < Y.
Увеличьте степень непрерывной дроби на 1 шаг без изменения значений чисел. В общем случае, если последние слагаемые y _k и y _k + 1, мы изменим это на [... y _k, y _{k + 1}= ∞] и [... y _k, z _{k + 1}= 1]. Теперь увеличьте k на 1.
Внутренние петли. Это по сути то же самое, что и вопрос @templatetypedef о проблемах с целыми числами. Мы делаем двухфазный бинарный поиск, чтобы приблизиться:
Внутренний цикл 1: y _k= ∞, z _k= a, а X - между Y и Z.
Двойной Z последний термин: вычислить M = Z, но с m _k= 2 * a = 2 * z _k.
Запросить неизвестное число: q = Q (X, M).
Если q = 0, мы получаем наш ответ и переходим к шагу 17.
Если q и Q (X, Y) имеют противоположные знаки, это означает, что X находится между Y и M, поэтому установите Z = M и переходим к шагу 5.
В противном случае установите Y = M и перейдите к следующему шагу:
Внутренний цикл 2. y _k= b, z _k= a, а X - между Y и Z.
Если a и b отличаются на 1, замените Y и Z, перейдите к шагу 2.
Выполните двоичный поиск: вычислите M, где m _k= floor ((a + b)/2, и запрос q = Q (X, M).
Если q = 0, мы закончили и переходим к шагу 17.
Если q и Q (X, Y) имеют противоположные знаки, это означает, что X находится между Y и M, поэтому установите Z = M и переходим к шагу 11.
В противном случае q и Q (X, Z) имеют противоположные знаки, это означает, что X находится между Z и M, поэтому установите Y = M и перейдите к шагу 11.
Готово: X = M.

Конкретный пример для 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. (Источник: Нивен и Цукерман, 4-е изд., Теоремы 7.3-7.5. См. Также Wikipedia)

Пример: [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 ₂ (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), поэтому пусть c = 1/4.

Индукция:

для термина k, q _k= a _k q _k-1 + q _{k-2к югу > . Опять же, для шагов n _k= 2b-1, необходимых для этого термина, a _k >= 2 ^b-1= 2 ^{(п <суб > ксуб > -1)/2}.}

Итак, _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 - жесткая часть здесь заключается в том, что если a _k= 1, q не может сильно увеличиться для этого одного члена, и нам нужно использовать q _k-2 но это может быть намного меньше q _k-1.

Ответ 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^O(n), которые находятся в порядке величины эффективности, которую вы искали.

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

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

l = 0, u = 1/2, query = 1/4.

l = 0, u = 1/4, query = 1/8.

l = 0, u = 1/8, query = 1/16.

l = 0, u = 1/16, query = 1/32.

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

l = 1/32, u = 3/64, query = 5/128 = 1/25.6

l = 1/32, u = 5/128, query = 9/256 = 1/28.4444....

l = 1/32, u = 9/256, query = 17/512 = 1/30.1176... (раунд до 1/30)

l = 1/32, u = 17/512, query = 33/1024 = 1/31.0303... (раунд до 1/31)

l = 33/1024, u = 17/512, query = 67/2048 = 1/30.5672... (раунд до 1/31)

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

УСПЕХ!

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

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

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

Ответ 4

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

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

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

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

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

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

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

Ответ 5

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

Интуиция алгоритма заключается в том, что любое рациональное число 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 × 3 + 2 → a2 = 3 3 = 2 x 1 + 1 → a3 = 2

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

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

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

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

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

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

Спасибо всем, кто внес вклад в понимание, необходимое для того, чтобы это решение работало, особенно Jason S, предлагая бинарный поиск по продолжающимся дроби.

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

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