77

我曾经收到以下面试问题：

我在想一个正整数n。想出一个可以在 O(lg n) 查询中猜测它的算法。每个查询都是您选择的数字，我将回答“较低”、“较高”或“正确”。

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

不过，我的问题是对这个问题的轻微修改。假设我选择了一个介于 0 和 1 之间的任意有理数，而不是选择一个正整数。我的问题是：你可以使用什么算法来最有效地确定我选择的有理数？

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

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

4

8 回答 8

50

好的，这是我单独使用连分数的答案。

首先让我们在这里了解一些术语。

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

让 Q(X,p/q) = sign(X - p/q) 成为查询函数：如果它是 0，我们已经猜到了这个数字，如果它是 +/- 1，则告诉我们错误的符号.

连分数的传统表示法是 A = [a 0 ; 一个1 , 一个2 , 一个3 , ... 一个k ]

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

对于 0 < p/q < 1，我们将遵循以下算法。

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

  2. 外循环：前提是：

    • Y 和 Z 是 k+1 项的连分数，除了在最后一个元素中它们是相同的，它们相差 1，因此 Y = [y 0 ; y 1 , y 2 , y 3 , ... y k ] 和 Z = [y 0 ; y 1 , y 2 , y 3 , ... y k + 1]

    • (-1) k (YX) < 0 < (-1) k (ZX)，或者更简单地说，对于 k 偶数，Y < X < Z 并且对于 k 奇数，Z < X < Y。

  3. 在不改变数字值的情况下将连分数的次数扩大 1 步。一般来说，如果最后一项是 y k和 y k + 1，我们将其更改为 [... y k , y k+1 =∞] 和 [... y k , z k+1 =1]。现在将 k 增加 1。

  4. 内循环：这与@templatetypedef 关于整数的面试问题基本相同。我们进行两阶段二分搜索以更接近：

  5. 内环 1：y k = ∞，z k = a，X 在 Y 和 Z 之间。

  6. 双 Z 的最后一项：计算 M = Z 但使用 m k = 2*a = 2*z k。

  7. 查询未知数：q = Q(X,M)。

  8. 如果 q = 0，我们有答案并转到第 17 步。

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

  10. 否则设置 Y = M 并进入下一步：

  11. 内循环 2. y k = b, z k = a, X 在 Y 和 Z 之间。

  12. 如果 a 和 b 相差 1，则交换 Y 和 Z，转到步骤 2。

  13. 执行二分查找：计算 M，其中 m k = floor((a+b)/2，查询 q = Q(X,M)。

  14. 如果 q = 0，我们完成并转到第 17 步。

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

  16. 否则 q 和 Q(X,Z) 符号相反，表示 X 在 Z 和 M 之间，所以设置 Y = M 并转到步骤 11。

  17. 完成：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：部分近似值的递归定义：

如果 A k = [a 0 ; a 1 , a 2 , a 3 , ... a k ] = p k /q k , 然后 p k = a k p k-1 + p k-2 , q k = a k q k-1 + q k-2。（来源：Niven & Zuckerman，第 4 版，定理 7.3-7.5。另见维基百科）

示例： [0] = 0/1 = p 0 /q 0 , [0; 7] = 1/7 = p 1 /q 1 ; 所以 [0; 7, 16] = (16*1+0)/(16*7+1) = 16/113 = p 2 /q 2。

这意味着如果两个连分数 Y 和 Z 除了最后一项之外有相同的项，并且不包括最后一项的连分数是 p k-1 /q k-1，那么我们可以写 Y = (y k p k- 1 + p k-2 ) / (y k q k-1 + q k-2 ) 和 Z = (z k p k-1 + p k-2 ) / (z k q k-1 + q k-2）。应该可以证明|YZ| 在该算法产生的每个较小间隔处至少减少 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）的大纲：

首先注意，在找到有理数之前，每个新的连分数项的步数 n k正好是2b(a_k)-1 其中 b(a_k) 是表示 a_k = ceil(log2(a_k ))：它是 b(a_k) 步骤来扩大二分搜索的“网络”，而 b(a_k)-1 步骤来缩小它）。请参阅上面的示例，您会注意到步数始终为 1、3、7、15 等。

现在我们可以使用递归关系 q k = a k q k-1 + q k-2和归纳来证明期望的结果。

让我们这样说明：在达到第 k 项所需的 N k = sum(n k ) 步骤之后，q 的值具有最小值：对于某些固定常数 A,c， q >= A*2 cN 。（所以要反转，我们会得到步骤数 N <= (1/c) * log 2 (q/A) = O(log q)。）

基本情况：

  • k=0: q = 1, N = 0, 所以 q >= 2 N
  • k=1：对于 N = 2b-1 步，q = a 1 >= 2 b-1 = 2 (N-1)/2 = 2 N/2 /sqrt(2)。

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

就职：

  • 对于术语 k，q k = a k q k-1 + q k-2。同样，对于本项所需的 n k = 2b-1 步骤， a k >= 2 b-1 = 2 (n k -1)/2。

    所以 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。

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

于 2011-03-26T22:56:16.933 回答
6

让我们以简化的形式取有理数，然后按分母的顺序写出来，然后是分子。

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

我们的第一个猜测是1/2。然后我们将沿着列表前进，直到我们的范围内有 3 个。然后我们将进行 2 次猜测来搜索该列表。然后我们将沿着列表继续，直到我们的剩余范围内有 7 个。然后我们将进行 3 次猜测来搜索该列表。等等。

在n步骤中，我们将介绍第一种可能性，这是您正在寻找的效率数量级。2O(n)

更新：人们没有得到这背后的原因。道理很简单。我们知道如何有效地遍历二叉树。有最大分母的分数。因此，我们可以逐步搜索到任何特定的分母大小。问题是我们有无数可能的有理数要搜索。所以我们不能把它们全部排好，排序，然后开始搜索。O(n2)nO(2*log(n)) = O(log(n))

因此我的想法是排队一些，搜索，排队更多，搜索，等等。每次我们排队更多时，我们排队的人数大约是上次的两倍。所以我们需要比上次更多的猜测。因此，我们的第一遍使用 1 个猜测来遍历 1 个可能的有理数。我们的第二个使用 2 个猜测来遍历 3 个可能的有理数。我们的第三个使用 3 个猜测来遍历 7 个可能的有理数。我们k的 'th 使用k猜测来遍历可能的有理数。对于任何特定的有理数，最终它将把那个有理数放在一个相当大的列表中，它知道如何有效地进行二分搜索。2k-1m/n

如果我们进行二分搜索，然后在我们抓取更多有理数时忽略我们学到的所有内容，那么我们会将所有有理数放在并包括m/n在O(log(n))pass 中。（那是因为到那时，我们将通过足够的有理数来包含直到并包括 的所有有理数m/n。）但是每次通过都需要更多的猜测，所以这将是猜测。O(log(n)2)

然而，我们实际上做得比这要好得多。通过我们的第一个猜测，我们消除了列表中一半的有理数太大或太小。我们接下来的两个猜测并没有将空间分成四等份，但它们并没有离它太远。我们接下来的 3 次猜测并没有完全将空间缩小到八分之一，但它们并没有离它太远。等等。当你把它放在一起时，我相信结果是你m/n在O(log(n))步骤中找到的。虽然我实际上没有证据。

试试看：这里是生成猜测的代码，这样你就可以玩，看看它的效率如何。

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

作为尝试的示例，我尝试了 101/1024 (0.0986328125)，发现需要 20 次猜测才能找到答案。我试了 0.98765，猜了 45 次。我尝试了 0.0123456789，它需要 66 次猜测和大约一秒钟的时间来生成它们。（注意，如果你用一个有理数作为参数调用程序，它会为你填写所有的猜测。这是一个非常有用的方便。）

于 2011-03-26T07:40:09.733 回答
4

我懂了！您需要做的是使用带有二分和连分数的并行搜索。

二分法会给你一个特定实数的限制，表示为 2 的幂，连分数将取实数并找到最接近的有理数。

您如何并行运行它们如下。

在每一步，你都有l并且u是二等分的下界和上界。这个想法是，您可以在将二分范围减半和添加一个附加项作为连分数表示之间进行选择。当两者l和u具有与连分数相同的下一项时，您将在连分数搜索中进行下一步，并使用连分数进行查询。否则，您使用二分法将范围减半。

由于这两种方法都将分母增加了至少一个常数因子（二分法乘以 2，连分式至少乘以 phi = (1+sqrt(5))/2），这意味着您的搜索应该是 O (log(q))。（可能有重复的连分数计算，所以它可能最终为 O(log(q)^2)。）

我们的连分数搜索需要四舍五入到最接近的整数，而不是使用下限（这在下面更清楚）。

以上是一种手摇。让我们用一个 r = 1/31 的具体例子：

  1. l = 0，u = 1，查询 = 1/2。0 不能表示为连分数，所以我们使用二分查找直到 l != 0。

  2. l = 0，u = 1/2，查询 = 1/4。

  3. l = 0，u = 1/4，查询 = 1/8。

  4. l = 0，u = 1/8，查询 = 1/16。

  5. l = 0，u = 1/16，查询 = 1/32。

  6. l = 1/32，u = 1/16。现在 1/l = 32, 1/u = 16，它们有不同的 cfrac 代表，所以继续平分。，查询 = 3/64。

  7. l = 1/32，u = 3/64，查询 = 5/128 = 1/25.6

  8. l = 1/32，u = 5/128，查询 = 9/256 = 1/28.4444....

  9. l = 1/32，u = 9/256，查询 = 17/512 = 1/30.1176...（四舍五入到 1/30）

  10. l = 1/32，u = 17/512，查询 = 33/1024 = 1/31.0303...（四舍五入到 1/31）

  11. l = 33/1024，u = 17/512，查询 = 67/2048 = 1/30.5672...（四舍五入到 1/31）

  12. l = 33/1024，u = 67/2048。此时 l 和 u 都有相同的连分数项 31，所以现在我们使用连分数猜测。查询 = 1/31。

成功！

再举一个例子，让我们使用 16/113（= 355/113 - 3，其中 355/113 非常接近 pi）。

[未完待续，我要去一个地方]

进一步思考，连分数是要走的路，除了确定下一项外，别介意二分法。当我回来的时候更多。

于 2011-03-26T14:11:46.350 回答
3

好的，我想我为这个问题找到了一个 O(lg 2 q) 算法，它基于 Jason S 关于使用连分数的最出色的见解。我想我会在这里一直充实算法，以便我们有一个完整的解决方案，以及运行时分析。

该算法背后的直觉是范围内的任何有理数 p/q 都可以写为

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

为了适当的选择。这称为连分数。更重要的是，尽管这些 a i可以通过在分子和分母上运行欧几里得算法来导出。例如，假设我们想以这种方式表示 11/14。我们首先注意到 14 进入 11 个零次，因此 11/14 的粗略近似值是

0 = 0

现在，假设我们取这个分数的倒数得到 14/11 = 1 3 / 11。所以如果我们写

0 + (1 / 1) = 1

我们得到了 11/14 的更好的近似值。现在我们剩下 3 / 11，我们可以再次取倒数得到 11/3 = 3 2 / 3，所以我们可以考虑

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

这是 11/14 的另一个很好的近似值。现在，我们有 2/3，所以考虑倒数，即 3/2 = 1 1 / 2。如果我们再写

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

我们得到了 11/14 的另一个很好的近似值。最后，我们剩下 1/2，它的倒数是 2/1。如果我们最终写出

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

这正是我们想要的分数。此外，看看我们最终使用的系数序列。如果你在 11 和 14 上运行扩展欧几里得算法，你会得到

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

事实证明（使用的数学比我目前知道的要多！）这不是巧合，p/q 的连分数中的系数总是使用扩展的欧几里得算法形成的。这很棒，因为它告诉我们两件事：

  1. 最多可以有 O(lg (p + q)) 个系数，因为欧几里得算法总是在这么多步骤中终止，并且
  2. 每个系数最多为 max{p, q}。

鉴于这两个事实，我们可以提出一种算法来恢复任何有理数 p/q，而不仅仅是那些介于 0 和 1 之间的有理数，通过应用一次猜测任意整数 n 的通用算法来恢复p/q 的连分数。不过，现在我们只关心 (0, 1] 范围内的数字，因为处理任意有理数的逻辑可以很容易地作为一个子程序来完成。

作为第一步，让我们假设我们想要找到 a 1 的最佳值，以便1 / a 1尽可能接近 p/q 并且 a 1是一个整数。为此，我们可以运行我们的算法来猜测任意整数，每次取倒数。完成此操作后，将发生两件事之一。首先，我们可能完全巧合地发现对于某个整数 k，p/q = 1/k，在这种情况下，我们就完成了。如果不是，我们会发现 p/q 夹在 1/(a 1 - 1) 和 1/a 0之间，对于一些 a 1。当我们这样做时，我们通过找到 a 2使得 p/q 在 1/(a 1 + 1/a2 ) 和 1/(a 1 + 1/(a 2 + 1))。如果我们神奇地找到 p/q，那就太好了！否则，我们将在连分数中进一步下降一级。最终，我们会以这种方式找到号码，而且不会花费太长时间。每次二分查找查找系数最多花费 O(lg(p + q)) 时间，并且搜索最多有 O(lg(p + q)) 级，所以我们只需要 O(lg 2 (p + q)) 算术运算和探测以恢复 p/q。

我想指出的一个细节是，在进行搜索时，我们需要跟踪我们是处于奇数水平还是偶数水平，因为当我们将 p/q 夹在两个连分数之间时，我们需要知道系数是否我们正在寻找的是较高或较低的分数。我会在没有证据的情况下声明，对于带有i奇数的 i，您要使用两个数字中的较大者，而对于带有i偶数的 i，您要使用两个数字中的较小者。

我几乎 100% 确信该算法有效。我将尝试写一个更正式的证明来填补这个推理中的所有空白，当我这样做时，我会在这里发布一个链接。

感谢大家为使该解决方案工作提供必要的见解，特别是 Jason S 建议对连分数进行二分搜索。

于 2011-03-26T22:51:06.460 回答
3

我想我找到了一个 O(log^2(p + q)) 算法。

为避免在下一段中混淆，“查询”是指猜测者给挑战者一个猜测，而挑战者回应“更大”或“更小”。这使我可以将“猜测”一词保留为其他内容，即不直接向挑战者询问的 p + q 猜测。

这个想法是首先找到p + q，使用您在问题中描述的算法：猜测一个值k，如果k太小，将其加倍并重试。然后，一旦有了上限和下限，就可以进行标准的二进制搜索。这需要 O(log(p+q)T) 次查询，其中 T 是检查猜测所需的查询次数的上限。让我们找到T。

我们要检查所有分数 r/s，其中 r + s <= k，然后将 k 加倍，直到 k 足够大。请注意，对于给定的 k 值，您需要检查 O(k^2) 个分数。建立一个包含所有这些值的平衡二叉搜索树，然后搜索它以确定 p/q 是否在树中。需要 O(log k^2) = O(log k) 查询来确认 p/q 不在树中。

我们永远不会猜测大于 2(p + q) 的 k 值。因此我们可以取 T = O(log(p+q))。

当我们猜出 k 的正确值（即 k = p + q）时，我们将在检查我们对 k 的猜想的过程中将查询 p/q 提交给挑战者，并赢得比赛。

查询总数为 O(log^2(p + q))。

于 2011-03-26T08:15:44.133 回答
2

这是另一种方法。如果有足够的兴趣，我今晚会尝试填写详细信息，但我现在不能，因为我有家庭责任。这是应该解释算法的实现的存根：

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)

这是解释。应该做best_continued_fraction(x, bound)的是找到x与分母最多的最后一个连分数逼近bound。该算法将采用 polylog 步骤来完成并找到非常好的（尽管并不总是最好的）近似值。因此，对于每个bound我们将通过该大小的所有可能部分得到接近二分搜索的结果。有时我们不会找到一个特定的分数，直到我们将界限增加得比我们应该的更远，但我们不会离得太远。

所以你有它。用 polylog 工作找到的对数问题。

更新：和完整的工作代码。

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

与之前的解决方案相比，它的猜测效率略高，并且执行的操作要少得多。对于 101/1024，它需要 19 次猜测和 251 次操作。对于 .98765，它需要 27 次猜测和 623 次操作。对于 0.0123456789，它需要 66 次猜测和 889 次操作。对于 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 （这需要 10 个副本和之前的操作 266） 0.012345678901234567890123666

于 2011-03-26T21:02:38.087 回答
2

请记住，(0, 1) 中的任何有理数都可以表示为不同（正或负）单位分数的有限和。例如，2/3 = 1/2 + 1/6 和 2/5 = 1/2 - 1/10。您可以使用它来执行直接的二进制搜索。

于 2011-03-26T12:45:58.323 回答
0

您可以通过例如对（分母，分子）对给定区间内的有理数进行排序。然后玩游戏就可以了

  1. [0, N]使用双步法求区间
  2. 给定一个区间[a, b]，在最接近区间中心的区间中寻找分母最小的有理数

然而，这可能仍然存在O(log(num/den) + den)（不确定，现在早上太早了，让我想清楚;-)）

于 2011-03-26T07:37:53.930 回答