algorithm - “guess the number”游戏用于任意有理数？

我曾经有以下问题作为面试问题:



此问题可通过修改后的二进制搜索解决，在该搜索中，您列出了2的幂，直到找到一个超过n的幂，然后在该范围内运行标准的二进制搜索。我认为这很酷，因为您可以比暴力破解更快地搜索无限数量的特定数字。

不过，我的问题是对此问题的轻微修改。假设不选择一个正整数，而是选择一个介于零和一之间的任意有理数。我的问题是:您可以使用哪种算法最有效地确定我选择了哪个有理数？

现在，我所拥有的最佳解决方案可以通过隐式遍历所有有理数的二叉搜索树Stern-Brocot tree，在最多O(q)的时间内找到p / q。但是，我希望使运行时更接近整数情况下的运行时，例如O(lg(p + q))或O(lg pq)。有人知道获得这种运行时的方法吗？

我最初考虑使用间隔[0，1]的标准二进制搜索，但是这只会找到具有非重复二进制表示形式的有理数，这几乎错过了所有有理数。我还考虑过使用其他方式来列举有理数，但是仅凭比较大/相等/少的比较，我似乎找不到找到这种空间的方法。

最佳答案

好的，这是我单独使用continued fractions的答案。

首先让我们在这里获得一些术语。

令X = p / q为未知分数。

令Q(X，p / q)= sign(X-p / q)为查询函数:如果为0，则我们猜出了这个数字；如果它是+/- 1，则告诉我们错误的迹象。

conventional notation for continued fractions是A = [a0; a1，a2，a3，... ak]

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

对于0

初始化Y = 0 = [0]，Z = 1 = [1]，k =0。

外循环:前提条件是:

Y和Z是k + 1项的连续分数，除了最后一个元素(它们相差1)之外，它们是相同的，因此Y = [y0; y1，y2，y3，... yk]，Z = [y0； y1，y2，y3，... yk +1]

(-1)k(Y-X)

将连续分数的度数扩展1步，而不更改数字的值。通常，如果最后一项是yk和yk +1，我们将其更改为[... yk，yk + 1 =∞]和[... yk，zk + 1 = 1]。现在将k增加1。

内循环:这与@templatetypedef关于整数的采访问题基本相同。我们进行两阶段的二进制搜索以进一步了解:

内循环1 :yk =∞，zk = a，并且X在Y和Z之间。

加倍Z的最后一项:计算M = Z，但mk = 2 * a = 2 * zk。

查询未知数:q = Q(X，M)。

如果q = 0，我们得到答案，然后转到步骤17。

如果q和Q(X，Y)具有相反的符号，则表示X在Y和M之间，因此设置Z = M并转到步骤5。

否则设置Y = M并转到下一步:

内循环2。 yk = b，zk = a，并且X在Y和Z之间。

如果a和b相差1，则将Y和Z互换，请转到步骤2。

执行二进制搜索:计算M，其中mk = floor((a + b)/ 2，并查询q = Q(X，M)。

如果q = 0，则完成并转到步骤17。

如果q和Q(X，Y)具有相反的符号，则表示X在Y和M之间，因此设置Z = M并转到步骤11。

否则，q和Q(X，Z)具有相反的符号，这意味着X在Z和M之间，因此设置Y = M并转到步骤11。

完成:X =M。

X = 16/113 = 0.14159292的具体示例

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

k = 1:
Y = 0 = [0; &#8734;] < X, Z = 1 = [0; 1] > X, M = [0; 2] = 1/2 > X.
Y = 0 = [0; &#8734;], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 > X.
Y = 0 = [0; &#8734;], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 < X.
Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 > X.
Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 > X.
Y = 1/8 = [0; 8], Z = 1/7 = [0; 7]
  --> the two last terms differ by one, so swap and repeat outer loop.

k = 2:
Y = 1/7 = [0; 7, &#8734;] > X, Z = 1/8 = [0; 7, 1] < X,
    M = [0; 7, 2] = 2/15 < X
Y = 1/7 = [0; 7, &#8734;], Z = 2/15 = [0; 7, 2],
    M = [0; 7, 4] = 4/29 < X
Y = 1/7 = [0; 7, &#8734;], Z = 4/29 = [0; 7, 4],
    M = [0; 7, 8] = 8/57 < X
Y = 1/7 = [0; 7, &#8734;], Z = 8/57 = [0; 7, 8],
    M = [0; 7, 16] = 16/113 = X
    --> done!

在计算M的每个步骤中，间隔范围会减小。可能很容易证明(尽管我不会这样做)，间隔在每一步至少减少了1 / sqrt(5)，这表明该算法为O(log q)步。

请注意，这可以与templatetypedef的原始采访问题结合使用，并通过首先计算Q(X，0)，然后对正整数或负整数进行计算，将其应用于两个有理数p / q，不仅在0和1之间，而且在两个连续整数，然后对小数部分使用上述算法。

接下来，我将发布实现该算法的python程序。

编辑:另外，请注意，您不必在每个步骤中都计算连续分数(将是O(k)，连续分数存在部分近似值，可以计算O(1中的上一步)的下一步)。

编辑2 :部分近似的递归定义:

如果Ak = [a0; a1，a2，a3，... ak] = pk / qk，然后pk = akpk-1 + pk-2，qk = akqk-1 + qk-2。 (来源:Niven和Zuckerman，第四版，定理7.3-7.5。另请参见Wikipedia)

示例:[0] = 0/1 = p0 / q0，[0; 7] = 1/7 = p1 / q1;所以[0; 7，16] =(16 * 1 + 0)/(16 * 7 + 1)= 16/113 = p2 / q2。

这意味着，如果两个连续分数Y和Z除了最后一个具有相同的项，并且不包括最后一项的连续分数是pk-1 / qk-1，则我们可以写成Y =(ykpk-1 + pk-2 )/(ykqk-1 + qk-2)和Z =(zkpk-1 + pk-2)/(zkqk-1 + qk-2)。由此可以证明| Y-Z |在此算法产生的每个较小的间隔中，它至少减小1 / sqrt(5)倍，但此刻代数似乎超出了我。 :-(

这是我的Python程序:

import math

# Return a function that returns Q(p0/q0,p/q)
#   = sign(p0/q0-p/q) = sign(p0q-q0p)*sign(q0*q)
# If p/q < p0/q0, then Q() = 1; if p/q < p0/q0, then Q() = -1; otherwise Q()=0.
def makeQ(p0,q0):
  def Q(p,q):
    return cmp(q0*p,p0*q)*cmp(q0*q,0)
  return Q

def strsign(s):
  return '<' if s<0 else '>' if s>0 else '=='

def cfnext(p1,q1,p2,q2,a):
  return [a*p1+p2,a*q1+q2]

def ratguess(Q, doprint, kmax):
# p2/q2 = p[k-2]/q[k-2]
  p2 = 1
  q2 = 0
# p1/q1 = p[k-1]/q[k-1]
  p1 = 0
  q1 = 1
  k = 0
  cf = [0]
  done = False
  while not done and (not kmax or k < kmax):
    if doprint:
      print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
# extend continued fraction
    k = k + 1
    [py,qy] = [p1,q1]
    [pz,qz] = cfnext(p1,q1,p2,q2,1)
    ay = None
    az = 1
    sy = Q(py,qy)
    sz = Q(pz,qz)
    while not done:
      if doprint:
        out = str(py)+'/'+str(qy)+' '+strsign(sy)+' X '
        out += strsign(-sz)+' '+str(pz)+'/'+str(qz)
        out += ', interval='+str(abs(1.0*py/qy-1.0*pz/qz))
      if ay:
        if (ay - az == 1):
          [p0,q0,a0] = [pz,qz,az]
          break
        am = (ay+az)/2
      else:
        am = az * 2
      [pm,qm] = cfnext(p1,q1,p2,q2,am)
      sm = Q(pm,qm)
      if doprint:
        out = str(ay)+':'+str(am)+':'+str(az) + '   ' + out + ';  M='+str(pm)+'/'+str(qm)+' '+strsign(sm)+' X '
        print out
      if (sm == 0):
        [p0,q0,a0] = [pm,qm,am]
        done = True
        break
      elif (sm == sy):
        [py,qy,ay,sy] = [pm,qm,am,sm]
      else:
        [pz,qz,az,sz] = [pm,qm,am,sm]

    [p2,q2] = [p1,q1]
    [p1,q1] = [p0,q0]
    cf += [a0]

  print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
  return [p1,q1]

以及ratguess(makeQ(33102,113017), True, 20)的示例输出:

p/q=[0]=0/1
None:2:1   0/1 < X < 1/1, interval=1.0;  M=1/2 > X
None:4:2   0/1 < X < 1/2, interval=0.5;  M=1/4 < X
4:3:2   1/4 < X < 1/2, interval=0.25;  M=1/3 > X
p/q=[0, 3]=1/3
None:2:1   1/3 > X > 1/4, interval=0.0833333333333;  M=2/7 < X
None:4:2   1/3 > X > 2/7, interval=0.047619047619;  M=4/13 > X
4:3:2   4/13 > X > 2/7, interval=0.021978021978;  M=3/10 > X
p/q=[0, 3, 2]=2/7
None:2:1   2/7 < X < 3/10, interval=0.0142857142857;  M=5/17 > X
None:4:2   2/7 < X < 5/17, interval=0.00840336134454;  M=9/31 < X
4:3:2   9/31 < X < 5/17, interval=0.00379506641366;  M=7/24 < X
p/q=[0, 3, 2, 2]=5/17
None:2:1   5/17 > X > 7/24, interval=0.00245098039216;  M=12/41 < X
None:4:2   5/17 > X > 12/41, interval=0.00143472022956;  M=22/75 > X
4:3:2   22/75 > X > 12/41, interval=0.000650406504065;  M=17/58 > X
p/q=[0, 3, 2, 2, 2]=12/41
None:2:1   12/41 < X < 17/58, interval=0.000420521446594;  M=29/99 > X
None:4:2   12/41 < X < 29/99, interval=0.000246366100025;  M=53/181 < X
4:3:2   53/181 < X < 29/99, interval=0.000111613371282;  M=41/140 < X
p/q=[0, 3, 2, 2, 2, 2]=29/99
None:2:1   29/99 > X > 41/140, interval=7.21500721501e-05;  M=70/239 < X
None:4:2   29/99 > X > 70/239, interval=4.226364059e-05;  M=128/437 > X
4:3:2   128/437 > X > 70/239, interval=1.91492009996e-05;  M=99/338 > X
p/q=[0, 3, 2, 2, 2, 2, 2]=70/239
None:2:1   70/239 < X < 99/338, interval=1.23789953207e-05;  M=169/577 > X
None:4:2   70/239 < X < 169/577, interval=7.2514738621e-06;  M=309/1055 < X
4:3:2   309/1055 < X < 169/577, interval=3.28550190148e-06;  M=239/816 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577
None:2:1   169/577 > X > 239/816, interval=2.12389981991e-06;  M=408/1393 < X
None:4:2   169/577 > X > 408/1393, interval=1.24415093544e-06;  M=746/2547 < X
None:8:4   169/577 > X > 746/2547, interval=6.80448470014e-07;  M=1422/4855 < X
None:16:8   169/577 > X > 1422/4855, interval=3.56972657711e-07;  M=2774/9471 > X
16:12:8   2774/9471 > X > 1422/4855, interval=1.73982239227e-07;  M=2098/7163 > X
12:10:8   2098/7163 > X > 1422/4855, interval=1.15020646951e-07;  M=1760/6009 > X
10:9:8   1760/6009 > X > 1422/4855, interval=6.85549088053e-08;  M=1591/5432 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432
None:2:1   1591/5432 < X < 1760/6009, interval=3.06364213998e-08;  M=3351/11441 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009
None:2:1   1760/6009 > X > 3351/11441, interval=1.45456726663e-08;  M=5111/17450 < X
None:4:2   1760/6009 > X > 5111/17450, interval=9.53679318849e-09;  M=8631/29468 < X
None:8:4   1760/6009 > X > 8631/29468, interval=5.6473816179e-09;  M=15671/53504 < X
None:16:8   1760/6009 > X > 15671/53504, interval=3.11036635336e-09;  M=29751/101576 > X
16:12:8   29751/101576 > X > 15671/53504, interval=1.47201634215e-09;  M=22711/77540 > X
12:10:8   22711/77540 > X > 15671/53504, interval=9.64157420569e-10;  M=19191/65522 > X
10:9:8   19191/65522 > X > 15671/53504, interval=5.70501257346e-10;  M=17431/59513 > X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504
None:2:1   15671/53504 < X < 17431/59513, interval=3.14052228667e-10;  M=33102/113017 == X

由于Python从一开始就处理biginteger数学，并且该程序仅使用整数数学(区间计算除外)，因此它应适用于任意有理数。

edit 3 :证明它是O(log q)而不是O(log ^ 2 q)的证明大纲:

首先请注意，在找到有理数之前，每个新的连续分数项的步骤nk的位数恰好是2b(a_k)-1，其中b(a_k)是表示a_k = ceil(log2(a_k)所需的位数。 ):扩宽二进位搜寻的「网」需要b(a_k)步，而收窄二阶是b(a_k)-1步。参见上面的示例，您会注意到步骤数始终为1、3、7、15等。

现在，我们可以使用递归关系qk = akqk-1 + qk-2和归纳法证明所需的结果。

让我们以这种方式陈述它:达到第k个项所需的Nk = sum(nk)个步骤之后的q值具有最小值:对于某些固定常数A，c，q> = A * 2cN。 (因此，反过来，我们将得到步骤N的数目
基本案例:

k = 0:q = 1，N = 0，所以q> = 2N

k = 1:对于N = 2b-1步，q = a1> = 2b-1 = 2(N-1)/ 2 = 2N / 2 / sqrt(2)。

这意味着A = 1，c = 1/2可以提供所需的界限。实际上，q可能不会使每个项加倍(反例:[0; 1，1，1，1，1，1]的增长因子为phi =(1 + sqrt(5))/ 2)，所以让我们使用c = 1 / 4。

感应:

词项k的

，qk = akqk-1 + qk-2。同样，对于该项所需的nk = 2b-1步，ak> = 2b-1 = 2(nk-1)/ 2。

所以akqk-1> = 2(Nk-1)/ 2 * qk-1> = 2(nk-1)/ 2 * A * 2Nk-1 / 4 = A * 2Nk / 4 / sqrt(2)* 2nk / 4。

Argh-这里最困难的部分是，如果ak = 1，则对于该一项，q可能不会增加太多，我们需要使用qk-2，但它可能比qk-1小得多。