任意有理数的“猜数”游戏？

我曾经有过面试的问题：

我正在考虑一个正整数n。 提出一个可以在O（lg n）查询中猜测的algorithm。 每个查询都是您select的数字，我会回答“低”，“高”或“正确”。

这个问题可以通过一个修改的二进制search来解决，在这个search中列出两个幂，直到find一个超过n的值，然后在该范围内运行一个标准的二进制search。 我认为对此非常酷的是，你可以search一个特定的数字无限的空间比蛮力更快。

但是，我有这个问题的一个小的修改。 假设我select了一个0到1之间的任意有理数 ，而不是select一个正整数。 我的问题是：什么algorithm可以用来最有效地确定我select了哪个有理数？

现在，我所拥有的最好的解决scheme可以通过隐式地步行斯特恩 – 布罗科特树 （ Stern-Brocot tree ）来find最多O（q）时间的p / q，二叉search树覆盖所有的合理性。 然而，我希望得到一个更接近运行时的运行时，我们得到的整数情况下，可能是像O（lg（p + q））或O（lg pq）。 有谁知道一种方法来获得这种types的运行时间？

我最初考虑使用区间[0，1]的标准二进制search，但是这只能find有重复二进制表示的有理数，这几乎是所有的有理数。 我也想过用一些其他的方法来列举理性，但是我似乎无法find一种比较大/相等/较less比较的方法来search这个空间。

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

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

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

令Q（X，p / q）= sign（X – p / q）为查询函数：如果它是0，我们猜测数字，如果是+/- 1则告诉我们错误的符号。

传统的连续分数表示法是A = [a 0 ; a 1 ，a 2 ，a 3 ，… a k ]

= a 0 + 1 /（a 1 + 1 /（a 2 + 1 /（a 3 + 1 /（… + 1 / a k ）…）））

我们将遵循以下algorithm0 <p / q <1。

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

  2. 外环 ： 前提条件是：

    • Y和Z是连续的k + 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和对于奇数，Z <X <Y。

  3. 将连续分数的程度延长1步，而不改变数字的值。 一般情况下，如果最后的项是y k和y k + 1，我们改变为[… y k ，y k + 1 =∞]和[… y k ，z k + 1 = 1]。 现在增加1。

  4. 内循环 ：这与@ templatetypedef关于整数的面试问题基本相同。 我们做一个两阶段的二进制search来接近：

  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. 执行二分search：计算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/11 = 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的每个步骤中，间隔的范围减小。 这可能相当容易certificate（尽pipe我不会这样做）在每一步中间隔至less减less了1 / sqrt（5），这将表明这个algorithm是O（log q）个步骤。

请注意，这可以与templatetypedef的原始面试问题相结合，通过首先计算Q（X，0），然后针对任意正数/负数整数，在两个连续整数，然后对小数部分使用上述algorithm。

当我有机会时，我会发布一个实现这个algorithm的Python程序。

编辑 ：另外，请注意，您不必计算每个步骤中的连续分数（这将是O（k），有连续分数的部分近似值，可以计算O（1）中上一步的下一步。 ）

编辑2 ：部分近似的recursion定义：

如果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 ）/ ）。 从这里可以看出| YZ | 在这个algorithm产生的每个更小的区间内至less减less1 / 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从一开始就处理bigintegermath，而且这个程序只使用整数（除了间隔计算），它应该适用于任意的理性。

编辑3 ：certificate这是O（log q）的概要，而不是O（log ^ 2 q）：

首先注意，直到find有理数为止，每个新的连续分数项的步数n k 恰好是 2b（a_k）-1，其中b（a_k）是表示a_k = ceil所需的比特数（log2（a_k） ））：这是b（a_k）步骤来扩大二进制search的“networking”，b（a_k）-1步骤来缩小它）。 看上面的例子，你会注意到＃的步骤总是1，3，7，15等

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

让我们用这种方式来表述：到达第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> = 2N
  • 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]具有phi =（1 + sqrt（5））/ 2的增长因子，所以让我们用c = 1 / 4。

感应：

  • 对于项k，q k = a k q k-1 + q k-2 。 同样，对于这个项所需的nk = 2b-1个步骤， k > = 2 b-1 = 2 （n k -1）/ 2 。

    因此， k 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 。

阿格 – 这里最棘手的部分是，如果一个k = 1，那么q可能不会增加太多，我们需要使用q k-2，但可能比q k-1小得多。

让我们把有理数以简化的forms写出来，先按分母，然后再按分子的顺序写出来。 

 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个猜测来search该列表。 那么我们将沿着这个清单走，直到我们剩余的范围内有7个。 然后，我们将采取3个猜测来search该列表。 等等。

在n步骤中，我们将涵盖前2 O(n)可能性，这是您所寻找的效率的数量级。

更新：人们没有得到这个背后的推理。 推理很简单。 我们知道如何有效地走二叉树。 有最大分母n O(n 2 )分数。 因此，我们可以在O(2*log(n)) = O(log(n))步骤中search任何特定的分母大小。 问题是，我们有无数的可能的理性search。 所以我们不能把所有的东西都排成一列，然后命令它们，然后开始search。

因此，我的想法是排队，search，排队，search，等等。 每次我们排队的时候，我们排队的时间大概是我们上次做的时间的两倍。 所以我们需要比上次更多的猜测。 所以我们的第一遍用1个猜测来遍历1个可能的理性。 我们第二次使用2个猜测来遍历3个可能的理由。 我们第三次使用3个猜测来遍历7个可能的理由。 而我们的第k次使用k猜测来遍历2 k -1可能的合理性。 对于任何特定的理性m/n ，最终都会把理性放在一个相当大的清单上，以便知道如何有效地进行二分search。

如果我们进行了二分search，那么当我们抓取更多的理性时，忽略了我们学到的所有东西，然后我们把所有的理由都包含在O(log(n))遍中。 （那是因为到那时候我们会得到一个足够有理的传球来包括每一个理性，包括m/n 。但是每个传球需要更多的猜测，所以这将是O(log(n) 2 )猜测。

但是，我们实际上做得比这更好。 用我们的第一个猜测，我们排除了名单上的一半是太大还是小的理由。 我们接下来的两个猜测并没有把这个空间切割成几个方面，但是它们并没有太大的距离。 我们接下来的三次猜测再也没有把这个空间缩减到八分之一，但是距离它们并不太远。 等等。 当你把它放在一起，我相信结果是你findO(log(n))步骤中的m/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个猜测find答案。 我试了0.98765，花了45个猜测。 我试了0.0123456789，需要66个猜测，大约一秒钟才能生成。 （注意，如果你用一个有理数的参数来调用这个程序，它会为你填充所有的猜测值，这是一个非常有用的方便。）

我懂了！ 你需要做的是使用平分search和连续分数 。

二等分将给你一个特定的实数的限制，用二的幂来表示，连续的分数将取实数并find最接近的有理数。

如何并行运行它们如下。

在每一步，你都有l和u是平分的下限和上限。 这个想法是，你可以在减半的范围之间进行select，并且增加一个作为连续分数表示的附加项。 当l和u都与下一个连续分数相同时，则继续分数search中的下一个步骤，并使用连续分数进行查询。 否则，您使用二分法将范围减半。

由于两种方法都至less使分母增加一个常数因子（二分因子为2，所以连续分数至less是因子=（1 + sqrt（5））/ 2），这意味着你的search应该是O （日志（q））。 （可能会重复连续分数计算，因此可能会以O（log（q）^ 2）结束。

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

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

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

  2. l = 0，u = 1/2，query = 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. 1 = 1/32，u = 1/16。 现在1 / l = 32，1 / u = 16，这些有不同的cfrac代表，所以保持平分，query = 3/64。

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

  8. 1 = 1/32，U = 5/128，查询= 9/256 = 1 / 28.4444 ….

  9. 1 = 1/32，u = 9/256，query = 17/512 = 1 / 30.1176 …（round to 1/30）

  10. 1 = 1/32，u = 17/512，query = 33/1024 = 1 / 31.0303 …（round to 1/31）

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

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

成功！

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

[待续，我必须去某个地方]

进一步反思，继续分数是要走的路，除了确定下一个任期，别介意平分。 当我回来的时候更多。

我想我find了一个O（log ^ 2（p + q））algorithm。

为了避免在下一段中出现混淆，“询问”是指猜测者给予挑战者猜测时，挑战者响应“更大”或“更小”。 这使我可以保留“猜测”这个词来代表其他的东西，而不是直接向挑战者提问。

这个想法是首先findp + q，使用你在问题中描述的algorithm：猜测一个值k，如果k太小，加倍，然后再试一次。 然后一旦你有一个上下限，做一个标准的二进制search。 这需要O（log（p + q）T）个查询，其中T是查询猜测数量的上限。 我们来找T.

我们想检查所有分数r / s r + s <= k，并且双k直到k足够大。 请注意，您需要检查给定的k值是否有O（k ^ 2）个分数。 构build一个包含所有这些值的平衡二叉search树，然后search它以确定p / q是否在树中。 需要O（log k ^ 2）= O（log k）查询来确认p / q不在树中。

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

当我们猜测k的正确值（即k = p + q）时，我们将在查询k的猜测过程中向查询者提交查询p / q，并赢得游戏。

总的查询数是O（log ^ 2（p + q））。

好吧，我想我find了一个基于Jason S关于使用连续分数的最佳见解的O（lg 2 q）algorithm。 我想我会一直在这里充实algorithm，以便我们有一个完整的解决scheme，以及一个运行时分析。

algorithm背后的直觉是，范围内的任何有理数p / q都可以写成

a 0 + 1 /（a 1 + 1 /（a 2 + 1 /（a 3 + 1 / …））

为了适当的select我 。 这被称为连续分数 。 更重要的是，尽pipe可以通过在分子和分母上运行欧几里得algorithm来导出这些。 例如，假设我们想用这种方式代表11/14。 我们首先注意到14进入十一次零，所以粗略近似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。 如果我们终于写出来

（1 +（1 + 1 /（3 + 1 /（1 + 1/2））））=（1 / /（1 +（1 /（3 + 2/3））））=（1 /（1 + 1 /（11/3）））） / 11）= 11/14

这正是我们想要的分数。 而且，看看我们最终使用的系数序列。 如果你在11和14上运行扩展的欧几里得algorithm，你可以得到

11 = 0×14 + 11→a0 = 0 14 = 1×11 + 3→a1 = 1 11 = 3×3 + 2→a2 = 3 3 = 2×1 + 1→a3 = 2

事实certificate，（使用更多的math比我现在知道该怎么做！），这不是一个巧合，并且p / q的连续部分中的系数总是通过使用扩展欧几里得algorithm形成的。 这很好，因为它告诉我们两件事：

  1. 最多可以有O（lg（p + q））系数，因为欧几里德algorithm总是在这么多步骤中终止，
  2. 每个系数最多为{p，q}。

考虑到这两个事实，我们可以想出一个algorithm来恢复任何有理数p / q，不仅是0和1之间的那些，通过应用通用algorithm猜测任意整数n一次一个来恢复所有的系数p / q的持续分数。 但现在，我们只关心范围（0,1）中的数字，因为处理任意有理数的逻辑可以很容易地完成，因为这是一个子程序。

作为第一步，假设我们想要find1的最佳值，以使1 / a 1尽可能接近p / q， 1是一个整数。 要做到这一点，我们可以运行我们的algorithm来猜测任意整数，每次都取倒数。 做完这件事之后，会发生两件事情之一。 首先，我们可能巧合地发现对于某个整数k，p / q = 1 / k，在这种情况下，我们就完成了。 如果不是，我们会发现p / q夹在1 /（a 1 – 1）和1 / a 0之间 。 当我们这样做的时候，我们开始继续研究一个更深的级别，通过find一个2使得p / q介于1 /（a 1 + 1 / a 2 ）和1 /（a 1 + 1 /（a 2 + 1））。 如果我们奇迹般地发现p / q，那太棒了！ 否则，我们会继续下一个级别。 最终，我们会以这种方式find号码，而且不会花太长的时间。 每个二进制searchfind一个系数的时间最多为O（lg（p + q））时间，并且最多有O（lg（p + q））级别的search，所以我们只需要O（lg 2 + q））算术运算和探针来恢复p / q。

我想指出的一个细节是，我们需要跟踪在search时是处于奇数还是偶数级，因为当我们将p / q夹在两个连续分数之间时，我们需要知道系数我们正在寻找是上部还是下部。 我会在没有证据的情况下陈述，对于一个我与我很奇怪，你想使用两个数字中的较高者，并且我甚至使用两个数字中较低的一个。

我几乎100％确信这个algorithm的工作原理。 我将试着写出一个更正式的证据，在这个certificate中我填补了这个推理的所有空白，而当我这样做的时候，我会在这里发布一个链接。

感谢大家提供必要的见解，使这个解决scheme的工作，特别是贾森Sbuild议二进制search连续分数。

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

这是另一种方法。 如果有足够的兴趣，我会尽量填写今晚的细节，但现在不行，因为我有家庭责任。 下面是一个应该解释algorithm的实现的一个存根： 

 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)应该做的是find最后的分母近似于x的分母最多的bound 。 这个algorithm将采取多项式步骤来完成，并find非常好的（虽然不总是最好的）近似值。 所以对于每一个bound我们将得到一个接近二进制search的东西，通过所有可能的分数的大小。 偶尔我们不会find一个特定的分数，直到我们增加的边界比我们应该更远，但我们不会离得很远。

所以你有它。 在multithreading工作中发现的对数数量的问题。

更新：完整的工作代码。 

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

它比前面的解决scheme在猜测上看起来稍微有效一些，而且操作less得多。 101/1024需要19次猜测和251次操作。 对于.98765，它需要27个猜测和623个操作。 对于0.0123456789，需要66次猜测和889次操作。 而对于咯咯笑声，0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789（这是上一张的10份），需要665次猜测和23289次操作。

You can sort rational numbers in a given interval by for example the pair (denominator, numerator). Then to play the game you can

  1. Find the interval [0, N] using the doubling-step approach
  2. Given an interval [a, b] shoot for the rational with smallest denominator in the interval that is the closest to the center of the interval

this is however probably still O(log(num/den) + den) (not sure and it's too early in the morning here to make me think clearly 😉 )

Interesting Posts