Le jeu "devinez le nombre" pour les nombres rationnels arbitraires ?

Question

Une fois, on m'a posé la question suivante lors d'un entretien :

Je pense à un nombre entier positif n. Trouvez un algorithme qui peut le deviner en O(lg n) requêtes. Chaque requête est un nombre de votre choix, et je répondrai soit "inférieur", soit "supérieur", soit "correct".

Ce problème peut être résolu par une recherche binaire modifiée, dans laquelle on énumère les puissances de deux jusqu'à ce qu'on en trouve une qui dépasse n, puis on effectue une recherche binaire standard sur cette plage. Ce que je trouve génial dans cette méthode, c'est que l'on peut rechercher un nombre particulier dans un espace infini plus rapidement que par la force brute.

La question que je me pose, cependant, est une légère modification de ce problème. Au lieu de choisir un entier positif, supposons que je choisisse un nombre rationnel arbitraire entre zéro et un. Ma question est la suivante : quel algorithme pouvez-vous utiliser pour déterminer le plus efficacement possible le nombre rationnel que j'ai choisi ?

Pour l'instant, la meilleure solution dont je dispose permet de trouver p/q en un temps maximum de O(q) en parcourant implicitement l'arborescence de la base de données. Arbre Stern-Brocot un arbre de recherche binaire sur tous les rationnels. Cependant, j'espérais obtenir un temps d'exécution plus proche de celui que nous avons obtenu pour le cas des entiers, peut-être quelque chose comme O(lg (p + q)) ou O(lg pq). Quelqu'un connaît-il un moyen d'obtenir ce type de temps d'exécution ?

J'ai d'abord envisagé d'utiliser une recherche binaire standard de l'intervalle [0, 1], mais cette méthode ne trouve que les nombres rationnels dont la représentation binaire n'est pas répétitive, ce qui laisse de côté la quasi-totalité des rationnels. J'ai également envisagé d'utiliser une autre méthode d'énumération des rationnels, mais je ne parviens pas à trouver un moyen de rechercher cet espace à partir de simples comparaisons plus grand/égal/moins.

Merci pour tous les conseils/suggestions que vous pourriez avoir !

Answer 1

Ok, voici ma réponse en utilisant fractions continues seul.

Tout d'abord, il convient d'établir une certaine terminologie.

Soit X = p/q la fraction inconnue.

Soit Q(X,p/q) = sign(X - p/q) la fonction d'interrogation : si elle vaut 0, nous avons deviné le nombre, et si elle est +/- 1, elle nous indique le signe de notre erreur.

El notation conventionnelle pour les fractions continues est A = [a ₀ ; a ₁ , a ₂ , a ₃ , ... a _k ]

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

---

Nous suivrons l'algorithme suivant pour 0 < p/q < 1.

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

2. Boucle extérieure : Le site conditions préalables sont que :

   • Y et Z sont des fractions continues de k+1 termes qui sont identiques sauf dans le dernier élément, où ils diffèrent de 1, de sorte que Y = [y ₀ ; y ₁ , y ₂ , y ₃ , ... y _k ] et Z = [y ₀ ; y ₁ , y ₂ , y ₃ , ... y _k + 1]

   • (-1) k (Y-X) < 0 < (-1) k (Z-X), ou en termes plus simples, pour k pair, Y < X < Z et pour k impair, Z < X < Y.

3. Prolongez le degré de la fraction continue d'un pas sans changer les valeurs des nombres. En général, si les derniers termes sont y _k et y _k + 1, nous changeons cela en [... y _k , y _k+1 \=∞] et [... y _k , z _k+1 \=1]. Augmentez maintenant k de 1.

4. Boucles intérieures : C'est essentiellement la même chose que la question d'entretien de @templatetypedef sur les entiers. Nous faisons une recherche binaire en deux phases pour nous rapprocher :

5. Boucle intérieure 1 : y _k \= ∞, z _k \= a, et X est entre Y et Z.

6. Le dernier terme de Double Z : Calculez M = Z mais avec m _k \= 2*a = 2*z _k .

7. Interroger le nombre inconnu : q = Q(X,M).

8. Si q = 0, nous avons notre réponse et passons à l'étape 17 .

9. Si q et Q(X,Y) ont des signes opposés, cela signifie que X se trouve entre Y et M, alors définissez Z = M et passez à l'étape 5.

10. Sinon, définir Y = M et passer à l'étape suivante :

11. Boucle intérieure 2. y _k \= b, z _k \= a, et X est entre Y et Z.

12. Si a et b diffèrent de 1, permutez Y et Z, passez à l'étape 2.

13. Effectuer une recherche binaire : calculer M où m _k \= floor((a+b)/2, et la requête q = Q(X,M).

14. Si q = 0, nous avons terminé et passons à l'étape 17.

15. Si q et Q(X,Y) ont des signes opposés, cela signifie que X se trouve entre Y et M, alors définissez Z = M et passez à l'étape 11.

16. Sinon, q et Q(X,Z) ont des signes opposés, ce qui signifie que X est entre Z et M, alors définissez Y = M et passez à l'étape 11.

17. C'est fait : X = M.

Un exemple concret pour 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!

A chaque étape du calcul de M, l'étendue de l'intervalle se réduit. Il est probablement assez facile de prouver (mais je ne le ferai pas) que l'intervalle se réduit d'un facteur d'au moins 1/sqrt(5) à chaque étape, ce qui montrerait que cet algorithme est O(log q) étapes.

Notez que ceci peut être combiné avec la question d'entretien originale de templatetypedef et s'appliquer à tout nombre rationnel p/q, et pas seulement entre 0 et 1, en calculant d'abord Q(X,0), puis pour les entiers positifs/négatifs, en délimitant entre deux entiers consécutifs, et enfin en utilisant l'algorithme ci-dessus pour la partie fractionnaire.

Quand j'en aurai l'occasion, je posterai un programme python qui implémente cet algorithme.

modifier En outre, notez que vous n'avez pas à calculer la fraction continue à chaque étape (ce qui serait O(k), il existe des approximations partielles des fractions continues qui peuvent calculer l'étape suivante à partir de l'étape précédente en O(1)).

modifier 2 : Définition récursive des approximants partiels :

Si A _k \= [a ₀ ; a ₁ , a ₂ , a ₃ , ... a _k ] = p _k /q _k alors p _k \= a _k p _k-1 + p _k-2 et q _k \= a _k q _k-1 + q _k-2 . (Source : Niven & Zuckerman, 4th ed, Théorèmes 7.3-7.5. Voir aussi Wikipedia )

Exemple : [0] = 0/1 = p ₀ /q ₀ , [0 ; 7] = 1/7 = p ₁ /q ₁ ; donc [0 ; 7, 16] = (16*1+0)/(16*7+1) = 16/113 = p ₂ /q ₂ .

Cela signifie que si deux fractions continues Y et Z ont les mêmes termes sauf le dernier, et que la fraction continue excluant le dernier terme est p _k-1 /q _k-1 alors nous pouvons écrire Y = (y _k p _k-1 + p _k-2 ) / (y _k q _k-1 + q _k-2 ) et Z = (z _k p _k-1 + p _k-2 ) / (z _k q _k-1 + q _k-2 ). Il devrait être possible de montrer à partir de là que |Y-Z| diminue d'au moins un facteur de 1/sqrt(5) à chaque intervalle plus petit produit par cet algorithme, mais l'algèbre semble me dépasser pour le moment :-(

Voici mon programme 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]

et un exemple de sortie pour 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

Étant donné que Python gère dès le départ les calculs sur les grands nombres entiers et que ce programme n'utilise que des nombres entiers (sauf pour les calculs d'intervalles), il devrait fonctionner pour des rationnels arbitraires.

---

éditer 3 : Aperçu de la preuve que c'est O(log q), et non O(log^2 q) :

Notez d'abord que jusqu'à ce que le nombre rationnel soit trouvé, le nombre d'étapes n _k pour chaque nouveau terme de fraction continue est exactement 2b(a_k)-1 où b(a_k) est le nombre de bits nécessaires pour représenter a_k = ceil(log2(a_k)) : il y a b(a_k) pas pour élargir le "filet" de la recherche binaire, et b(a_k)-1 pas pour le réduire). Dans l'exemple ci-dessus, vous noterez que le nombre de pas est toujours 1, 3, 7, 15, etc.

Nous pouvons maintenant utiliser la relation de récurrence q _k \= a _k q _k-1 + q _k-2 et l'induction pour prouver le résultat souhaité.

Disons-le ainsi : que la valeur de q après le N _k \= somme(n _k ) étapes nécessaires pour atteindre le kième terme a un minimum : q >= A*2 cN pour certaines constantes fixes A,c. (donc, pour inverser, nous obtiendrions que le nombre d'étapes N est <= (1/c) * log ₂ (q/A) = O(log q).)

Cas de base :

• k=0 : q = 1, N = 0, donc q >= 2 N
• k=1 : pour N = 2b-1 étapes, q = a ₁ >= 2 b-1 \= 2 (N-1)/2 \= 2 N/2 /sqrt(2).

Cela implique que A = 1, c = 1/2 pourraient fournir les limites souhaitées. En réalité, q peut no doubler chaque terme (contre-exemple : [0 ; 1, 1, 1, 1, 1, 1] a un facteur de croissance de phi = (1+sqrt(5))/2) donc utilisons c = 1/4.

Induction :

• pour le terme k, q _k \= a _k q _k-1 + q _k-2 . Encore une fois, pour les n _k \= 2b-1 étapes nécessaires pour ce terme, a _k >= 2 b-1 \= 2 (n _k -1)/2 .

  Donc un _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 -- la partie difficile ici est que si un _k \= 1, q peut ne pas augmenter beaucoup pour ce seul terme, et nous devons utiliser q _k-2 mais cela peut être beaucoup plus petit que q _k-1 .

Answer 2

Prenons les nombres rationnels, sous forme réduite, et écrivons-les dans l'ordre d'abord du dénominateur, puis du numérateur.

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

Notre première supposition sera 1/2 . Ensuite, nous allons parcourir la liste jusqu'à ce que nous en ayons 3 dans notre gamme. Ensuite, nous prendrons 2 devinettes pour chercher dans cette liste. Ensuite, nous parcourrons la liste jusqu'à ce que nous ayons 7 dans notre plage restante. Nous ferons alors 3 essais pour chercher dans cette liste. Et ainsi de suite.

Sur n nous couvrirons les premières étapes 2O(n) possibilités, ce qui est dans l'ordre de grandeur de l'efficacité que vous recherchiez.

Mise à jour : Les gens n'ont pas compris le raisonnement derrière tout ça. Le raisonnement est simple. Nous savons comment parcourir un arbre binaire efficacement. Il y a O(n2) fractions avec dénominateur maximal n . Nous pourrions donc chercher jusqu'à une taille de dénominateur particulière en O(2*log(n)) = O(log(n)) étapes. Le problème est que nous avons un nombre infini de rationnels possibles à rechercher. Nous ne pouvons donc pas simplement les aligner, les ordonner et commencer à chercher.

Mon idée était donc d'en aligner quelques-uns, de chercher, d'en aligner d'autres, de chercher, et ainsi de suite. Chaque fois que nous en alignons plus, nous alignons environ le double de ce que nous avons fait la dernière fois. Nous avons donc besoin d'une estimation de plus que la dernière fois. Par conséquent, notre première passe utilise 1 estimation pour parcourir 1 rationnel possible. Notre deuxième passe utilise 2 devinettes pour traverser 3 rationnels possibles. Notre troisième passe utilise 3 devinettes pour traverser 7 rationnels possibles. Et notre k L'utilisation k des hypothèses à traverser 2k-1 rationnels possibles. Pour tout rationnel particulier m/n il finira par placer ce rationnel dans une liste assez importante sur laquelle il sait effectuer efficacement une recherche binaire.

Si nous faisions des recherches binaires, puis ignorions tout ce que nous avions appris en saisissant d'autres rationnels, nous mettrions tous les rationnels jusqu'à et y compris m/n en O(log(n)) passe. (C'est parce qu'à ce moment-là, nous arriverons à un passage avec suffisamment de rationnels pour inclure tous les rationnels jusqu'à et y compris m/n .) Mais chaque passage nécessite plus de suppositions, donc ce serait O(log(n)2) devine.

Cependant nous faisons en fait beaucoup mieux que ça. Avec notre première estimation, nous éliminons la moitié des rationnels de notre liste comme étant trop grands ou trop petits. Nos deux propositions suivantes ne coupent pas tout à fait l'espace en quarts, mais elles n'en sont pas très éloignées. Nos trois suppositions suivantes ne découpent pas non plus l'espace en huitièmes, mais elles n'en sont pas trop éloignées. Et ainsi de suite. Quand vous mettez tout ça ensemble, je suis convaincu que le résultat est que vous trouvez m/n en O(log(n)) étapes. Bien que je n'aie pas vraiment de preuve.

Essayez-le : Voici le code pour générer les suppositions afin que vous puissiez jouer et voir si c'est efficace.

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

À titre d'exemple, j'ai essayé 101/1024 (0,0986328125) et j'ai constaté qu'il fallait 20 essais pour trouver la réponse. J'ai essayé 0,98765 et il m'a fallu 45 essais. J'ai essayé 0,0123456789 et il m'a fallu 66 essais et environ une seconde pour les générer. (Notez que si vous appelez le programme avec un nombre rationnel comme argument, il remplira toutes les propositions pour vous. C'est une commodité très utile).

Answer 3

Je l'ai trouvé ! Ce que vous devez faire est d'utiliser une recherche parallèle avec bissection et fractions continues .

La bissection vous donne une limite vers un nombre réel spécifique, représenté par une puissance de deux, et les fractions continues prennent le nombre réel et trouvent le nombre rationnel le plus proche.

La façon de les faire fonctionner en parallèle est la suivante.

A chaque étape, vous avez l y u étant les limites inférieure et supérieure de la bissection. L'idée est que vous avez le choix entre réduire de moitié l'étendue de la bissection et ajouter un terme supplémentaire comme représentation de la fraction continue. Lorsque les deux l y u ont le même terme suivant qu'une fraction continue, vous passez alors à l'étape suivante de la recherche par fraction continue, et effectuez une requête en utilisant la fraction continue. Sinon, vous divisez l'intervalle en deux en utilisant la bissection.

Puisque les deux méthodes augmentent le dénominateur d'au moins un facteur constant (la bissection augmente par des facteurs de 2, les fractions continues augmentent d'au moins un facteur de phi = (1+sqrt(5))/2), cela signifie que votre recherche devrait être O(log(q)). (Il peut y avoir des calculs répétés de fractions continues, donc cela peut finir par être O(log(q)^2)).

Notre recherche de fraction continue doit arrondir à l'entier le plus proche, et non utiliser le plancher (ceci est plus clair ci-dessous).

Ce qui précède est un peu lourd à porter. Utilisons un exemple concret de r = 1/31 :

1. l = 0, u = 1, query = 1/2. 0 n'est pas exprimable comme une fraction continue, donc nous utilisons la recherche binaire jusqu'à ce que l != 0.

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

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

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

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

6. l = 1/32, u = 1/16. Maintenant 1/l = 32, 1/u = 16, ceux-ci ont des reps cfrac différents, donc continuer à bissecter., query = 3/64.

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

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

9. l = 1/32, u = 9/256, query = 17/512 = 1/30.1176... (arrondir à 1/30)

10. l = 1/32, u = 17/512, query = 33/1024 = 1/31.0303... (arrondir à 1/31)

11. l = 33/1024, u = 17/512, query = 67/2048 = 1/30.5672... (arrondir à 1/31)

12. l = 33/1024, u = 67/2048. À ce stade, l et u ont tous deux le même terme de fraction continue 31, donc nous utilisons maintenant une estimation de fraction continue. query = 1/31.

SUCCÈS !

Pour un autre exemple, utilisons 16/113 (= 355/113 - 3 où 355/113 est assez proche de pi).

[à suivre, je dois aller quelque part]

---

Après réflexion, les fractions continues sont la solution, sans parler de la bissection, sauf pour déterminer le terme suivant. Je vous en dirai plus à mon retour.

Answer 4

Je pense avoir trouvé un algorithme O(log^2(p + q)).

Pour éviter toute confusion dans le paragraphe suivant, une "requête" fait référence au moment où le devineur donne une estimation au challenger, et que ce dernier répond "plus grand" ou "plus petit". Cela me permet de réserver le mot "devinette" pour autre chose, une devinette pour p + q qui n'est pas demandée directement au challenger.

L'idée est de trouver d'abord p + q, en utilisant l'algorithme que vous décrivez dans votre question : devinez une valeur k, si k est trop petit, doublez-la et réessayez. Ensuite, une fois que vous avez une limite supérieure et inférieure, faites une recherche binaire standard. Cela prend O(log(p+q)T) requêtes, où T est une limite supérieure pour le nombre de requêtes nécessaires pour vérifier une estimation. Trouvons T.

Nous voulons vérifier toutes les fractions r/s avec r + s <= k, et doubler k jusqu'à ce que k soit suffisamment grand. Notez qu'il y a O(k^2) fractions que vous devez vérifier pour une valeur donnée de k. Construisez un arbre de recherche binaire équilibré contenant toutes ces valeurs, puis cherchez-le pour déterminer si p/q est dans l'arbre. Il faut O(log k^2) = O(log k) requêtes pour confirmer que p/q n'est pas dans l'arbre.

Nous ne devinerons jamais une valeur de k supérieure à 2(p + q). Par conséquent, nous pouvons prendre T = O(log(p+q)).

Lorsque nous devinons la valeur correcte de k (c'est-à-dire k = p + q), nous soumettons la requête p/q au challenger au cours de la vérification de notre estimation de k, et nous gagnons la partie.

Le nombre total de requêtes est alors O(log^2(p + q)).

Answer 5

Rappelez-vous que tout nombre rationnel dans (0, 1) peut être représenté comme une somme finie de fractions unitaires distinctes (positives ou négatives). Par exemple, 2/3 = 1/2 + 1/6 et 2/5 = 1/2 - 1/10. Vous pouvez vous en servir pour effectuer une recherche binaire simple.