Das "Rate die Zahl" -Spiel für beliebige rationale Zahlen?

77

Als Interviewfrage habe ich einmal folgendes bekommen:

Ich denke an eine positive ganze Zahl n. Überlegen Sie sich einen Algorithmus, der dies in O (lg n) -Abfragen erraten kann. Jede Anfrage ist eine Nummer Ihrer Wahl, und ich werde entweder "niedriger", "höher" oder "richtig" antworten.

Dieses Problem kann durch eine modifizierte binäre Suche gelöst werden, bei der Sie Zweierpotenzen auflisten, bis Sie eine finden, die n überschreitet, und dann eine standardmäßige binäre Suche über diesen Bereich ausführen. Was ich daran so cool finde, ist, dass Sie einen unendlichen Raum schneller nach einer bestimmten Zahl durchsuchen können als nur Brute-Force.

Die Frage, die ich habe, ist jedoch eine geringfügige Änderung dieses Problems. Angenommen, ich wähle eine beliebige rationale Zahl zwischen Null und Eins, anstatt eine positive ganze Zahl zu wählen . Meine Frage ist: Mit welchem ​​Algorithmus können Sie am effizientesten bestimmen, welche rationale Zahl ich ausgewählt habe?

Im Moment kann die beste Lösung, die ich habe, p / q in höchstens O (q) Zeit finden, indem ich implizit über den Stern-Brocot-Baum gehe , einen binären Suchbaum über alle Rationalen. Ich hatte jedoch gehofft, eine Laufzeit näher an die Laufzeit heranzuführen, die wir für den ganzzahligen Fall erhalten haben, vielleicht so etwas wie O (lg (p + q)) oder O (lg pq). Kennt jemand einen Weg, um diese Art von Laufzeit zu bekommen?

Ich habe anfangs überlegt, eine Standard-Binärsuche des Intervalls [0, 1] zu verwenden, aber dies wird nur rationale Zahlen mit einer sich nicht wiederholenden binären Darstellung finden, bei der fast alle Rationalen fehlen. Ich habe auch darüber nachgedacht, die Rationalitäten auf andere Weise aufzuzählen, aber ich kann keinen Weg finden, diesen Raum zu durchsuchen, wenn ich nur größere / gleiche / kleinere Vergleiche mache.

algorithm math puzzle rational-numbers templatetypedef
quelle
3
Sie wissen, dass dies ohne Einschränkungen unmöglich ist, da es in jedem Bereich unendlich viele rationale Zahlen gibt? Sie können auch nicht wirklich nach einer unbegrenzten Ganzzahl suchen. Angenommen, die Zahl war eine Zufallszahl mit 10 ^ 1000 Stellen? "100" - "höher". "1000" - "höher". "Eine Million" - "höher". "Eine Billion?" "Höher." "Ein Googol ?" "Höher!"
Tom Zych
16
@Tom - Bei einer beliebigen Zahl (z. B. 10 ^ 1000) findet der Algorithmus diese in einer begrenzten Zeitspanne (auch wenn es sich um eine sehr lange Zeit handelt). Dies unterscheidet sich von der Aussage, dass der Algorithmus eine beliebige Zahl innerhalb von t Schritten erraten kann (für einen festen Wert von t), aber niemand hat diese Behauptung aufgestellt.
Seth
6
@ Tom Zych- Wenn Sie eine endliche ganze Zahl auswählen, kann ich sie schließlich durch wiederholtes Verdoppeln finden. Es mag lächerlich lange dauern, aber ich kann es trotzdem in einer Zeit tun, die proportional zum Logarithmus Ihrer Zahl ist. Dabei gehe ich davon aus, dass die Person, die die Fragen beantwortet, die Zahl ehrlich darstellt und nicht nur ausweicht, indem sie auf eine Weise antwortet, die niemals endet.
Templatetypedef
Interessanter Algorithmus. Alle Rationalen mit dem Nenner N befinden sich vor (oder in) der Ebene N des Baumes, so dass O (q) eindeutig möglich ist
Dr. belisarius
4
@Everyone: Ich möchte nur sagen, dass dies eine interessante Frage mit einigen netten Antworten und Diskussionen war. Mein innerer Mathe-Nerd ist glücklich.
Seth

Antworten:

49

Okay, hier ist meine Antwort, wenn ich nur fortgesetzte Brüche verwende .

Lassen Sie uns zuerst eine Terminologie hier bekommen.

Sei X = p / q der unbekannte Bruch.

Sei Q (X, p / q) = Vorzeichen (X - p / q) die Abfragefunktion: Wenn es 0 ist, haben wir die Zahl erraten, und wenn es +/- 1 ist, sagt es uns das Vorzeichen unseres Fehlers .

Die herkömmliche Notation für fortgesetzte Brüche lautet 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 ) ...))

Wir folgen dem folgenden Algorithmus für 0 <p / q <1.

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

  2. Äußere Schleife : Die Voraussetzungen sind:

    • Y und Z sind fortgesetzte Brüche von k + 1 Termen, die identisch sind, außer im letzten Element, wo sie sich um 1 unterscheiden, so dass Y = [y 0 ; y 1 , y 2 , y 3 , ... y k ] und Z = [y 0 ; y 1 , y 2 , y 3 , ... y k + 1]

    • (-1) k (YX) <0 <(-1) k (ZX) oder einfacher ausgedrückt für k gerade, Y <X <Z und für k ungerade, Z <X <Y.

  3. Erweitern Sie den Grad der fortgesetzten Fraktion um 1 Schritt, ohne die Werte der Zahlen zu ändern. Wenn die letzten Terme y k und y k + 1 sind, ändern wir dies im Allgemeinen in [... y k , y k + 1 = ∞] und [... y k , z k + 1 = 1]. Erhöhen Sie nun k um 1.

  4. Innere Schleifen : Dies entspricht im Wesentlichen der Interviewfrage von @ templatetypedef zu den ganzen Zahlen. Wir führen eine zweiphasige binäre Suche durch, um näher zu kommen:

  5. Innere Schleife 1 : y k = ∞, z k = a und X liegt zwischen Y und Z.

  6. Double Zs letzter Term: Berechne M = Z, aber mit m k = 2 * a = 2 * z k .

  7. Fragen Sie die unbekannte Nummer ab: q = Q (X, M).

  8. Wenn q = 0 ist, haben wir unsere Antwort und fahren mit Schritt 17 fort.

  9. Wenn q und Q (X, Y) entgegengesetzte Vorzeichen haben, bedeutet dies, dass X zwischen Y und M liegt. Setzen Sie also Z = M und fahren Sie mit Schritt 5 fort.

  10. Andernfalls setzen Sie Y = M und fahren Sie mit dem nächsten Schritt fort:

  11. Innere Schleife 2. y k = b, z k = a und X liegt zwischen Y und Z.

  12. Wenn sich a und b um 1 unterscheiden, tauschen Sie Y und Z aus und fahren Sie mit Schritt 2 fort.

  13. Führen Sie eine binäre Suche durch: Berechnen Sie M mit m k = Etage ((a + b) / 2) und fragen Sie q = Q (X, M) ab.

  14. Wenn q = 0 ist, sind wir fertig und fahren mit Schritt 17 fort.

  15. Wenn q und Q (X, Y) entgegengesetzte Vorzeichen haben, bedeutet dies, dass X zwischen Y und M liegt. Setzen Sie also Z = M und fahren Sie mit Schritt 11 fort.

  16. Andernfalls haben q und Q (X, Z) entgegengesetzte Vorzeichen. Dies bedeutet, dass X zwischen Z und M liegt. Setzen Sie also Y = M und fahren Sie mit Schritt 11 fort.

  17. Fertig: X = M.

Ein konkretes Beispiel für 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!

Bei jedem Schritt der Berechnung von M verringert sich der Bereich des Intervalls. Es ist wahrscheinlich ziemlich einfach zu beweisen (obwohl ich das nicht tun werde), dass sich das Intervall bei jedem Schritt um einen Faktor von mindestens 1 / sqrt (5) verringert, was zeigen würde, dass dieser Algorithmus O (log q) Schritte ist.

Beachten Sie, dass dies mit der ursprünglichen Interviewfrage von templatetypedef kombiniert werden kann und auf jede rationale Zahl p / q angewendet werden kann , nicht nur zwischen 0 und 1, indem zuerst Q (X, 0) berechnet wird, dann für entweder positive / negative ganze Zahlen, die zwischen zwei aufeinanderfolgenden liegen Ganzzahlen und dann Verwendung des obigen Algorithmus für den Bruchteil.

Wenn ich das nächste Mal eine Chance habe, werde ich ein Python-Programm veröffentlichen, das diesen Algorithmus implementiert.

Bearbeiten : Beachten Sie auch, dass Sie nicht für jeden Schritt den fortgesetzten Bruch berechnen müssen (dies wäre O (k). Es gibt teilweise Annäherungen an fortgesetzte Brüche, mit denen der nächste Schritt aus dem vorherigen Schritt in O (1) berechnet werden kann. )

edit 2 : Rekursive Definition von partiellen Approximanten:

Wenn A k = [a 0 ; a 1 , a 2 , a 3 , ... a k ] = p k / q k , dann p k = a k p k-1 + p k-2 und q k = a k q k-1 + q k-2 . (Quelle: Niven & Zuckerman, 4. Auflage, Theoreme 7.3-7.5. Siehe auch Wikipedia )

Beispiel: [0] = 0/1 = p 0 / q 0 , [0; 7] = 1/7 = p 1 / q 1 ; also [0; 7, 16] = (16 · 1 + 0) / (16 · 7 + 1) = 16/113 = p 2 / q 2 .

Dies bedeutet, dass wenn zwei fortgesetzte Brüche Y und Z mit Ausnahme des letzten die gleichen Terme haben und der fortgesetzte Bruch ohne den letzten Term p k-1 / q k-1 ist , wir Y = (y k p k- schreiben können) 1 + p k-2 ) / (y k q k-1 + q k-2 ) und Z = (z k p k-1 + p k-2 ) / (z k q k-1 + q k-2) ). Daraus sollte gezeigt werden können, dass | YZ | nimmt in jedem kleineren Intervall, das von diesem Algorithmus erzeugt wird, um mindestens den Faktor 1 / sqrt (5) ab, aber die Algebra scheint mir im Moment ein Rätsel zu sein. :-(

Hier ist mein Python-Programm:

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]

und eine Beispielausgabe für 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

Da Python von Anfang an mit Biginteger-Mathematik umgeht und dieses Programm nur Integer-Mathematik verwendet (mit Ausnahme der Intervallberechnungen), sollte es für beliebige Rationals funktionieren.

edit 3 : Umriss des Beweises, dass dies O (log q) ist, nicht O (log ^ 2 q):

Beachten Sie zunächst, dass die Anzahl der Schritte n k für jeden neuen fortgesetzten Bruchterm genau 2b (a_k) -1 beträgt, bis die rationale Zahl gefunden ist, wobei b (a_k) die Anzahl der Bits ist, die zur Darstellung von a_k = lid (log2 (a_k) benötigt werden )): Es sind b (a_k) Schritte, um das "Netz" der binären Suche zu erweitern, und b (a_k) -1 Schritte, um es einzugrenzen). Im obigen Beispiel werden Sie feststellen, dass die Anzahl der Schritte immer 1, 3, 7, 15 usw. beträgt.

Jetzt können wir die Wiederholungsrelation q k = a k q k-1 + q k-2 und die Induktion verwenden, um das gewünschte Ergebnis zu beweisen.

Sagen wir es so: Der Wert von q nach den Schritten N k = Summe (n k ), die zum Erreichen des k-ten Terms erforderlich sind, hat ein Minimum: q> = A * 2 cN für einige feste Konstanten A, c. (Um zu invertieren, würden wir erhalten, dass die Anzahl der Schritte N <= (1 / c) * log 2 (q / A) = O (log q) ist.)

Basisfälle:

  • k = 0: q = 1, N = 0, also q> = 2 N.
  • k = 1: für N = 2b-1 Schritte ist q = a 1 > = 2 b-1 = 2 (N-1) / 2 = 2 N / 2 / sqrt (2).

Dies impliziert, dass A = 1, c = 1/2 die gewünschten Grenzen liefern könnte. In der Realität kann q nicht jeden Term verdoppeln (Gegenbeispiel: [0; 1, 1, 1, 1, 1] hat einen Wachstumsfaktor von phi = (1 + sqrt (5)) / 2), also verwenden wir c = 1 / 4.

Induktion:

  • für den Term k ist q k = a k q k-1 + q k-2 . Wiederum ist für die für diesen Term benötigten n k = 2b-1 Schritte a k > = 2 b-1 = 2 (n k -1) / 2 .

    Also ist 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 / sqrt (2) * 2 n k / 4 .

Argh - der schwierige Teil hier ist, dass wenn a k = 1 ist, q für diesen einen Term möglicherweise nicht viel zunimmt und wir q k-2 verwenden müssen, aber das kann viel kleiner als q k-1 sein .

Jason S.
quelle
Das sieht also wirklich gut aus, aber ich denke nicht, dass es O ist (lg q). Jede einzelne Iteration der inneren Schleife wird in O (lg q) -Schritten ausgeführt, während Sie die modifizierte binäre Suche verwenden, um die nächste Nummer des fortgesetzten Bruchs wiederherzustellen. Beachten Sie jedoch, dass es O (lg q) -Iterationen dieser Schleife gibt, da es ( im schlimmsten Fall) O (lg q) Zahlen in der Teilfraktion. Das lässt mich denken, dass dies stattdessen O (lg ^ 2 q) Zeit ist. Dies ist jedoch immer noch eine ausgezeichnete Lösung für das Problem, und ob es nun O (lg q) oder O (lg ^ 2 q) ist, es ist immer noch exponentiell besser als das, was ich vorher hatte.
Templatetypedef
Ich weiß, dass es wegen der beiden Schleifen wie O (lg ^ 2 q) aussieht, aber das ist wahrscheinlich konservativ. Ich werde versuchen, es zu beweisen.
Jason S
+1: Ich habe die Details nicht überprüft, aber ich glaube jetzt, dass der CF-Ansatz funktionieren wird.
Sie müssen versuchen, das | YZ | zu zeigen nimmt geometrisch ab. Wie typedeftemplate in seiner Antwort erwähnt, gibt es in der CF O (log q) Terme, von denen jeder höchstens q hat. Wenn Sie also O (log q) Schritte ausführen, um den 'Grad' Ihrer CF um 1 zu erhöhen, führen Sie insgesamt O (log ^ 2 q) Schritte aus.
Nein, Sie können es aufgrund der beiden Schleifen nicht als O (log ^ 2 q) auswerten. das ist überkonservativ. Wenn Sie O (log q) Schritte ausführen, um die Anzahl der Terme des fortgesetzten Bruchs zu erhöhen, ist der Term dieses Bruchs sehr groß und das Intervall ist sehr klein. Jede Iteration der inneren Schleife verringert auch das Intervall, nicht nur die Zunahme der fortgesetzten Bruchlänge.
Jason S
6

Nehmen wir die rationalen Zahlen in reduzierter Form und schreiben sie zuerst in der Reihenfolge Nenner, dann Zähler auf.

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

Unsere erste Vermutung wird sein 1/2. Dann gehen wir die Liste durch, bis wir 3 in unserem Sortiment haben. Dann werden wir 2 Vermutungen anstellen, um diese Liste zu durchsuchen. Dann gehen wir die Liste durch, bis wir 7 in unserem verbleibenden Bereich haben. Dann werden wir 3 Vermutungen anstellen, um diese Liste zu durchsuchen. Und so weiter.

In nSchritten werden wir die ersten Möglichkeiten behandeln, die in der Größenordnung der Effizienz liegen, nach der Sie gesucht haben.2O(n)

Update: Die Leute haben die Gründe dafür nicht verstanden. Die Argumentation ist einfach. Wir wissen, wie man einen Binärbaum effizient durchläuft. Es gibt Brüche mit maximalem Nenner . Wir könnten daher schrittweise nach einer bestimmten Nennergröße suchen . Das Problem ist, dass wir unendlich viele mögliche Gründe für die Suche haben. Wir können sie also nicht einfach alle aneinanderreihen, bestellen und mit der Suche beginnen.O(n2)nO(2*log(n)) = O(log(n))

Daher war meine Idee, ein paar aufzustellen, zu suchen, mehr aufzustellen, zu suchen und so weiter. Jedes Mal, wenn wir uns mehr anstellen, stellen wir uns ungefähr doppelt so auf wie beim letzten Mal. Wir brauchen also eine Vermutung mehr als beim letzten Mal. Daher verwendet unser erster Durchgang 1 Vermutung, um 1 mögliche rationale zu durchqueren. Unsere zweite verwendet 2 Vermutungen, um 3 mögliche Rationalitäten zu durchlaufen. Unser dritter verwendet 3 Vermutungen, um 7 mögliche Rationalitäten zu durchlaufen. Und unser k'th verwendet kVermutungen, um mögliche Rationalitäten zu durchqueren . Für einen bestimmten Rational wird es schließlich dazu führen, dass dieser Rational auf eine ziemlich große Liste gesetzt wird, auf der er weiß, wie man eine binäre Suche effizient durchführt.2k-1m/n

Wenn wir binäre Suchen durchgeführt und dann alles ignoriert hätten, was wir gelernt hatten, als wir mehr Rationals ergriffen hatten, dann hätten wir alle Rationals auf Pässe gesetzt und m/nin O(log(n))Pässe aufgenommen. (Das liegt daran, dass wir zu diesem Zeitpunkt zu einem Durchgang mit genügend Rationalen gelangen, um jeden Rational bis einschließlich m/neinzuschließen.) Aber jeder Durchgang erfordert mehr Vermutungen, das wären also Vermutungen.O(log(n)2)

Allerdings machen wir es tatsächlich viel besser. Mit unserer ersten Vermutung eliminieren wir die Hälfte der Rationals auf unserer Liste als zu groß oder zu klein. Unsere nächsten beiden Vermutungen teilen den Raum nicht ganz in Viertel, aber sie kommen nicht zu weit davon entfernt. Unsere nächsten drei Vermutungen schneiden den Raum nicht ganz in Achtel, aber sie kommen nicht zu weit davon entfernt. Und so weiter. Wenn Sie es zusammenstellen, bin ich überzeugt, dass das Ergebnis ist, dass Sie m/nin O(log(n))Schritten finden. Obwohl ich eigentlich keinen Beweis habe.

Probieren Sie es aus: Hier ist Code, um die Vermutungen zu generieren, damit Sie spielen und sehen können, wie effizient es ist.

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

Als Beispiel zum Ausprobieren habe ich 101/1024 (0.0986328125) ausprobiert und festgestellt, dass 20 Vermutungen erforderlich waren, um die Antwort zu finden. Ich habe 0.98765 ausprobiert und es dauerte 45 Vermutungen. Ich habe 0.0123456789 ausprobiert und es brauchte 66 Vermutungen und ungefähr eine Sekunde, um sie zu generieren. (Wenn Sie das Programm mit einer rationalen Nummer als Argument aufrufen, werden alle Vermutungen für Sie ausgefüllt. Dies ist eine sehr hilfreiche Annehmlichkeit.)

Übrigens
quelle
Ich bin mir nicht sicher, ob ich verstehe, was du sagst. Können Sie das klarstellen?
Templatetypedef
@templatetypedef: Was ist unklar? Unsere erste Vermutung ist immer 1/2. Angenommen, die Antwort kommt niedriger zurück. Die nächsten 3 Zahlen auf der Liste, die der Bedingung entsprechen 1/3, sind 1/4und 1/5. Also raten wir als 1/4nächstes entweder 1/3oder 1/5auf die folgende Vermutung. Wenn wir fortfahren, nehmen wir 7 Zahlen in unserem Bereich und stellen die nächsten 3 Vermutungen auf. Danach schnappen wir uns 15 und stellen die nächsten 4 Vermutungen auf. etc. Was ist daran unklar? Ich werde jetzt ins Bett gehen. Wenn Sie morgens immer noch nicht verstehen, schreibe ich ein Programm, um zu raten, und Sie können sehen, wie es funktioniert.
Btilly
3
@btilly: Woher kommen die 7-3, 15-4 (31-5?)? Was ist die Logik hinter einer solchen Warteschlange von "rate-next" -Nummern?
stakx - nicht mehr beitragen
2
@Btilly: +1, aber es sieht so aus, als hätten Sie das Hauptproblem nicht wirklich gelöst . Sie generieren Theta (q) -Rationalen und führen eine binäre Suche über diese durch. Die Laufzeit ist also Omega (q), obwohl Sie O-Abfragen (log ^ 2 q) annehmen. In der Tat hat Seth einen sehr ähnlichen Algorithmus (und wenn Sie sorgfältig zu lesen, er ist nicht die Abfrage für p + q). IMO, das Hauptproblem, das hier gelöst werden muss, ist die Erzeugung von O-Rationalen (Polylog (q)), anstatt zu versuchen, die Anzahl der Abfragen O (Polylog (q)) unabhängig vom anderen Buchhaltungsaufwand beizubehalten.
1
@ Seth: Es ist btilly, nicht billy :-) q oder p + q, spielt keine Rolle, da p <q.
4

Ich habe es! Was Sie tun müssen, ist eine parallele Suche mit Halbierung und fortgesetzten Brüchen .

Die Halbierung gibt Ihnen eine Grenze für eine bestimmte reelle Zahl, die als Zweierpotenz dargestellt wird, und fortgesetzte Brüche nehmen die reelle Zahl und finden die nächste rationale Zahl.

Wie Sie sie parallel ausführen, ist wie folgt.

Bei jedem Schritt haben lund usind Sie die untere und obere Grenze der Halbierung. Die Idee ist, dass Sie die Wahl haben, den Halbierungsbereich zu halbieren und einen zusätzlichen Term als fortgesetzte Bruchdarstellung hinzuzufügen. Wenn beide lund udenselben nächsten Begriff als fortgesetzte Fraktion haben, führen Sie den nächsten Schritt in der Suche nach fortgesetzten Brüchen aus und führen eine Abfrage unter Verwendung der fortgesetzten Fraktion durch. Andernfalls halbieren Sie den Bereich mithilfe der Halbierung.

Da beide Methoden den Nenner um mindestens einen konstanten Faktor erhöhen (die Halbierung erfolgt um den Faktor 2, die fortgesetzten Brüche um mindestens den Faktor phi = (1 + sqrt (5)) / 2), bedeutet dies, dass Ihre Suche O sein sollte (log (q)). (Es kann wiederholt fortgesetzte Fraktionsberechnungen geben, so dass es als O enden kann (log (q) ^ 2).)

Unsere fortgesetzte Suche nach Brüchen muss auf die nächste Ganzzahl gerundet werden und darf nicht den Boden verwenden (dies ist unten klarer).

Das obige ist irgendwie handgewellt. Verwenden wir ein konkretes Beispiel für r = 1/31:

  1. l = 0, u = 1, Abfrage = 1/2. 0 kann nicht als fortgesetzter Bruch ausgedrückt werden, daher verwenden wir die binäre Suche bis l! = 0.

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

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

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

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

  6. l = 1/32, u = 1/16. Jetzt 1 / l = 32, 1 / u = 16, diese haben unterschiedliche cfrac-Wiederholungen, also halbieren Sie weiter., Abfrage = 3/64.

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

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

  9. l = 1/32, u = 9/256, Abfrage = 17/512 = 1 / 30.1176 ... (rund auf 1/30)

  10. l = 1/32, u = 17/512, Abfrage = 33/1024 = 1 / 31.0303 ... (rund auf 1/31)

  11. l = 33/1024, u = 17/512, Abfrage = 67/2048 = 1 / 30.5672 ... (rund auf 1/31)

  12. l = 33/1024, u = 67/2048. Zu diesem Zeitpunkt haben sowohl l als auch u den gleichen fortgesetzten Bruchterm 31, daher verwenden wir jetzt eine fortgesetzte Bruchschätzung. Abfrage = 1/31.

ERFOLG!

Für ein anderes Beispiel verwenden wir 16/113 (= 355/113 - 3, wobei 355/113 ziemlich nahe an pi liegt).

[um fortzufahren, muss ich irgendwohin gehen]

Bei weiterer Überlegung sind fortgesetzte Brüche der richtige Weg, unabhängig von der Halbierung, außer um den nächsten Term zu bestimmen. Mehr, wenn ich zurückkomme.

Jason S.
quelle
Sie sind definitiv auf etwas hier. Ich denke, der Ansatz könnte darin bestehen, den allgemeinen Algorithmus "Ich denke an eine ganze Zahl" zu verwenden, um jeweils einen Term des fortgesetzten Bruchs zu berechnen. Ich bin kein Experte für fortgesetzte Brüche, aber soweit ich weiß, enthält die Darstellung nur logarithmisch viele Begriffe. Wenn dieses Verfahren funktioniert, ist es eine Möglichkeit, jeden dieser Begriffe einzeln mit logarithmischer Zeit für jeden der Begriffe zu generieren Sie. Ich werde darüber nachdenken.
Templatetypedef
Ja, ich stimme vollkommen zu - CFs sind die einfachste und wahrscheinlich effektivste Antwort, indem nur eine ganzzahlige Suche für jeden Begriff verwendet wird. Ich wollte das als meine eigene Antwort setzen, aber @Jason hat mich geschlagen.
Mokus
1
Es gibt keine genau definierte rationale Zahl , die einem gegebenen Real am nächsten kommt (außer sich selbst). Was dieser Ansatz bewirkt, ist nicht sehr klar, vielleicht muss er genauer ausgearbeitet werden.
@Moron: Informieren Sie sich über fortgesetzte Bruchannäherungen. (zB Theory of Numbers, Niven & Zuckerman) Sie bilden die nächsten rationalen Zahlen für einen beschränkten Nenner, nämlich dass, wenn p / q die fortgesetzte Bruchnäherung einer reellen Zahl r ist, | r - (p / q) | <= C / (q ^ 2) wo ich vergesse, was C ist, denke ich, dass es entweder 1/5 oder 1 / sqrt (5) ist.
Jason S
Wenn Sie beispielsweise lbis zu ueinem gewissen Punkt dieselbe CF haben, bedeutet dies nicht unbedingt, dass die von Ihnen erratene Zahl auch dieselbe Konvergenz aufweist ... (wenn ich Ihren Ansatz richtig verstanden habe).
3

Ich glaube, ich habe einen O-Algorithmus (log ^ 2 (p + q)) gefunden.

Um Verwirrung im nächsten Absatz zu vermeiden, bezieht sich eine "Abfrage" darauf, wenn der Vermesser dem Herausforderer eine Vermutung gibt und der Herausforderer "größer" oder "kleiner" antwortet. Dies ermöglicht mir, das Wort "Vermutung" für etwas anderes zu reservieren, eine Vermutung für p + q, die nicht direkt an den Herausforderer gestellt wird.

Die Idee ist, zuerst p + q mit dem Algorithmus zu finden, den Sie in Ihrer Frage beschrieben haben: Erraten Sie einen Wert k, wenn k zu klein ist, verdoppeln Sie ihn und versuchen Sie es erneut. Sobald Sie eine Ober- und Untergrenze haben, führen Sie eine standardmäßige binäre Suche durch. Dies erfordert O-Abfragen (log (p + q) T), wobei T eine Obergrenze für die Anzahl der Abfragen ist, die zum Überprüfen einer Vermutung erforderlich sind. Lassen Sie uns T. finden.

Wir wollen alle Brüche r / s mit r + s <= k überprüfen und k verdoppeln, bis k ausreichend groß ist. Beachten Sie, dass es O (k ^ 2) -Fraktionen gibt, die Sie auf einen bestimmten Wert von k prüfen müssen. Erstellen Sie einen ausgeglichenen binären Suchbaum, der alle diese Werte enthält, und durchsuchen Sie ihn, um festzustellen, ob sich p / q im Baum befindet. Es sind Abfragen von O (log k ^ 2) = O (log k) erforderlich, um zu bestätigen, dass p / q nicht im Baum enthalten ist.

Wir werden niemals einen Wert von k größer als 2 (p + q) erraten. Daher können wir T = O (log (p + q)) nehmen.

Wenn wir den richtigen Wert für k erraten (dh k = p + q), senden wir die Abfrage p / q an den Herausforderer, während wir unsere Vermutung für k überprüfen, und gewinnen das Spiel.

Die Gesamtzahl der Abfragen beträgt dann O (log ^ 2 (p + q)).

Seth
quelle
Das eigentliche Erstellen des Suchbaums dauert K ^ 2log K Zeit. Vielleicht sollten Sie diesen Schritt verbessern, um sich wirklich Zeit für O (log k) zu nehmen. Sobald Sie einen Kandidaten k haben, sollten Sie "größer / kleiner" dafür zurückgeben und nicht nur "existiert / existiert nicht". Wie machst du das?
Eyal Schneider
Bitte ignorieren Sie den zweiten Teil meines vorherigen Kommentars;) Wenn die äußere Schleife die Verdoppelung durchführt, muss der innere Teil nur auf Übereinstimmung / keine Übereinstimmung prüfen.
Eyal Schneider
Dies ist ein netter Algorithmus für # Vermutungen, die O sind (log ^ 2 (p + q)), aber nicht für die Komplexität der Rechenzeit O (log ^ 2 (p + q)). Welche Art von Komplexität fordert das OP an?
Eyal Schneider
Ich suche etwas (idealerweise) mit beiden Eigenschaften. Dies ist sicherlich ein guter Anfang, um die Anzahl der Abfragen zu minimieren, obwohl ich im Idealfall etwas möchte, das auch die damit verbundene Berechnung minimiert. Andererseits könnte dies theoretisch optimal sein!
Templatetypedef
1
@billy: Der Algorithmus stellt keine direkten p + q-Fragen. Für ein gegebenes k werden (unter Verwendung einer binären Suche) alle Brüche r / s mit r + s <= k überprüft. Wenn p + q <= k ist, findet es die Antwort; ansonsten kennen wir p + q> k, also verdoppeln wir k.
Seth
3

Okay, ich denke, ich habe einen O (lg 2 q) -Algorithmus für dieses Problem gefunden, der auf Jason S 'bester Einsicht über die Verwendung fortgesetzter Brüche basiert. Ich dachte, ich würde den Algorithmus genau hier ausarbeiten, damit wir eine vollständige Lösung zusammen mit einer Laufzeitanalyse haben.

Die Intuition hinter dem Algorithmus ist, dass jede rationale Zahl p / q innerhalb des Bereichs als geschrieben werden kann

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

Für geeignete Auswahlmöglichkeiten eines i . Dies wird als fortgesetzte Fraktion bezeichnet . Noch wichtiger ist, dass diese a i abgeleitet werden können, indem der euklidische Algorithmus auf dem Zähler und Nenner ausgeführt wird. Angenommen, wir möchten 11/14 auf diese Weise darstellen. Wir beginnen mit der Feststellung, dass 14 in elf Nullen geht, also wäre eine grobe Annäherung von 11/14

0 = 0

Nun sei angenommen , dass wir den reziproken Wert dieser Fraktion nehmen zu 14/11 = 1 zu erhalten 3 / 11 . Also wenn wir schreiben

0 + (1/1) = 1

Wir erhalten eine etwas bessere Annäherung an den 14.11. Nun , da wir mit 3/11 links sind, können wir die gegenseitige nehmen wieder 11/3 = 3 zu erhalten 2 / 3 , so dass wir betrachten können ,

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

Welches ist eine weitere gute Annäherung an 11/14. Jetzt haben wir zwei Drittel, also die gegenseitigen betrachten, die 3/2 = 1 1 / 2 . Wenn wir dann schreiben

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

Wir bekommen eine weitere gute Annäherung an den 14.11. Schließlich bleibt uns 1/2 übrig, dessen Kehrwert 2/1 ist. Wenn wir endlich schreiben

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

Das ist genau der Bruchteil, den wir wollten. Schauen Sie sich außerdem die Folge der Koeffizienten an, die wir letztendlich verwendet haben. Wenn Sie den erweiterten euklidischen Algorithmus auf 11 und 14 ausführen, erhalten Sie das

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

Es stellt sich heraus, dass (mit mehr Mathematik als ich derzeit weiß!) Dies kein Zufall ist und dass die Koeffizienten im fortgesetzten Bruchteil von p / q immer unter Verwendung des erweiterten euklidischen Algorithmus gebildet werden. Das ist großartig, weil es uns zwei Dinge sagt:

  1. Es kann höchstens O (lg (p + q)) Koeffizienten geben, da der euklidische Algorithmus immer in diesen vielen Schritten endet, und
  2. Jeder Koeffizient ist höchstens max {p, q}.

Angesichts dieser beiden Tatsachen können wir einen Algorithmus entwickeln, um jede rationale Zahl p / q wiederherzustellen, nicht nur jene zwischen 0 und 1, indem wir den allgemeinen Algorithmus anwenden, um beliebige ganze Zahlen n einzeln zu erraten, um alle Koeffizienten in wiederherzustellen die fortgesetzte Fraktion für p / q. Im Moment werden wir uns jedoch nur um Zahlen im Bereich (0, 1] kümmern, da die Logik für den Umgang mit beliebigen rationalen Zahlen leicht gemacht werden kann, wenn dies als Unterprogramm verwendet wird.

Nehmen wir als ersten Schritt an, wir wollen den besten Wert einer 1 finden, damit 1 / a 1 so nah wie möglich an p / q liegt und a 1 eine ganze Zahl ist. Zu diesem Zweck können wir einfach unseren Algorithmus zum Erraten beliebiger Ganzzahlen ausführen und jedes Mal den Kehrwert verwenden. Danach ist eines von zwei Dingen passiert. Erstens könnten wir zufällig feststellen, dass p / q = 1 / k für eine ganze Zahl k ist. In diesem Fall sind wir fertig. Wenn nicht, werden wir feststellen, dass p / q für einige a 1 zwischen 1 / (a 1 - 1) und 1 / a 0 liegt . Wenn wir dies tun, beginnen wir mit der Arbeit an der fortgesetzten Fraktion eine Ebene tiefer, indem wir die a 2 so finden, dass p / q zwischen 1 / (a 1 + 1 / a liegt2 ) und 1 / (a 1 + 1 / (a 2 + 1)). Wenn wir p / q auf magische Weise finden, ist das großartig! Andernfalls gehen wir in der fortgesetzten Fraktion eine Ebene weiter nach unten. Schließlich werden wir die Nummer auf diese Weise finden, und es kann nicht zu lange dauern. Jede binäre Suche zum Finden eines Koeffizienten dauert höchstens O (lg (p + q)), und die Suche enthält höchstens O (lg (p + q)) Ebenen, sodass wir nur O (lg 2 (p) benötigen + q)) arithmetische Operationen und Sonden zur Wiederherstellung von p / q.

Ein Detail, auf das ich hinweisen möchte, ist, dass wir bei der Suche nachverfolgen müssen, ob wir uns auf einer ungeraden oder einer geraden Ebene befinden, denn wenn wir p / q zwischen zwei fortgesetzten Brüchen einklemmen, müssen wir wissen, ob der Koeffizient Wir suchten nach der oberen oder unteren Fraktion. Ich werde ohne Beweis sagen, dass für ein i mit i ungerade die obere der beiden Zahlen verwenden möchten, und für ein i sogar verwenden Sie die untere der beiden Zahlen.

Ich bin fast zu 100% davon überzeugt, dass dieser Algorithmus funktioniert. Ich werde versuchen, einen formelleren Beweis dafür zu verfassen, in dem ich alle Lücken in dieser Argumentation ausfülle, und wenn ich das tue, werde ich hier einen Link posten.

Vielen Dank an alle, die die notwendigen Erkenntnisse geliefert haben, um diese Lösung zum Laufen zu bringen, insbesondere an Jason S, der eine binäre Suche über fortgesetzte Brüche vorgeschlagen hat.

templatetypedef
quelle
Ich habe das gerade gesehen, hatte noch keine Gelegenheit, es sorgfältig durchzulesen, aber Sie haben wahrscheinlich Recht.
Jason S
... obwohl ich denke, es ist log (q), nicht log ^ 2 (q).
Jason S
Ich glaube das ist richtig. Für einen Beweis siehe meinen Kommentar zu Jasons erster Antwort.
Eigentlich denke ich, wir haben einen Beweis dafür, dass es O ist (log q). Siehe meinen Kommentar zu Jasons zweiter Antwort.
2

Denken Sie daran, dass jede rationale Zahl in (0, 1) als endliche Summe verschiedener (positiver oder negativer) Einheitsbrüche dargestellt werden kann. Zum Beispiel 2/3 = 1/2 + 1/6 und 2/5 = 1/2 - 1/10. Sie können dies verwenden, um eine einfache binäre Suche durchzuführen.

Mick
quelle
2
Könnten Sie näher erläutern, wie der Algorithmus diese Tatsache nutzen würde?
Seth
Sprechen Sie über ägyptische Fraktionen?
Gabe
2

Hier ist noch ein anderer Weg, dies zu tun. Wenn es genügend Interesse gibt, werde ich versuchen, die Details heute Abend auszufüllen, aber ich kann es jetzt nicht, weil ich familiäre Pflichten habe. Hier ist ein Teil einer Implementierung, die den Algorithmus erklären sollte:

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)

Und hier ist die Erklärung. Was best_continued_fraction(x, bound)zu tun ist, ist die letzte fortgesetzte Bruchannäherung xan höchstens mit dem Nenner zu finden bound. Dieser Algorithmus benötigt Polylog-Schritte und findet sehr gute (wenn auch nicht immer die besten) Näherungen. Also für jedenbound wir also etwas, das einer binären Suche durch alle möglichen Brüche dieser Größe nahe kommt. Gelegentlich werden wir keinen bestimmten Bruch finden, bis wir die Grenze weiter erhöhen, als wir sollten, aber wir werden nicht weit weg sein.

Da haben Sie es also. Eine logarithmische Anzahl von Fragen, die bei Polylog-Arbeiten gefunden wurden.

Update: Und vollständiger Arbeitscode.

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

Es scheint in Vermutungen etwas effizienter zu sein als die vorherige Lösung und führt viel weniger Operationen aus. Für 101/1024 waren 19 Vermutungen und 251 Operationen erforderlich. Für .98765 wurden 27 Vermutungen und 623 Operationen benötigt. Für 0.0123456789 waren 66 Vermutungen und 889 Operationen erforderlich. Und für Kichern und Grinsen waren für 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (das sind 10 Kopien der vorherigen) 665 Vermutungen und 23289 Operationen erforderlich.

Übrigens
quelle
@ Moron: Das ist für dich.
Btilly
@ Jason-s: Es ist jetzt besser ausgefüllt. Ich freue mich darauf, mit Ihrem zu vergleichen, wenn Sie Code haben. Ihre werden definitiv weniger Operationen erfordern, ich habe keinen Sinn, wessen weniger Vermutungen erfordern werden.
Btilly
0

Sie können rationale Zahlen in einem bestimmten Intervall beispielsweise nach dem Paar (Nenner, Zähler) sortieren. Dann können Sie das Spiel spielen

  1. Finden Sie das Intervall [0, N]mit dem Doppelschritt-Ansatz
  2. Gegeben ist ein Intervall- [a, b]Shoot für das Rationale mit dem kleinsten Nenner in dem Intervall, das der Mitte des Intervalls am nächsten liegt

das ist aber wahrscheinlich noch O(log(num/den) + den)(nicht sicher und es ist zu früh am Morgen hier, um mich klar denken zu lassen ;-))

6502
quelle