Frage Das "rate the number" -Spiel für beliebige rationale Zahlen?


Ich habe mal folgendes als Interviewfrage bekommen:

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

Dieses Problem kann durch eine modifizierte binäre Suche gelöst werden, in der Sie Potenzen von zwei auflisten, bis Sie eine finden, die n überschreitet, und dann eine Standard-Binärsuche über diesen Bereich ausführen. Was ich denke, ist so cool daran, dass Sie einen unendlichen Raum für eine bestimmte Zahl schneller als nur Brute-Force suchen können.

Die Frage, die ich habe, ist jedoch eine geringfügige Abänderung dieses Problems. Anstatt eine positive ganze Zahl zu wählen, nehme ich an, dass ich eine auswähle willkürliche rationale Zahl zwischen null und eins. Meine Frage ist: Mit welchem ​​Algorithmus können Sie am effizientesten bestimmen, welche rationale Zahl ich ausgewählt habe?

Gerade jetzt, die beste Lösung, die ich habe, kann p / q in höchstens O (q) Zeit finden, indem Sie implizit gehen Stern-Brokotbaum, ein binärer Suchbaum über alle Rationalitäten. Allerdings hatte ich gehofft, eine Laufzeit näher an die Laufzeit zu bekommen, die wir für den Integer-Fall hatten, vielleicht 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 binäre Standardsuche des Intervalls [0, 1] zu verwenden, aber dies wird nur rationale Zahlen mit einer sich nicht wiederholenden binären Darstellung finden, die fast alle Rationalitäten verfehlt. Ich habe auch darüber nachgedacht, die Rationale auf andere Weise zu nummerieren, aber ich kann anscheinend keinen Weg finden, diesen Raum zu durchsuchen, wenn man nur größere / gleiche / weniger Vergleiche anstellt.


75
2018-03-26 06:19


Ursprung


Antworten:


Okay, hier ist meine Antwort mit fortlaufende Brüche allein.

Zuerst lasst uns hier ein paar Begriffe finden.

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 uns das das Zeichen unseres Fehlers .

Das konventionelle Schreibweise für fortlaufende Brüche ist A = [a0; ein1, ein2, ein3, ... eink]

= a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / (... + 1 / ak) ...)))


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: Das Voraussetzungen sind das:

    • Y und Z sind fortlaufende Bruchteile von k + 1 Termen, die bis auf das letzte Element identisch sind, wobei sie sich um 1 unterscheiden, so dass Y = [y0; y1, y2, y3, ... yk] und Z = [y0; y1, y2, y3, ... yk + 1]

    • (-1)k(Y-X) <0 <(-1)k(Z-X), oder in einfacheren Worten, für k gerade, Y <X <Z und für k ungerade, Z <X <Y.

  3. Erweitere den Grad des fortlaufenden Bruches um 1 Schritt, ohne die Werte der Zahlen zu ändern. Im Allgemeinen, wenn die letzten Begriffe y sindk Andyk+ 1, wir ändern das zu [... yk, yk + 1= ∞] und [... ykzk + 1= 1]. Jetzt k um 1 erhöhen.

  4. Innere Schleifen: Dies ist im Wesentlichen das gleiche wie die Interviewfrage von @ templatetypedef zu den ganzen Zahlen. Wir machen eine zweiphasige binäre Suche, um näher zu kommen:

  5. Innere Schleife 1: yk = ∞, zk  = a, und X ist zwischen Y und Z.

  6. Doppelter Z letzter Ausdruck: Berechne M = Z, aber mit mk = 2 * a = 2 * zk.

  7. Frage die unbekannte Zahl ab: q = Q (X, M).

  8. Wenn q = 0, haben wir unsere Antwort und gehen zu Schritt 17.

  9. Wenn q und Q (X, Y) entgegengesetzte Vorzeichen haben, bedeutet dies, dass X zwischen Y und M liegt, also setze Z = M und gehe zu Schritt 5.

  10. Ansonsten setze Y = M und gehe zum nächsten Schritt:

  11. Innere Schleife 2. yk = b, zk  = a, und X ist zwischen Y und Z.

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

  13. Führen Sie eine binäre Suche durch: Berechnen Sie M mit mk = floor ((a + b) / 2 und Abfrage q = Q (X, M).

  14. Wenn q = 0 ist, sind wir fertig und gehen zu Schritt 17.

  15. Wenn q und Q (X, Y) entgegengesetzte Vorzeichen haben, bedeutet dies, dass X zwischen Y und M liegt, also setze Z = M und gehe zu Schritt 11.

  16. Ansonsten haben q und Q (X, Z) entgegengesetzte Vorzeichen, dh X liegt zwischen Z und M, also setze Y = M und gehe zu Schritt 11.

  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 des Berechnens von M verringert sich der Bereich des Intervalls. Es ist wahrscheinlich ziemlich einfach zu beweisen (obwohl ich dies nicht tun werde), dass das Intervall bei jedem Schritt um einen Faktor von mindestens 1 / √ 5 abnimmt, 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 irgendein rationale Zahl p / q, nicht nur zwischen 0 und 1, indem zuerst Q (X, 0) berechnet wird, dann entweder für positive / negative Ganzzahlen, die Grenze zwischen zwei aufeinanderfolgenden ganzen Zahlen, und dann der obige Algorithmus für den Bruchteil verwendet wird.

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

bearbeitenBeachten Sie auch, dass Sie nicht den fortlaufenden Bruch jedes Schrittes berechnen müssen (was O (k) wäre, es gibt teilweise Annäherungen an fortlaufende Brüche, die den nächsten Schritt aus dem vorherigen Schritt in O (1) berechnen können.)

bearbeite 2: Rekursive Definition von partiellen Approximanten:

Wenn eink = [a0; ein1, ein2, ein3, ... eink] = pk/ qk, dann pk = akpk-1 + pk-2und qk = akqk-1 + qk-2. (Quelle: Niven & Zuckerman, 4. Auflage, Theoreme 7.3-7.5. Siehe auch Wikipedia)

Beispiel: [0] = 0/1 = p0/ q0, [0; 7] = 1/7 = p1/ q1; so [0; 7, 16] = (16 * 1 + 0) / (16 * 7 + 1) = 16/113 = p2/ q2.

Dies bedeutet, dass, wenn zwei fortlaufende Brüche Y und Z die gleichen Terme außer dem letzten haben, und der fortgesetzte Bruch, der den letzten Term ausschließt, p istk-1/ qk-1, dann können wir Y = (ykpk-1 + pk-2) / (ykqk-1 + qk-2) und Z = (zkpk-1 + pk-2) / (zkqk-1 + qk-2). Es sollte möglich sein, davon zu zeigen, dass | Y-Z | bei jedem kleineren Intervall, das von diesem Algorithmus erzeugt wird, um mindestens einen Faktor von 1 / √ (5) ab, aber die Algebra scheint im Moment über mir 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 Biginteger-Berechnungen von Anfang an handhabt und dieses Programm nur Integer-Mathe verwendet (außer für die Intervallberechnungen), sollte es für beliebige Rationale funktionieren.


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

Beachten Sie zunächst, dass bis zur Angabe der rationalen Zahl die Anzahl der Schritte nk für jeden neuen fortgesetzten Bruchteil ist genau 2b (a_k) -1 wobei b (a_k) die Anzahl der Bits ist, die benötigt werden, um a_k = ceil darzustellen (log2 (a_k)): 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 sehen Sie, dass die Anzahl der Schritte immer 1, 3, 7, 15 usw. ist.

Jetzt können wir die Rekursionsbeziehung q verwendenk = akqk-1 + qk-2 und Induktion, um das gewünschte Ergebnis zu beweisen.

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

Basisfälle:

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

Dies bedeutet A = 1, c = 1/2 könnte gewünschte Grenzen liefern. In Wirklichkeit kann q nicht verdoppeln Sie jeden Begriff (Gegenbeispiel: [0; 1, 1, 1, 1, 1] hat einen Wachstumsfaktor von phi = (1 + sqrt (5)) / 2), also benutzen wir c = 1/4.

Induktion:

  • für Term k, qk = akqk-1 + qk-2. Nochmals, für die nk = 2b-1 Schritte, die für diesen Ausdruck benötigt werden, ak > = 2b-1 = 2(Anmk-1) / 2.

    Also akqk-1 > = 2(Nk-1) / 2 * qk-1 > = 2(Anmk-1) / 2 * A * 2Nk-1/ 4 = A * 2Nk/ 4/ sqrt (2) * 2nk/ 4.

Argh - der schwierige Teil hier ist, dass wenn ak = 1, q darf für diesen einen Begriff nicht viel zunehmen, und wir müssen q verwendenk-2 aber das kann viel kleiner als q seink-1.


49
2018-03-26 22:56



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

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 entlang, bis wir 3 in unserem Sortiment haben. Dann werden wir 2 Vermutungen nehmen, um diese Liste zu durchsuchen. Dann gehen wir die Liste entlang, bis wir 7 in unserem Restbereich haben. Dann werden wir 3 Vermutungen nehmen, um diese Liste zu durchsuchen. Und so weiter.

Im n Schritte werden wir die erste abdecken 2Auf) Möglichkeiten, die in der Größenordnung der Effizienz, die Sie gesucht haben.

Aktualisieren: Die Leute haben die Gründe dafür nicht verstanden. Die Argumentation ist einfach. Wir wissen, wie man einen binären Baum effizient begehen kann. Es gibt O(n2) Brüche mit maximalem Nenner n. Wir konnten daher bis zu einer bestimmten Nennergröße in O(2*log(n)) = O(log(n)) Schritte. Das Problem ist, dass wir unendlich viele rationale Suchkriterien haben. Also können wir sie nicht alle zusammenstellen, sie bestellen und anfangen zu suchen.

Daher war es meine Idee, ein paar aufzureißen, zu suchen, mehr aufzustellen, zu suchen und so weiter. Jedes Mal, wenn wir uns mehr aufstellen, stellen wir uns doppelt so auf wie beim letzten Mal. Also brauchen wir eine weitere Schätzung als beim letzten Mal. Daher verwendet unser erster Durchlauf 1 Schätzung, um 1 mögliches Rational zu durchlaufen. Unsere Sekunde verwendet 2 Vermutungen, um 3 mögliche Rationale zu durchlaufen. Unsere dritte verwendet 3 Annahmen, um 7 mögliche Rationale zu durchlaufen. Und unser k'th verwendet k Vermutungen zu durchqueren 2k-1 mögliche Rationale. Für irgendeinen besonderen Zweck m/nIrgendwann wird es das rationale auf eine ziemlich große Liste setzen, dass es weiß, wie man eine binäre Suche effizient macht.

Wenn wir eine binäre Suche durchführen würden und dann alles ignorieren würden, was wir gelernt haben, wenn wir mehr Rationale greifen, dann würden wir alle Rationals bis einschließlich einordnen m/n im O(log(n)) geht vorbei. (Das kommt daher, dass wir zu diesem Zeitpunkt mit genügend Rationalen einen Pass bekommen, um alle Rationalitäten bis einschließlich einzugliedern m/n.) Aber jeder Durchlauf benötigt mehr Schätzungen, so wäre es O(log(n)2) Vermutungen.

jedoch Wir machen tatsächlich viel besser als das. Mit unserer ersten Schätzung eliminieren wir die Hälfte der Rationalen auf unserer Liste als zu groß oder zu klein. Unsere nächsten beiden Vermutungen schneiden den Raum nicht ganz in Viertel, aber sie kommen nicht zu weit davon entfernt. Unsere nächsten 3 Vermutungen schneiden den Platz nicht wirklich in Achtel, aber sie kommen nicht zu weit davon entfernt. Und so weiter. Wenn Sie es zusammensetzen, bin ich überzeugt, dass das Ergebnis ist, dass Sie finden m/n im O(log(n)) Schritte. Obwohl ich keinen Beweis habe.

Versuch es: Hier ist Code, um die Vermutungen zu generieren, so dass Sie spielen können und sehen, 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 ein Beispiel, um es auszuprobieren, versuchte ich 101/1024 (0.0986328125) und fand heraus, dass es 20 Vermutungen brauchte, um die Antwort zu finden. Ich habe 0.98765 ausprobiert und 45 Versuche benötigt. Ich habe versucht, 0.0123456789 und es brauchte 66 Schätzungen und etwa eine Sekunde, um sie zu generieren. (Beachte, wenn du das Programm mit einer rationalen Zahl als Argument anrufst, wird es alle Raten für dich ausfüllen. Dies ist eine sehr hilfreiche Annehmlichkeit.)


6
2018-03-26 07:40



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

Die Bisektion 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 hast du l und u die unteren und oberen Grenzen der Halbierung sind. Die Idee ist, dass Sie die Wahl haben, den Bereich der Halbierung zu halbieren und einen zusätzlichen Ausdruck als fortlaufende Bruchdarstellung hinzuzufügen. Wenn beide l und u Haben Sie den gleichen nächsten Begriff wie ein fortgesetzter Bruch, dann machen Sie den nächsten Schritt in der Fortsetzung der Fraktionssuche und machen eine Abfrage mit dem Kettenbruch. Andernfalls halbieren Sie den Bereich halbiert.

Da beide Methoden den Nenner um mindestens einen konstanten Faktor erhöhen (Halbierung um Faktor 2, kontinuierliche Brüche um mindestens einen Faktor von phi = (1 + sqrt (5)) / 2), bedeutet dies, dass Ihre Suche O sein sollte (log (q)). (Wiederholte Berechnungen können fortgesetzt werden, so dass es als O (log (q) ^ 2) enden kann.)

Unsere fortlaufende Fraktionssuche muss auf die nächste Ganzzahl runden, und nicht die Ebene verwenden (dies wird nachstehend näher erläutert).

Das oben genannte ist handwavy. Nehmen wir ein konkretes Beispiel für r = 1/31:

  1. l = 0, u = 1, Abfrage = 1/2. 0 ist nicht als fortlaufender Bruchteil auszudrücken, also 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 verschiedene cfrac Wiederholungen, also halte die Halbierung., Query = 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 zu 1/30)

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

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

  12. l = 33/1024, u = 67/2048. An diesem Punkt haben sowohl l als auch du den gleichen Fortsetzungsbruchteil 31, also verwenden wir jetzt eine fortgesetzte Bruchratenschätzung.   Abfrage = 1/31.

ERFOLG!

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

[Fortsetzung folgt, ich muss irgendwohin gehen]


Bei weiterer Betrachtung sind fortgesetzte Brüche der richtige Weg, ganz abgesehen von der Halbierung, außer um den nächsten Begriff zu bestimmen. Mehr wenn ich zurückkomme.


4
2018-03-26 14:11



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

Um Verwirrung im nächsten Abschnitt zu vermeiden, bezieht sich eine "Abfrage" darauf, dass der Herausforderer dem Herausforderer eine Schätzung gibt und der Herausforderer "größer" oder "kleiner" antwortet. Dies erlaubt mir, das Wort "rate" für etwas anderes zu reservieren, eine Schätzung für p + q, die nicht direkt an den Herausforderer gerichtet ist.

Die Idee ist, zuerst p + q zu finden, mit dem Algorithmus, den Sie in Ihrer Frage beschreiben: rate einen Wert k, wenn k zu klein ist, verdopple ihn und versuche es erneut. Sobald Sie eine obere und untere Grenze haben, führen Sie eine Standard-Binärsuche durch. Dies erfordert O (log (p + q) T) -Abfragen, wobei T eine obere Grenze für die Anzahl von Abfragen ist, die zum Prüfen einer Schätzung benötigt werden. Lass uns T. finden

Wir wollen alle Brüche r / s mit r + s <= k überprüfen und k verdoppeln, bis k groß genug ist. Beachten Sie, dass es O (k ^ 2) Brüche gibt, die Sie für einen gegebenen Wert von k überprüfen müssen. Erstellen Sie einen ausgeglichenen binären Suchbaum, der all diese Werte enthält, und suchen Sie danach, ob p / q im Baum ist. Es braucht O (log k ^ 2) = O (log k) -Abfragen, um zu bestätigen, dass p / q nicht im Baum 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 korrekten Wert für k erraten (d. H. K = p + q), werden wir die Abfrage p / q dem Herausforderer im Verlauf der Überprüfung unserer Schätzung für k vorlegen und das Spiel gewinnen.

Die Gesamtanzahl der Abfragen ist dann O (log ^ 2 (p + q)).


3
2018-03-26 08:15



Okay, ich denke, ich habe ein O herausgefunden (lg2 q) Algorithmus für dieses Problem, der auf Jason Ss exzellentestem Wissen über die Verwendung fortgesetzter Brüche basiert. Ich dachte, ich würde den Algorithmus genau hier aushöhlen, so dass 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

ein0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / ...))

Für eine angemessene Auswahl von aich. Das nennt man a Fortsetzung Fraktion. Noch wichtiger, obwohl diese aich kann abgeleitet werden, indem der euklidische Algorithmus auf 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 Nullzeiten geht, so dass eine grobe Näherung von 11/14 wäre

0 = 0

Nehmen wir nun an, dass wir das Reziproke dieses Bruches nehmen, um 14/11 = 1 zu erhalten 3/11. Also wenn wir schreiben

0 + (1/1) = 1

Wir bekommen eine etwas bessere Annäherung an 11/14. Jetzt, da wir noch 3/11 haben, können wir den Kehrwert wieder nehmen, um 11/3 = 3 zu erhalten 2/3Also können wir darüber nachdenken

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

Das ist eine weitere gute Annäherung an 11/14. Nun haben wir 2/3, also betrachten wir das Reziproke, welches 3/2 = 1 ist 1/2. Wenn wir dann schreiben

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

Wir erhalten eine weitere gute Annäherung an 11/14. Schließlich bleibt uns 1/2, 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 Bruch, den wir wollten. Schauen wir uns außerdem die Reihenfolge der Koeffizienten an, die wir 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 (unter Verwendung von 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 0 (lg (p + q)) Koeffizienten geben, weil 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 zur Wiederherstellung einer beliebigen rationalen Zahl p / q, nicht nur derjenigen zwischen 0 und 1, durch Anwendung des allgemeinen Algorithmus zum raschen Ermitteln beliebiger ganzer Zahlen n, um alle Koeffizienten in der fortlaufende Bruch für p / q. Fürs Erste aber werden wir uns nur um Zahlen im Bereich (0, 1) sorgen, da die Logik zur Handhabung beliebiger rationaler Zahlen leicht als Subroutine ausgeführt werden kann.

Nehmen wir als ersten Schritt an, dass wir den besten Wert von a finden wollen1 so dass 1 / a1 ist so nahe wie möglich an p / q und a1 ist eine ganze Zahl. Um dies zu tun, können wir einfach unseren Algorithmus zum Erraten von beliebigen ganzen Zahlen ausführen, wobei wir jedes Mal den Kehrwert nehmen. Danach wird eines von zwei Dingen passiert sein. Erstens könnten wir durch reinen Zufall feststellen, dass p / q = 1 / k für eine ganze Zahl k ist, in welchem ​​Fall wir fertig sind. Wenn nicht, werden wir feststellen, dass p / q zwischen 1 / (a1- 1) und 1 / a0 für einige a1. Wenn wir das machen, beginnen wir mit der Arbeit an der weiterführenden Fraktion, eine Stufe tiefer, indem wir die a finden2 so dass p / q zwischen 1 / (a1 + 1 / a2) und 1 / (a1 + 1 / (a2 + 1)). Wenn wir auf magische Weise p / q finden, ist das großartig! Ansonsten gehen wir dann im fortlaufenden Bruch eine Stufe tiefer. Irgendwann werden wir die Nummer auf diese Weise finden, und es kann nicht zu lange dauern. Jede binäre Suche, um einen Koeffizienten zu finden, nimmt höchstens 0 (lg (p + q)) Zeit, und es gibt höchstens 0 (lg (p + q)) Ebenen für die Suche, so dass wir nur O (lg2(p + q)) arithmetische Operationen und Sonden zur Wiederherstellung von p / q.

Ein Detail, das ich hervorheben möchte, ist, dass wir bei der Suche verfolgen müssen, ob wir auf einer ungeraden Ebene oder einer geraden Ebene sind, denn wenn wir p / q zwischen zwei fortgesetzten Brüchen einbetten, müssen wir wissen, ob der Koeffizient Wir suchten nach der oberen oder unteren Fraktion. Ich werde ohne Beweis sagen, dass für eineich mit i odd willst du die obere der beiden Zahlen verwenden, und mit aich selbst du benutzt die niedrigere der beiden Zahlen.

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

Danke an alle, dass sie die Einsichten beigetragen haben, die notwendig waren, um diese Lösung zum Laufen zu bringen, besonders Jason S, der eine binäre Suche über fortlaufende Brüche vorgeschlagen hat.


3
2018-03-26 22:51



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


2
2018-03-26 12:45



Hier ist noch ein anderer Weg, es zu tun. Wenn es genügend Interesse gibt, werde ich versuchen, die Details heute Abend auszufüllen, aber ich kann jetzt nicht, weil ich familiäre Verpflichtungen habe. Hier ist ein Stub 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) sollte tun, finden Sie die letzte fortgesetzte Fraktion Annäherung an x höchstens mit dem Nenner bound. Dieser Algorithmus nimmt Polylog-Schritte zum Abschluss und findet sehr gute (wenn auch nicht immer die besten) Näherungen. Also für jeden bound wir werden etwas in der Nähe einer binären Suche durch alle möglichen Bruchteile dieser Größe bekommen. Gelegentlich werden wir einen bestimmten Bruchteil nicht finden, bis wir die Grenze weiter erhöhen, als wir sollten, aber wir werden nicht in der Nähe sein.

So, da hast du es. Eine logarithmische Anzahl von Fragen gefunden mit Polylog Arbeit.

Aktualisieren: Und voller funktionierender Code.

#! /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 etwas effizienter zu sein als die vorherige Lösung und macht viel weniger Operationen. Für 101/1024 benötigte es 19 Vermutungen und 251 Operationen. Für .98765 benötigt es 27 Vermutungen und 623 Operationen. Für 0,0123456789 erforderte es 66 Annahmen und 889 Operationen. Und für Kichern und Grinsen, für 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (das ist 10 Kopien der vorherigen) es benötigt 665 Vermutungen und 23289 Operationen.


2
2018-03-26 21:02