algorithm - "guess the number"任意有理数的游戏？

Question

我曾经在面试中得到以下问题:

I'm thinking of a positive integer n. Come up with an algorithm that can guess it in O(lg n) queries. Each query is a number of your choosing, and I will answer either "lower," "higher," or "correct."

这个问题可以通过修改后的二分搜索来解决，其中列出 2 的幂，直到找到超过 n 的幂，然后在该范围内运行标准二分搜索。我认为这很酷的是，您可以比蛮力更快地搜索特定数字的无限空间。

不过，我的问题是对这个问题稍作修改。假设我选择了一个 ，而不是选择一个正整数。任意有理数零和一之间。我的问题是:你可以使用什么算法来最有效地确定我选择了哪个有理数？

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

我最初考虑使用区间 [0, 1] 的标准二进制搜索，但这只会找到具有非重复二进制表示的有理数，这几乎错过了所有有理数。我还考虑过使用其他一些枚举有理数的方法，但我似乎无法找到一种方法来搜索这个空间，因为只有更大/相等/更少的比较。

Answer 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 < p/q < 1，我们将遵循以下算法。

初始化 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) < 0 < (-1)k(Z-X)，或者更简单地说，对于 k 偶数，Y < X < Z 和对于 k 奇数，Z < X < Y。

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

内循环 :这与@templatetypedef 关于整数的面试问题本质上相同。我们进行了两阶段二分搜索以接近:

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

Double 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 的原始面试问题相结合，并适用于任何有理数 p/q，而不仅仅是在 0 和 1 之间，首先计算 Q(X,0)，然后对于正/负整数，在两个连续的整数，然后对小数部分使用上述算法。

下次有机会我会贴出实现这个算法的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，第 4 版，定理 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 从一开始就处理大整数数学，并且该程序仅使用整数数学(区间计算除外)，因此它应该适用于任意有理数。

编辑 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 的数量 <= (1/c) * log2 (q/A) = O(log q)。)

基本情况:

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] 的增长因子为 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.

啊——这里的难点在于，如果 ak = 1，那一项的 q 可能不会增加太多，我们需要使用 qk-2 但它可能比 qk-1 小得多。