任意有理数的"猜数"游戏？

Question

任意有理数的"猜数"游戏？

tem*_*def 75 puzzle algorithm math rational-numbers

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

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

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

不过,我的问题是对这个问题稍加修改.假设我在0和1之间选择一个任意有理数,而不是选择正整数.我的问题是:您可以使用什么算法来最有效地确定我选择的有理数？

现在,我所拥有的最佳解决方案是在最多O(q)时间内通过隐式地走Stern-Brocot树(在所有有理数上的二叉搜索树)中找到p/q .但是,我希望运行时更接近我们为整数情况得到的运行时,可能是O(lg(p + q))或O(lg pq).有没有人知道如何获得这种运行时？

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

Answer 1

Jas*_*n S 49

好的,这是我单独使用连续分数的答案.

首先让我们来看一些术语.

设X = p/q为未知分数.

设Q(X,p/q)=符号(X - p/q)为查询函数:如果为0,我们猜测了数字,如果它是+/- 1则告诉我们错误的符号.

连续分数的常规表示法是A = [a ₀ ; a ₁,a ₂,a ₃,... a _k ]

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

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

初始化Y = 0 = [0],Z = 1 = [1],k = 0.
外循环:前提条件是:
- Y和Z是k + 1项的连续分数,除最后一个元素外,它们是相同的,它们相差1,因此Y = [y ₀ ; y ₁,y ₂,y ₃,... y _k ]和Z = [y ₀ ; y ₁,y ₂,y ₃,... y _k + 1]
- (-1)^k(YX)<0 <( - 1)^k(ZX),或者更简单地说,对于k even,Y <X <Z和对于k odd,Z <X <Y.
在不改变数字值的情况下,将连续分数的程度延长1步.通常,如果最后的项是y _k和y _k + 1,我们将其改变为[... y _k,y _{k + 1} =∞]和[... y _k,z _{k + 1} = 1].现在将k增加1.
内循环:这与@ templatetypedef关于整数的面试问题基本相同.我们进行两阶段二分搜索以获得更接近:
内环1:y _k =∞,z _k = a,X在Y和Z之间.
双Z的最后一项:计算M = Z但m _k = 2*a = 2*z _k.
查询未知数:q = Q(X,M).
如果q = 0,我们得到答案并转到步骤17.
如果q和Q(X,Y)具有相反的符号,则表示X在Y和M之间,因此设置Z = M并转到步骤5.
否则设置Y = M并转到下一步:
内环2. y _k = b,z _k = a,X在Y和Z之间.
如果a和b相差1,则交换Y和Z,转到步骤2.
执行二分搜索:计算M,其中m _k = 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!

Run Code Online (Sandbox Code Playgroud)

在计算M的每个步骤中,间隔的范围减小.可能相当容易证明(尽管我不会这样做)每个步骤的间隔减少至少1/sqrt(5)的因子,这将表明该算法是O(log q)步骤.

请注意,这可以与templatetypedef的原始面试问题结合使用,并且适用于任何有理数p/q,而不仅仅是0到1之间,首先计算Q(X,0),然后是正/负整数,两个连续之间的边界整数,然后使用上述算法的小数部分.

当我有机会接下来,我会发布一个实现这个算法的python程序.

编辑:另外,请注意,您不必计算每一步的连续分数(这将是O(k),对于连续分数有部分近似值,可以计算O(1)中上一步的下一步. )

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

如果A _k = [a ₀ ; a ₁,a ₂,a ₃,... 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版,Theorems 7.3-7.5.另见维基百科)

示例:[0] = 0/1 = p ₀/q ₀,[0; 7] = 1/7 = p ₁/q ₁ ; 所以[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 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]

Run Code Online (Sandbox Code Playgroud)

和示例输出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

Run Code Online (Sandbox Code Playgroud)

由于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 ₂(q/A)= O(log q).)

基本情况:

k = 0:q = 1,N = 0,所以q> = ^2N
k = 1:对于N = 2b-1步,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]的生长因子为phi =(1 + sqrt(5))/ 2)所以让我们使用c = 1/4.

感应:

对于项k,q _k = a _k q _k-1 + q _k-2.同样,对于该项所需的n _k = 2b-1步,_k > = 2 ^b-1 = 2 ^{(n _k -1)/ 2}.

所以_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}.

唉 - 这里最难的部分是,如果_k = 1,q对于那个项可能不会增加太多,我们需要使用q _k-2,但这可能比q _k-1小得多.

Answer 2

bti*_*lly 6

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

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

Run Code Online (Sandbox Code Playgroud)

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

在n步骤中,我们将涵盖第一种可能性,这是您正在寻找的效率的数量级.2^O(n)

更新:人们没有得到这背后的推理.推理很简单.我们知道如何有效地遍历二叉树.有分数具有最大分母.因此,我们可以逐步搜索任何特定的分母大小.问题是我们有无数可能的搜索理由.因此,我们不能只将它们排成一行,订购它们,然后开始搜索.O(n²)nO(2*log(n)) = O(log(n))

因此,我的想法是排队,搜索,排队,搜索等等.每次我们排队时,我们排队的比例是我们上次的两倍.所以我们需要比上次更多猜测.因此,我们的第一遍使用1猜测来遍历1个可能的理性.我们的第二个使用2个猜测来遍历3个可能的有理数.我们的第三个使用3个猜测来遍历7个可能的理性.我们k用k猜测来追溯可能的理性.对于任何特定的理性,最终它会最终将该理性放在一个相当大的列表上,它知道如何有效地进行二进制搜索.2^k-1m/n

如果我们进行二元搜索,那么当我们获得更多的理性时,忽略了我们学到的所有内容,然后我们将所有的有理数放在并包含m/n在O(log(n))传递中.(那是因为到那时我们将通过足够的理性来包括所有理性,包括m/n.)但每次传球需要更多的猜测,所以这将是猜测.O(log(n)²)

然而,我们实际上做得比这更好.通过我们的第一次猜测,我们将列表中的一半理性消除为太大或太小.我们接下来的两个猜测并没有将空间缩小到几分之一,但它们并没有太远.我们接下来的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] = []

Run Code Online (Sandbox Code Playgroud)

作为尝试它的一个例子,我尝试了101/1024(0.0986328125),发现需要20个猜测才能找到答案.我尝试了0.98765并进行了45次猜测.我尝试了0.0123456789,它需要66次猜测,大约需要一秒钟来生成它们.(注意,如果你用一个有理数字作为参数调用程序,它将为你填写所有的猜测.这是一个非常有帮助的方便.)

@btilly:7-3,15-4,(31-5？)在哪里进来？有这样一个"猜测下一个"数字队列背后的逻辑是什么？ (3认同)
@Btilly:+1,但看起来你还没有真正解决_main_问题.你生成Theta(q)有理数并对它们进行二元搜索.所以运行时是Omega(q),即使您采用O(log ^ 2 q)查询.实际上,Seth有一个非常相似的算法(如果你仔细阅读,他不是_querying_ for p + q).IMO,这里要解决的主要问题是生成O(polylog(q))有理数,而不是试图保持查询数量O(polylog(q)),而不考虑其他的簿记开销. (2认同)

归档时间：	14 年，10 月前
查看次数：	7657 次
最近记录：	10 年，6 月前