在＆QUOT;猜数＆QUOT;游戏中任意有理数？ [英] The "guess the number" game for arbitrary rational numbers?

问题描述

有一次，我得到了下面的一个面试问题：

I once got the following as an interview question:

我在想一个正整数n的。想出一种算法，可以在O（LG N）查询猜测它。每个查询是一些你选择的，我会回答不是低，高或正确的。

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."

此问题可以通过修改后的二进制搜索，在其中列出的两个大国，直到你找到一个超过n，则运行在该范围标准的二进制搜索来解决。我认为是太酷了这个是你可以搜索特定的数字空间无限快不仅仅是蛮力。

This problem can be solved by a modified binary search, in which you listing powers of two until you find one that exceeds n, then run a standard binary search over that range. What I think is so cool about this is that you can search an infinite space for a particular number faster than just brute-force.

我的问题，虽然是轻微的这一问题进行修改。相反，选择一个正整数，假设我选0和1之间的任意有理数。我的问题是：你可以用什么算法最有效地确定哪些有理数我挑选

The question I have, though, is a slight modification of this problem. Instead of picking a positive integer, suppose that I pick an arbitrary rational number between zero and one. My question is: what algorithm can you use to most efficiently determine which rational number I've picked?

目前，最好的解决办法我已经能够通过隐含走的斯特恩Brocot树的，在所有的有理数二叉搜索树。不过，我希望能得到一个运行时更接近，我们得到的整数的情况下运行时，可能像O（LG电子（P + Q））或O（LG PQ）。有谁知道的一种方式来获得这种运行时？

Right now, the best solution I have can find p/q in at most O(q) time by implicitly walking the Stern-Brocot tree, a binary search tree over all the rationals. However, I was hoping to get a runtime closer to the runtime that we got for the integer case, maybe something like O(lg (p + q)) or O(lg pq). Does anyone know of a way to get this sort of runtime?

我使用间隔的一个标准二进制搜索[0，1]，但这只会发现有理数用非重复二进制重新presentation，这几乎射门所有有理数的最初考虑。我也想过用枚举有理数的一些其他的方式，但我似乎无法找到一个方法来搜索这个空间给刚大于/等于/更少的对比。

I initially considered using a standard binary search of the interval [0, 1], but this will only find rational numbers with a non-repeating binary representation, which misses almost all of the rationals. I also thought about using some other way of enumerating the rationals, but I can't seem to find a way to search this space given just greater/equal/less comparisons.

推荐答案

好了，这是一个使用我的答案连分数独。

Okay, here's my answer using continued fractions alone.

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

First let's get some terminology here.

设X = P / Q是未知的分数。

Let X = p/q be the unknown fraction.

让Q（x，P / Q）=符号（X - P / Q）是查询功能：如果它是0，我们猜测的数目，并且如果它是+/- 1告诉我们的符号我们的错误。

Let Q(X,p/q) = sign(X - p/q) be the query function: if it is 0, we've guessed the number, and if it's +/- 1 that tells us the sign of our error.

的<一个href="http://en.wikipedia.org/wiki/Continued_fraction#Notations_for_continued_fractions">conventional记法连分数是A = [A <子> 0 ;一个<子> 1 ，一个 ₂ ，一个<子> 3 ，...一个<子> K ]

The conventional notation for continued fractions is A = [a₀; a₁, a₂, a₃, ... a_k]

= A <子> 0 + 1 /（A <子> 1 + 1 /（A ₂ + 1 /（A _{3 + 1 /（... + 1 / A <子> K} ）...）））

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

我们将遵循以下算法0℃ P / Q＆LT; 1。

We'll follow the following algorithm for 0 < p/q < 1.

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

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

外环：在 preconditions 的是：

• 的K + 1项Y和Z连分数它们除了在最后一个元素，在那里他们由1相同的不同，从而使Y = [Y <子> 0 ;是<子> 1 ，Y ₂ ，Y <子> 3 ，... Y <子> K ]和Z = [Y <子> 0 ;是<子> 1 ，Y ₂ ，Y <子> 3 ，... Y <子> K + 1]

• Y and Z are continued fractions of k+1 terms which are identical except in the last element, where they differ by 1, so that Y = [y₀; y₁, y₂, y₃, ... y_k] and Z = [y₀; y₁, y₂, y₃, ... y_k + 1]

（ - 1） ^K （Y-X）LT; 0℃下（-1） ^K （ZX），或者更简单，对于k连中，Y; X - LT; Z和对于k奇数中，Z; X - LT;年。

(-1)^k(Y-X) < 0 < (-1)^k(Z-X), or in simpler terms, for k even, Y < X < Z and for k odd, Z < X < Y.

1步骤延长的持续部分的程度，而不改变号的值。一般情况下，如果最后条款为Y <子> K 和y <子> K + 1，我们更改为[... Y <子> K ，Y <子> K + 1 =∞]和[... Y <子> K ，Z <子> K + 1 = 1]。现在增加1ķ。

Extend the degree of the continued fraction by 1 step without changing the values of the numbers. In general, if the last terms are y_k and y_k + 1, we change that to [... y_k, y_k+1=∞] and [... y_k, z_k+1=1]. Now increase k by 1.

内环：这是基本相同@ templatetypedef的关于整数面试问题。我们做了两相的二进制搜索，获得更接近：

Inner loops: This is essentially the same as @templatetypedef's interview question about the integers. We do a two-phase binary search to get closer:

内环1 ：Y <子> K =∞，Z <子> K = A，X是Y和Z之间

Inner loop 1: y_k = ∞, z_k = a, and X is between Y and Z.

双Z的最后期限：计算M =ž但其中m <子> K = 2 * A = 2 * Z <子> K

Double Z's last term: Compute M = Z but with m_k = 2*a = 2*z_k.

查询数目不详：Q = Q（X，M）

Query the unknown number: q = Q(X,M).

如果Q = 0，我们有我们的答案，然后转到步骤17。

If q = 0, we have our answer and go to step 17 .

如果Q和Q（X，Y）的符号相反，这意味着X是Y和M之间，所以设置Z = M和转到步骤5。

If q and Q(X,Y) have opposite signs, it means X is between Y and M, so set Z = M and go to step 5.

否则设置Y = M和进入下一个步骤：

Otherwise set Y = M and go to the next step:

内环2。是<子> K = B，Z <子> K = A，X是Y和Z之间

Inner loop 2. y_k = b, z_k = a, and X is between Y and Z.

如果A和B相差1，交换Y和Z，则转到步骤2。

If a and b differ by 1, swap Y and Z, go to step 2.

执行二进制搜索：计算M，其中米<子> K =地板（（A + B）/ 2，查询Q = Q（X，M）

Perform a binary search: compute M where m_k = floor((a+b)/2, and query q = Q(X,M).

如果Q = 0，我们就大功告成了，然后转到步骤17。

If q = 0, we're done and go to step 17.

如果Q和Q（X，Y）的符号相反，这意味着X是Y和M之间，所以设置Z = M和转到步骤11。

If q and Q(X,Y) have opposite signs, it means X is between Y and M, so set Z = M and go to step 11.

否则，Q和Q（X，Z）的符号相反，这意味着X是Z和M之间，所以设置Y = M和转到步骤11。

Otherwise, q and Q(X,Z) have opposite signs, it means X is between Z and M, so set Y = M and go to step 11.

完成：X = M。

一个具体的例子为X =一百十三分之十六= 0.14159292

A concrete example for 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 /开方（5）在每一步的因素，这将表明，该算法是O（登录Q）的步骤减少。

At each step of computing M, the range of the interval reduces. It is probably fairly easy to prove (though I won't do this) that the interval reduces by a factor of at least 1/sqrt(5) at each step, which would show that this algorithm is O(log q) steps.

请注意，这可以与templatetypedef的原始面试问题被组合和应用向的任何的有理数p / q时不只是0和1之间，由第一计算Q（x，0），则对或正/负整数，连续的两个整数之间边界，然后使用上述算法的小数部分。

Note that this can be combined with templatetypedef's original interview question and apply towards any rational number p/q, not just between 0 and 1, by first computing Q(X,0), then for either positive/negative integers, bounding between two consecutive integers, and then using the above algorithm for the fractional part.

当我下一次机会的话，我将发布一个实现该算法Python程序。

When I have a chance next, I will post a python program that implements this algorithm.

修改：另外请注意，您不必计算连分数每一个步骤（这将是O（K），也有部分逼近持续分数可以计算出下一步从澳previous步骤（1）。）

edit: also, note that you don't have to compute the continued fraction each step (which would be O(k), there are partial approximants to continued fractions that can compute the next step from the previous step in O(1).)

修改2 ：局部逼近的递归定义：

edit 2: Recursive definition of partial approximants:

如果A <子> K = [A <子> 0 ;一个<子> 1 ，一个 ₂ ，一个<子> 3 ，...一个<子> K ] = P <子> K / Q <子> K ，那么P <子> K = A <子> K P <子> K-1 + P <子> K-2 和Q <子> K = A <子> K 问：<子> K-1 + Q <子> K-2 。 （来源：尼文和放大器;祖克曼，第4版，定理7.3-7.5参见维基百科）

If A_k = [a₀; a₁, a₂, a₃, ... a_k] = p_k/q_k, then p_k = a_kp_k-1 + p_k-2, and q_k = a_kq_k-1 + q_k-2. (Source: Niven & Zuckerman, 4th ed, Theorems 7.3-7.5. See also Wikipedia)

例如：[0] = 0/1 = P <子> 0 / Q ₀ ，[0; 7] = 1/7 = P <子> 1 / Q ₁ ;因此[0; 7，16] =（16 * 1 + 0）/（16 * 7 + 1）=一百十三分之十六= P ₂ / Q ₂ 。

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

这意味着，如果两个连分数Y和Z具有除了最后一个相同的条款，而连分数不包括最后一项是P <子> K-1 / Q <子> K-1 ，那么我们就可以写Y =（Y <子> K P <子> K-1 + P <子> K-2 ）/（Y <子> K 问：<子> K-1 + Q <子> K-2 ）和Z =（Z <子> K P <子> K-1 + P <子> K-2 ）/（Z <子> K 问：<子> K-1 + Q <子> K-2 ）。它应该有可能从该证明| YZ |降低到1 / SQRT（5）在由这个算法产生的每个小的间隔的至少一个因素，但该代数似乎超越我的时刻。 ： - （

This means that if two continued fractions Y and Z have the same terms except the last one, and the continued fraction excluding the last term is p_k-1/q_k-1, then we can write Y = (y_kp_k-1 + p_k-2) / (y_kq_k-1 + q_k-2) and Z = (z_kp_k-1 + p_k-2) / (z_kq_k-1 + q_k-2). It should be possible to show from this that |Y-Z| decreases by at least a factor of 1/sqrt(5) at each smaller interval produced by this algorithm, but the algebra seems to be beyond me at the moment. :-(

下面是我的Python程序：

Here's my Python program:

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），的确，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数学从一开始，这个程序只使用整数运算（除区间计算），它应该对任意有理数。

Since Python handles biginteger math from the start, and this program uses only integer math (except for the interval calculations), it should work for arbitrary rationals.

修改3 ：证明纲要，这是为O（log Q），而不是为O（log ^ 2 Q）：

edit 3: Outline of proof that this is O(log q), not O(log^2 q):

首先要注意，直到有理数发现，在＃的步数N <子> K 为每个新的连分数任期的完全的2B（a_k）-1，其中B（ a_k）是＃重新present a_k = CEIL（LOG2（a_k））所需的比特的：它是B（a_k）步骤来扩大网的二进制搜索的，和b（a_k）-1的步骤缩小它）。见上面的例子，你会注意到，步骤＃始终为1，3，7，15，等等。

First note that until the rational number is found, the # of steps n_k for each new continued fraction term is exactly 2b(a_k)-1 where b(a_k) is the # of bits needed to represent a_k = ceil(log2(a_k)): it's b(a_k) steps to widen the "net" of the binary search, and b(a_k)-1 steps to narrow it). See the example above, you'll note that the # of steps is always 1, 3, 7, 15, etc.

现在我们可以使用递推关系q <子> K = A <子> K 问：<子> K-1 + Q <子> K-2 和诱导，以证明所期望的结果。

Now we can use the recurrence relation q_k = a_kq_k-1 + q_k-2 and induction to prove the desired result.

让我们说出它以这样的方式在于q的N个<子>后K值 = SUM（N <子> K ）需要达到第k个任期的步骤有一个最低： Q> = A * 2 ^厘对于一些固定的常数A，C。 （所以反转，我们会得到的步数N的＃为＆lt; =（1 / C）*登录 ₂ （Q / A）= O（登录Q）。）

Let's state it in this way: that the value of q after the N_k = sum(n_k) steps required for reaching the kth term has a minimum: q >= A*2^cN for some fixed constants A,c. (so to invert, we'd get that the # of steps N is <= (1/c) * log₂ (q/A) = O(log q).)

基本情况：

• 在K = 0：Q = 1，N = 0，Q> = 2 ^N
• K = 1：对于N = 2B-1的步骤，Q =一<子> 1 > = 2 ^B-1 = 2 ^{（N-1）/ 2} = 2 ^{N / 2} / SQRT（2）。

• k=0: q = 1, N = 0, so q >= 2^N
• k=1: for N = 2b-1 steps, q = a₁ >= 2^b-1 = 2^(N-1)/2 = 2^N/2/sqrt(2).

这意味着A = 1，C = 1/2可以提供所需的界限。在现实中，Q可以的不的双每个术语（反：[0; 1，1，1，1，1]具有披=（1 + SQRT生长因子（5））/ 2）让我们用c = 1/4。

This implies A = 1, c = 1/2 could provide desired bounds. In reality, q may not double each term (counterexample: [0; 1, 1, 1, 1, 1] has a growth factor of phi = (1+sqrt(5))/2) so let's use c = 1/4.

感应：

• 有关任期K，Q <子> K = A <子> K 问：<子> K-1 + Q <子> K-2 。再次，对于第n <子> K = 2B-1所需的该术语的步骤，一个<子> K > = 2 ^B-1 = 2 ^{（N <子> K -1）/ 2} 。

• for term k, q_k = a_kq_k-1 + q_k-2. Again, for the n_k = 2b-1 steps needed for this term, a_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} /开方（2）* 2 ^{N <子> K / 4} 。

So a_kq_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 。

Argh -- the tough part here is that if a_k = 1, q may not increase much for that one term, and we need to use q_k-2 but that may be much smaller than q_k-1.

这篇关于在＆QUOT;猜数＆QUOT;游戏中任意有理数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！