¿El juego de "adivinar el número" para números racionales arbitrarios?

77

Una vez recibí lo siguiente como pregunta de entrevista:

Estoy pensando en un número entero positivo n. Cree un algoritmo que pueda adivinarlo en consultas O (lg n). Cada consulta es un número de su elección y responderé "más bajo", "más alto" o "correcto".

Este problema puede resolverse mediante una búsqueda binaria modificada, en la que enumera potencias de dos hasta encontrar una que exceda n, luego ejecuta una búsqueda binaria estándar sobre ese rango. Lo que creo que es tan bueno de esto es que puedes buscar un número en particular en un espacio infinito más rápido que solo la fuerza bruta.

Sin embargo, la pregunta que tengo es una pequeña modificación de este problema. En lugar de elegir un número entero positivo, suponga que elijo un número racional arbitrario entre cero y uno. Mi pregunta es: ¿qué algoritmo puede usar para determinar de manera más eficiente qué número racional he elegido?

En este momento, la mejor solución que tengo puede encontrar p / q en un tiempo máximo de O (q) caminando implícitamente en el árbol Stern-Brocot , un árbol de búsqueda binaria sobre todos los racionales. Sin embargo, esperaba conseguir un tiempo de ejecución más cercano al tiempo de ejecución que obtuvimos para el caso de números enteros, tal vez algo como O (lg (p + q)) u O (lg pq). ¿Alguien sabe alguna forma de obtener este tipo de tiempo de ejecución?

Inicialmente consideré usar una búsqueda binaria estándar del intervalo [0, 1], pero esto solo encontrará números racionales con una representación binaria no repetida, que pierde casi todos los racionales. También pensé en usar alguna otra forma de enumerar los racionales, pero parece que no puedo encontrar una manera de buscar en este espacio dadas solo comparaciones mayores / iguales / menores.

algorithm math puzzle rational-numbers templatetypedef
fuente
3
Um, ¿te das cuenta de que sin algunos límites esto es imposible, ya que hay infinitos números racionales en cualquier rango? Realmente tampoco puedes buscar un número entero ilimitado; suponga que el número hubiera sido un número aleatorio con 10 ^ 1000 dígitos. "100" - "más alto". "1000" - "superior". "Un millón" - "más alto". "¿Un billón?" "Mayor." "¿Un googol ?" "¡Mayor!"
Tom Zych
16
@Tom: dado cualquier número (como 10 ^ 1000), el algoritmo lo encontrará en una cantidad de tiempo finita (incluso si es un tiempo muy largo). Esto es diferente a decir que el algoritmo puede adivinar cualquier número dentro de t pasos (para un valor fijo de t), pero nadie ha hecho esta afirmación.
Seth
6
@Tom Zych- si eliges cualquier entero finito, eventualmente puedo encontrarlo duplicando repetidamente. Puede llevar una cantidad de tiempo ridícula, pero aún puedo hacerlo en un tiempo proporcional al logaritmo de su número. En esto, asumo que la persona que responde a las preguntas representa honestamente el número y no solo elude al responder de una manera que nunca termina.
templatetypedef
Interesante algoritmo. Todos los racionales con denominador N están ubicados antes (o en) el nivel N del árbol, por lo que O (q) es claramente posible
Dr. belisarius
4
@Todo el mundo: Me gustaría decir que esta ha sido una pregunta interesante con algunas respuestas y discusiones interesantes. Mi nerd matemático interior está feliz.
Seth

Respuestas:

49

Bien, aquí está mi respuesta usando solo fracciones continuas .

Primero, obtengamos algo de terminología aquí.

Sea X = p / q la fracción desconocida.

Deje que Q (X, p / q) = sign (X - p / q) sea la función de consulta: si es 0, hemos adivinado el número, y si es +/- 1 que nos dice el signo de nuestro error .

La notación convencional para fracciones continuas es A = [a 0 ; a 1 , a 2 , a 3 , ... a k ]

= a 0 + 1 / (a 1 + 1 / (a 2 + 1 / (a 3 + 1 / (... + 1 / a k ) ...)))

Seguiremos el siguiente algoritmo para 0 <p / q <1.

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

  2. Bucle externo : las condiciones previas son las siguientes:

    • Y y Z son fracciones continuas de k + 1 términos que son idénticos excepto en el último elemento, donde difieren en 1, de modo que Y = [y 0 ; y 1 , y 2 , y 3 , ... y k ] y Z = [y 0 ; y 1 , y 2 , y 3 , ... y k + 1]

    • (-1) k (YX) <0 <(-1) k (ZX), o en términos más simples, para k par, Y <X <Z y para k impar, Z <X <Y.

  3. Extiende el grado de la fracción continua en 1 paso sin cambiar los valores de los números. En general, si los últimos términos son y k y y k + 1, lo cambiamos a [... y k , y k + 1 = ∞] y [... y k , z k + 1 = 1]. Ahora aumente k en 1.

  4. Bucles internos : esto es esencialmente lo mismo que la pregunta de la entrevista de @ templatetypedef sobre los números enteros. Hacemos una búsqueda binaria de dos fases para acercarnos:

  5. Bucle interior 1 : y k = ∞, z k = a, y X está entre Y y Z.

  6. Último término de Double Z: Calcule M = Z pero con m k = 2 * a = 2 * z k .

  7. Consultar el número desconocido: q = Q (X, M).

  8. Si q = 0, tenemos nuestra respuesta y vamos al paso 17.

  9. Si q y Q (X, Y) tienen signos opuestos, significa que X está entre Y y M, así que configure Z = M y vaya al paso 5.

  10. De lo contrario, configure Y = M y vaya al siguiente paso:

  11. Bucle interior 2. y k = b, z k = a, y X está entre Y y Z.

  12. Si ayb difieren en 1, intercambie Y y Z, vaya al paso 2.

  13. Realice una búsqueda binaria: calcule M donde m k = piso ((a + b) / 2, y consulte q = Q (X, M).

  14. Si q = 0, terminamos y vamos al paso 17.

  15. Si q y Q (X, Y) tienen signos opuestos, significa que X está entre Y y M, así que configure Z = M y vaya al paso 11.

  16. De lo contrario, q y Q (X, Z) tienen signos opuestos, significa que X está entre Z y M, así que configure Y = M y vaya al paso 11.

  17. Hecho: X = M.

Un ejemplo concreto para 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!

En cada paso del cálculo de M, el rango del intervalo se reduce. Probablemente sea bastante fácil probar (aunque no haré esto) que el intervalo se reduce en un factor de al menos 1 / sqrt (5) en cada paso, lo que mostraría que este algoritmo es O (log q) pasos.

Tenga en cuenta que esto puede combinarse con la pregunta de entrevista original de templatetypedef y aplicarse a cualquier número racional p / q, no solo entre 0 y 1, calculando primero Q (X, 0), luego para enteros positivos / negativos, delimitando entre dos enteros, y luego usando el algoritmo anterior para la parte fraccionaria.

La próxima vez que tenga la oportunidad, publicaré un programa de Python que implemente este algoritmo.

editar : también, tenga en cuenta que no tiene que calcular la fracción continua en cada paso (que sería O (k), hay aproximaciones parciales a las fracciones continuas que pueden calcular el siguiente paso del paso anterior en O (1). )

edición 2 : Definición recursiva de aproximaciones parciales:

Si A k = [a 0 ; a 1 , a 2 , a 3 , ... a k ] = p k / q k , entonces p k = a k p k-1 + p k-2 , y q k = a k q k-1 + q k-2 . (Fuente: Niven & Zuckerman, 4th ed, Theorems 7.3-7.5. Ver también Wikipedia )

Ejemplo: [0] = 0/1 = p 0 / q 0 , [0; 7] = 1/7 = p 1 / q 1 ; entonces [0; 7, 16] = (16 * 1 + 0) / (16 * 7 + 1) = 16/113 = p 2 / q 2 .

Esto significa que si dos fracciones continuas Y y Z tienen los mismos términos excepto el último, y la fracción continua que excluye el último término es p k-1 / q k-1 , entonces podemos escribir Y = (y k p k- 1 + p k-2 ) / (y k q k-1 + q k-2 ) y Z = (z k p k-1 + p k-2 ) / (z k q k-1 + q k-2 ). Debería ser posible demostrar a partir de esto que | YZ | disminuye en al menos un factor de 1 / sqrt (5) en cada intervalo más pequeño producido por este algoritmo, pero el álgebra parece estar más allá de mí en este momento. :-(

Aquí está mi programa 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]

y una salida de muestra para 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

Dado que Python maneja matemáticas de números enteros desde el principio, y este programa solo usa matemáticas de números enteros (excepto para los cálculos de intervalo), debería funcionar para racionales arbitrarias.

edición 3 : Esquema de la prueba de que esto es O (log q), no O (log ^ 2 q):

Primero tenga en cuenta que hasta que se encuentre el número racional, el # de pasos n k para cada nuevo término de fracción continua es exactamente 2b (a_k) -1 donde b (a_k) es el # de bits necesarios para representar a_k = ceil (log2 (a_k )): son b (a_k) pasos para ampliar la "red" de la búsqueda binaria, y b (a_k) -1 pasos para reducirla). Vea el ejemplo anterior, observará que el número de pasos es siempre 1, 3, 7, 15, etc.

Ahora podemos usar la relación de recurrencia q k = a k q k-1 + q k-2 y la inducción para demostrar el resultado deseado.

Digámoslo de esta manera: que el valor de q después de los N k = suma (n k ) pasos requeridos para alcanzar el k-ésimo término tiene un mínimo: q> = A * 2 cN para algunas constantes fijas A, c. (para invertir, obtendríamos que el # de pasos N es <= (1 / c) * log 2 (q / A) = O (log q).)

Casos base:

  • k = 0: q = 1, N = 0, entonces q> = 2 N
  • k = 1: para N = 2b-1 pasos, q = a 1 > = 2 b-1 = 2 (N-1) / 2 = 2 N / 2 / sqrt (2).

Esto implica que A = 1, c = 1/2 podría proporcionar los límites deseados. En realidad, q no puede duplicar cada término (contraejemplo: [0; 1, 1, 1, 1, 1] tiene un factor de crecimiento de phi = (1 + sqrt (5)) / 2) así que usemos c = 1 / 4.

Inducción:

  • para el término k, q k = a k q k-1 + q k-2 . Nuevamente, para los n k = 2b-1 pasos necesarios para este término, a k > = 2 b-1 = 2 (n k -1) / 2 .

    Entonces a 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 / raíz cuadrada (2) * 2 n k / 4 .

Argh, la parte difícil aquí es que si a k = 1, es posible que q no aumente mucho para ese término, y necesitamos usar q k-2 pero eso puede ser mucho más pequeño que q k-1 .

Jason S
fuente
Así que esto se ve muy bien, pero no creo que sea O (lg q). Cualquier iteración individual del ciclo interno se ejecuta en pasos O (lg q) a medida que utiliza la búsqueda binaria modificada para recuperar el siguiente número de la fracción continua, pero recuerde que hay O (lg q) iteraciones de ese ciclo, ya que hay ( en el peor de los casos) O (lg q) números en la fracción parcial. Eso me hace pensar que este es el tiempo O (lg ^ 2 q). Sin embargo, esta sigue siendo una excelente solución al problema, y ​​ya sea que sea O (lg q) u O (lg ^ 2 q), sigue siendo exponencialmente mejor que lo que tenía antes.
templatetypedef
Sé que parece O (lg ^ 2 q) debido a los dos bucles, pero probablemente sea conservador. Intentaré probarlo.
Jason S
+1: No verifiqué los detalles, pero ahora creo que el enfoque CF funcionará.
Necesitas probar y demostrar que | YZ | disminuye geométricamente. Como menciona typedeftemplate en su respuesta, hay términos O (log q) en el CF, cada uno de tamaño como máximo q. Entonces, si toma O (log q) pasos para aumentar el 'grado' de su FQ en 1, toma O (log ^ 2 q) pasos en total.
No, no puede evaluarlo como O (log ^ 2 q) debido a los dos bucles; eso es demasiado conservador. Si toma O (log q) pasos para aumentar el número de términos de la fracción continua, entonces el término de esa fracción es muy grande y el intervalo será muy pequeño. Cada iteración del bucle interno también disminuye el intervalo, no solo el aumento en la longitud de la fracción continua.
Jason S
6

Tomemos los números racionales, en forma reducida, y escribamos primero en el orden del denominador, luego del numerador.

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

Nuestra primera suposición será 1/2. Luego seguiremos la lista hasta que tengamos 3 en nuestro rango. Luego, realizaremos 2 intentos para buscar en esa lista. Luego seguiremos la lista hasta que tengamos 7 en nuestro rango restante. Luego, realizaremos 3 intentos para buscar en esa lista. Y así.

En npasos, cubriremos las primeras posibilidades, que se encuentran en el orden de magnitud de eficiencia que estaba buscando.2O(n)

Actualización: la gente no entendió el razonamiento detrás de esto. El razonamiento es simple. Sabemos cómo caminar por un árbol binario de manera eficiente. Hay fracciones con máximo denominador . Por lo tanto, podríamos buscar hasta cualquier tamaño de denominador particular en pasos. El problema es que tenemos un número infinito de posibles racionales para buscar. Así que no podemos simplemente alinearlos todos, ordenarlos y comenzar a buscar.O(n2)nO(2*log(n)) = O(log(n))

Por lo tanto, mi idea era alinear algunos, buscar, alinear más, buscar, etc. Cada vez que hacemos más fila, nos alineamos aproximadamente el doble de lo que hicimos la última vez. Así que necesitamos una suposición más que la última vez. Por lo tanto, nuestra primera pasada usa 1 suposición para recorrer 1 posible racional. Nuestro segundo usa 2 conjeturas para atravesar 3 posibles racionales. Nuestro tercero usa 3 conjeturas para atravesar 7 posibles racionales. Y nuestro k'th usa kconjeturas para atravesar posibles racionales. Para cualquier racional en particular , eventualmente terminará colocando ese racional en una lista bastante grande en la que sabe cómo hacer una búsqueda binaria de manera eficiente.2k-1m/n

Si hiciéramos búsquedas binarias, luego ignoramos todo lo que aprendimos cuando obtenemos más racionales, entonces pondríamos todos los racionales hasta e inclusive m/nen O(log(n))pases. (Eso es porque en ese punto llegaremos a un paso con suficientes racionales para incluir cada racional hasta e inclusive m/n). Pero cada paso requiere más conjeturas, por lo que serían conjeturas.O(log(n)2)

Sin embargo, lo hacemos mucho mejor que eso. Con nuestra primera suposición, eliminamos la mitad de los racionales de nuestra lista por ser demasiado grandes o pequeños. Nuestras siguientes dos conjeturas no cortan el espacio en cuartos, pero no se alejan demasiado de él. Nuestras siguientes 3 conjeturas nuevamente no cortan el espacio en octavos, pero no se alejan demasiado de él. Y así. Cuando lo juntas, estoy convencido de que el resultado es que encuentras m/nen O(log(n))pasos. Aunque en realidad no tengo una prueba.

Pruébelo: aquí hay un código para generar las conjeturas para que pueda jugar y ver qué tan eficiente es.

#! /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] = []

Como ejemplo para probarlo, probé 101/1024 (0.0986328125) y descubrí que se necesitaron 20 conjeturas para encontrar la respuesta. Probé 0.98765 y me tomó 45 intentos. Probé 0.0123456789 y necesité 66 conjeturas y alrededor de un segundo para generarlas. (Tenga en cuenta que si llama al programa con un número racional como argumento, completará todas las suposiciones por usted. Esta es una conveniencia muy útil).

tímidamente
fuente
No estoy seguro de entender lo que estás diciendo. ¿Puedes aclarar esto?
templatetypedef
@templatetypedef: ¿Qué no está claro? Nuestra primera suposición es siempre 1/2. Supongamos que la respuesta vuelve más baja. Los siguientes 3 números de la lista que se ajustan a la condición son 1/3, 1/4y 1/5. Así que adivinamos a 1/4continuación, luego 1/3o 1/5en la siguiente suposición. Si continuamos, tomamos 7 números en nuestro rango y configuramos las siguientes 3 conjeturas. Después de eso, tomaremos 15 y configuraremos las siguientes 4 conjeturas. etc. ¿Qué no está claro sobre eso? Me voy a la cama ahora. Si todavía no lo entiendes por la mañana, escribiré un programa para hacer las adivinanzas y podrás ver cómo funciona.
Btilly
3
@btilly: ¿Dónde entran el 7-3, 15-4, (31-5?) ¿Cuál es la lógica detrás de tener tal cola de números de "adivinar el siguiente"?
stakx - ya no contribuye el
2
@Btilly: +1, pero parece que realmente no has resuelto el problema principal . Generas racionales Theta (q) y haces una búsqueda binaria sobre ellos. Por tanto, el tiempo de ejecución es Omega (q), a pesar de que realiza consultas O (log ^ 2 q). De hecho, Seth tiene un algoritmo muy similar (y si lee con atención, no está consultando p + q). En mi opinión, el principal problema que se debe resolver aquí es la generación de O (polylog (q)) racionales, en lugar de intentar mantener el número de consultas O (polylog (q)) independientemente de los otros gastos generales de contabilidad.
1
@Seth: Btilly, no billy :-) q o p + q, no importa, ya que p <q.
4

¡Lo tengo! Lo que debe hacer es utilizar una búsqueda paralela con bisección y fracciones continuas .

La bisección le dará un límite hacia un número real específico, representado como una potencia de dos, y las fracciones continuas tomarán el número real y encontrarán el número racional más cercano.

La forma en que los ejecuta en paralelo es la siguiente.

En cada paso, tienes ly usiendo los límites superior e inferior de la bisección. La idea es que puede elegir entre dividir a la mitad el rango de bisección y agregar un término adicional como una representación de fracción continua. Cuando ambos ly utienen el mismo término siguiente como fracción continua, entonces da el siguiente paso en la búsqueda de fracción continua y realiza una consulta utilizando la fracción continua. De lo contrario, reduce a la mitad el rango mediante bisección.

Dado que ambos métodos aumentan el denominador en al menos un factor constante (la bisección va por factores de 2, las fracciones continuas van por al menos un factor de phi = (1 + sqrt (5)) / 2), esto significa que su búsqueda debe ser O (registro (q)). (Puede haber cálculos repetidos de fracciones continuas, por lo que puede terminar como O (log (q) ^ 2).)

Nuestra búsqueda continua de fracciones debe redondearse al número entero más cercano, no usar piso (esto es más claro a continuación).

Lo anterior es algo ondulado. Usemos un ejemplo concreto de r = 1/31:

  1. l = 0, u = 1, consulta = 1/2. 0 no se puede expresar como una fracción continua, por lo que usamos la búsqueda binaria hasta que l! = 0.

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

  3. l = 0, u = 1/4, consulta = 1/8.

  4. l = 0, u = 1/8, consulta = 1/16.

  5. l = 0, u = 1/16, consulta = 1/32.

  6. l = 1/32, u = 1/16. Ahora 1 / l = 32, 1 / u = 16, estos tienen diferentes repeticiones de cfrac, así que sigue bisecando., Query = 3/64.

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

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

  9. l = 1/32, u = 9/256, consulta = 17/512 = 1 / 30.1176 ... (redondeado a 1/30)

  10. l = 1/32, u = 17/512, consulta = 33/1024 = 1 / 31.0303 ... (redondeado a 1/31)

  11. l = 33/1024, u = 17/512, consulta = 67/2048 = 1 / 30.5672 ... (redondeado a 1/31)

  12. l = 33/1024, u = 67/2048. En este punto, tanto l como u tienen el mismo término de fracción continua 31, por lo que ahora usamos una estimación de fracción continua. consulta = 1/31.

¡ÉXITO!

Para otro ejemplo, usemos 16/113 (= 355/113 - 3 donde 355/113 está bastante cerca de pi).

[para continuar, tengo que ir a algún lado]

Reflexionando más, las fracciones continuas son el camino a seguir, sin importar la bisección, excepto para determinar el siguiente término. Más cuando vuelva.

Jason S
fuente
Definitivamente estás en algo aquí. Creo que el enfoque podría ser utilizar el algoritmo general "Estoy pensando en un número entero" para calcular un término de la fracción continua a la vez. No soy un experto en fracciones continuas, pero por lo que deduzco, solo hay muchos términos logarítmicos en la representación, y si este procedimiento funciona, sería una forma de generar cada uno de esos términos uno a la vez usando el tiempo logarítmico para cada uno de ellos. Pensaré esto.
templatetypedef
Sí, estoy completamente de acuerdo: los CF son la respuesta más simple y probablemente la más efectiva, simplemente usando una búsqueda de números enteros para cada término. Iba a poner eso como mi propia respuesta, pero @Jason se me adelantó.
mokus
1
No existe un número racional más cercano bien definido a un real dado (aparte de sí mismo). Lo que está haciendo este enfoque no está muy claro, tal vez necesite más elaboración.
@ Moron: Lea acerca de aproximaciones de fracciones continuas. (por ejemplo, Teoría de los números, Niven y Zuckerman) Forman los números racionales más cercanos para un denominador restringido, es decir, que si p / q es la aproximación de fracción continua de un número real r, entonces | r - (p / q) | <= C / (q ^ 2) donde olvido qué es C, creo que es 1/5 o 1 / sqrt (5).
Jason S
Por ejemplo, ly utener la misma CF hasta un cierto punto, no implica necesariamente que el número al que está adivinando también tiene el mismo convergente ... (si he entendido su enfoque correctamente).
3

Creo que encontré un algoritmo O (log ^ 2 (p + q)).

Para evitar confusiones en el siguiente párrafo, una "consulta" se refiere a cuando el adivino le da al retador una suposición y el retador responde "más grande" o "más pequeño". Esto me permite reservar la palabra "adivinar" para otra cosa, una suposición para p + q que no se le pide directamente al retador.

La idea es encontrar primero p + q, usando el algoritmo que describe en su pregunta: adivine un valor k, si k es demasiado pequeño, duplíquelo y vuelva a intentarlo. Luego, una vez que tenga un límite superior e inferior, realice una búsqueda binaria estándar. Esto requiere consultas O (log (p + q) T), donde T es un límite superior para el número de consultas necesarias para verificar una suposición. Busquemos a T.

Queremos comprobar todas las fracciones r / s con r + s <= k, y duplicar k hasta que k sea lo suficientemente grande. Tenga en cuenta que hay O (k ^ 2) fracciones que debe verificar para un valor dado de k. Construya un árbol de búsqueda binario balanceado que contenga todos estos valores, luego búsquelo para determinar si p / q está en el árbol. Se necesitan consultas O (log k ^ 2) = O (log k) para confirmar que p / q no está en el árbol.

Nunca adivinaremos un valor de k mayor que 2 (p + q). Por tanto, podemos tomar T = O (log (p + q)).

Cuando adivinamos el valor correcto de k (es decir, k = p + q), enviaremos la consulta p / q al retador en el curso de verificar nuestra suposición de k, y ganaremos el juego.

El número total de consultas es entonces O (log ^ 2 (p + q)).

Seth
fuente
En realidad, la construcción del árbol de búsqueda llevará un tiempo de K ^ 2log K. Tal vez debería mejorar este paso para realmente tomar O (log k) tiempo. Además, una vez que tenga un candidato k, debe devolver "más grande / más pequeño", y no solo "existe / no existe". ¿Cómo lo haces?
Eyal Schneider
Por favor ignore la segunda parte de mi comentario anterior;) Si el bucle externo realiza la duplicación, entonces la parte interna debe verificar solo si coincide / no coincide.
Eyal Schneider
Este es un buen algoritmo para # conjeturas que son O (log ^ 2 (p + q)), pero no para la complejidad del tiempo de cálculo O (log ^ 2 (p + q)). ¿Qué tipo de complejidad solicita el OP?
Eyal Schneider
Estoy buscando algo (idealmente) con ambas propiedades. Este es ciertamente un buen comienzo en términos de minimizar el número de consultas, aunque idealmente me gustaría algo que también minimice el cálculo involucrado. Por otra parte, ¡esto podría ser teóricamente óptimo!
templatetypedef
1
@billy: el algoritmo no hace preguntas p + q directamente. Para una k dada, verifica (usando una búsqueda binaria) todas las fracciones r / s con r + s <= k. Si p + q <= k, encuentra la respuesta; de lo contrario, conocemos p + q> k, por lo que duplicamos k.
Seth
3

De acuerdo, creo que descubrí un algoritmo O (lg 2 q) para este problema que se basa en el conocimiento más excelente de Jason S sobre el uso de fracciones continuas. Pensé en desarrollar el algoritmo hasta el final aquí para que tengamos una solución completa, junto con un análisis de tiempo de ejecución.

La intuición detrás del algoritmo es que cualquier número racional p / q dentro del rango se puede escribir como

a 0 + 1 / (a 1 + 1 / (a 2 + 1 / (a 3 + 1 / ...))

Para las elecciones adecuadas de un i . A esto se le llama fracción continua . Más importante aún, aunque estos a i se pueden derivar ejecutando el algoritmo euclidiano en el numerador y denominador. Por ejemplo, supongamos que queremos representar 11/14 de esta manera. Comenzamos señalando que 14 entra en once cero veces, por lo que una aproximación burda de 11/14 sería

0 = 0

Ahora, suponga que tomamos el recíproco de esta fracción para obtener 14/11 = 1 3 / 11 . Entonces si escribimos

0 + (1/1) = 1

Obtenemos una aproximación ligeramente mejor al 14/11. Ahora que nos quedamos con 3/11, podemos tomar el recíproco nuevamente para obtener 11/3 = 3 2 / 3 , por lo que podemos considerar

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

Que es otra buena aproximación al 14/11. Ahora, tenemos 2/3, por lo que considerar el recíproco, que es 3/2 = 1 1 / 2 . Si luego escribimos

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

Obtenemos otra buena aproximación al 14/11. Finalmente, nos queda 1/2, cuyo recíproco es 2/1. Si finalmente escribimos

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

que es exactamente la fracción que queríamos. Además, mire la secuencia de coeficientes que terminamos usando. Si ejecuta el algoritmo euclidiano extendido en 11 y 14, obtiene eso

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

Resulta que (¡usando más matemáticas de las que actualmente sé cómo hacer!) Que esto no es una coincidencia y que los coeficientes en la fracción continua de p / q siempre se forman usando el algoritmo euclidiano extendido. Esto es genial, porque nos dice dos cosas:

  1. Puede haber como máximo O (lg (p + q)) coeficientes, porque el algoritmo euclidiano siempre termina en esta cantidad de pasos, y
  2. Cada coeficiente es como máximo {p, q} como máximo.

Dados estos dos hechos, podemos idear un algoritmo para recuperar cualquier número racional p / q, no solo aquellos entre 0 y 1, aplicando el algoritmo general para adivinar enteros arbitrarios n uno a la vez para recuperar todos los coeficientes en la fracción continua para p / q. Por ahora, sin embargo, solo nos preocuparemos por los números en el rango (0, 1], ya que la lógica para manejar números racionales arbitrarios se puede hacer fácilmente dado esto como una subrutina.

Como primer paso, supongamos que queremos encontrar el mejor valor de a 1 para que 1 / a 1 esté lo más cerca posible de p / qy que 1 sea ​​un número entero. Para hacer esto, simplemente podemos ejecutar nuestro algoritmo para adivinar enteros arbitrarios, tomando el recíproco cada vez. Después de hacer esto, habrá sucedido una de dos cosas. Primero, podríamos descubrir por pura coincidencia que p / q = 1 / k para algún número entero k, en cuyo caso hemos terminado. De lo contrario, encontraremos que p / q se intercala entre 1 / (a 1 - 1) y 1 / a 0 para algunos a 1 . Cuando hacemos esto, comenzamos a trabajar en la fracción continua un nivel más profundo encontrando el a 2 tal que p / q esté entre 1 / (a 2 1 + 1 / a) y 1 / (a 1 + 1 / (a 2 + 1)). Si mágicamente encontramos p / q, ¡genial! De lo contrario, bajamos un nivel más en la fracción continua. Eventualmente, encontraremos el número de esta manera, y no puede tomar mucho tiempo. Cada búsqueda binaria para encontrar un coeficiente toma como máximo O (lg (p + q)) tiempo, y hay como máximo O (lg (p + q)) niveles para la búsqueda, por lo que solo necesitamos O (lg 2 (p + q)) operaciones aritméticas y sondeos para recuperar p / q.

Un detalle que quiero señalar es que necesitamos hacer un seguimiento de si estamos en un nivel impar o en un nivel par cuando hacemos la búsqueda porque cuando intercalamos p / q entre dos fracciones continuas, necesitamos saber si el coeficiente que estábamos buscando era la fracción superior o la inferior. Declararé sin pruebas que para una i con una i impar, desea usar la parte superior de los dos números y con una i par, usa la menor de los dos números.

Estoy casi 100% seguro de que este algoritmo funciona. Voy a intentar escribir una prueba más formal de esto en la que llenaré todos los vacíos en este razonamiento, y cuando lo haga, publicaré un enlace aquí.

Gracias a todos por contribuir con los conocimientos necesarios para que esta solución funcione, especialmente a Jason S por sugerir una búsqueda binaria sobre fracciones continuas.

templatetypedef
fuente
Acabo de ver esto, no he tenido la oportunidad de leerlo detenidamente, pero probablemente tenga razón.
Jason S
... aunque creo que es log (q), no log ^ 2 (q).
Jason S
Creo que esto es correcto. Para una prueba, vea mi comentario a la primera respuesta de Jason.
De hecho, creo que tenemos una prueba de que es O (log q). Vea mi comentario a la segunda respuesta de Jason.
2

Recuerde que cualquier número racional en (0, 1) se puede representar como una suma finita de fracciones unitarias distintas (positivas o negativas). Por ejemplo, 2/3 = 1/2 + 1/6 y 2/5 = 1/2 - 1/10. Puede usar esto para realizar una búsqueda binaria sencilla.

Mick
fuente
2
¿Podrías explicar cómo usaría el algoritmo este hecho?
Seth
¿Estás hablando de fracciones egipcias?
Gabe
2

Aquí hay otra forma de hacerlo. Si hay suficiente interés, intentaré completar los detalles esta noche, pero no puedo ahora porque tengo responsabilidades familiares. Aquí hay un fragmento de una implementación que debería explicar el algoritmo:

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)

Y aquí está la explicación. Lo que best_continued_fraction(x, bound)debe hacer es encontrar la última aproximación de fracción continua xcon el denominador como máximo bound. Este algoritmo tomará pasos de polylog para completar y encuentra muy buenas (aunque no siempre las mejores) aproximaciones. Entonces para cadabound obtendremos algo parecido a una búsqueda binaria a través de todas las fracciones posibles de ese tamaño. Ocasionalmente no encontraremos una fracción en particular hasta que aumentemos el límite más de lo debido, pero no estaremos muy lejos.

Así que ahí lo tienes. Número logarítmico de preguntas encontradas con el trabajo polylog.

Actualización: Y código de trabajo completo.

#! /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])

Parece un poco más eficiente en las conjeturas que la solución anterior y realiza muchas menos operaciones. Para 101/1024 requirió 19 conjeturas y 251 operaciones. Para .98765 necesitó 27 suposiciones y 623 operaciones. Para 0.0123456789 requirió 66 suposiciones y 889 operaciones. Y para risitas y sonrisas, para 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (eso es 10 copias del anterior) requirió 665 suposiciones y 23289 operaciones.

tímidamente
fuente
@ jason-s: Es mejor completarlo ahora. Espero poder compararlo con el suyo cuando tenga código. El tuyo definitivamente requerirá menos operaciones, no tengo sentido de quién requerirá menos conjeturas.
Btilly
0

Puede ordenar números racionales en un intervalo dado, por ejemplo, por el par (denominador, numerador). Entonces para jugar el juego puedes

  1. Encuentre el intervalo [0, N]utilizando el método de duplicación
  2. Dado un intervalo, [a, b]apunte al racional con el denominador más pequeño en el intervalo más cercano al centro del intervalo.

Sin embargo, esto probablemente sea todavía O(log(num/den) + den)(no estoy seguro y es demasiado temprano en la mañana aquí para hacerme pensar con claridad ;-))

6502
fuente