임의의 유리수에 대한 "숫자 추측"게임?

임의의 유리수에 대한 "숫자 추측"게임?

---

인터뷰 질문으로 다음과 같은 질문을 받았습니다.

나는 양의 정수 n을 생각하고 있습니다. O (lg n) 쿼리에서 추측 할 수있는 알고리즘을 생각해보세요. 각 쿼리는 귀하가 선택한 번호이며 "낮음", "높음"또는 "정답"으로 대답합니다.

이 문제는 수정 된 이진 검색으로 해결할 수 있습니다. 여기서 n을 초과하는 것을 찾을 때까지 2의 거듭 제곱을 나열한 다음 해당 범위에서 표준 이진 검색을 실행합니다. 제가 생각하기에 이것에 대해 너무나 멋지다고 생각하는 것은 당신이 단지 무차별 대입보다 빠르게 특정 숫자에 대한 무한 공간을 검색 할 수 있다는 것입니다.

하지만 제가 가진 질문은이 문제를 약간 수정 한 것입니다. 양의 정수를 선택하는 대신 0과 1 사이 의 임의의 유리수를 선택한다고 가정합니다 . 제 질문은 내가 선택한 유리수를 가장 효율적으로 결정하기 위해 어떤 알고리즘을 사용할 수 있습니까?

지금 내가 가진 최고의 솔루션은 모든 합리적 관점 에서 이진 검색 트리 인 Stern-Brocot tree 를 암묵적으로 걸 으면서 최대 O (q) 시간 내에 p / q를 찾을 수 있습니다 . 그러나 정수 케이스에 대해 얻은 런타임에 가까운 런타임을 얻고 싶었습니다. O (lg (p + q)) 또는 O (lg pq)와 같은 것일 수 있습니다. 누구든지 이런 종류의 런타임을 얻는 방법을 알고 있습니까?

처음에는 간격 [0, 1]의 표준 이진 검색을 사용하는 것을 고려했지만 거의 모든 이진법을 놓치는 반복되지 않는 이진 표현으로 유리수 만 찾습니다. 나는 또한 합리성을 열거하는 다른 방법을 사용하는 것에 대해 생각했지만 더 크거나 같거나 적은 비교를 감안할 때이 공간을 검색하는 방법을 찾을 수없는 것 같습니다.

---

좋아요, 여기에 연속 분수 만을 사용한 제 대답이 있습니다.

먼저 여기서 몇 가지 용어를 살펴 보겠습니다.

X = p / q를 알려지지 않은 분수라고합시다.

Q (X, p / q) = sign (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에 대해 다음 알고리즘을 따릅니다.

1. 초기화 Y = 0 = [0], Z = 1 = [1], k = 0.

2. 외부 루프 : 전제 조건 은 다음과 같습니다.

   • 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 짝수 인 경우 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의 인터뷰 질문과 동일합니다. 더 가까워지기 위해 2 단계 이진 검색을 수행합니다.

5. 내부 루프 1 : y _k = ∞, z _k = a, X는 Y와 Z 사이입니다.

6. Double 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 _k = floor ((a + b) / 2 인 경우 M을 계산 하고 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의 원래 인터뷰 질문과 결합 될 수 있으며 , 먼저 Q (X, 0)를 계산하여 0과 1 사이가 아닌 모든 유리수 p / q에 적용 할 수 있습니다 . 그런 다음 양 / 음의 정수에 대해 두 연속 사이의 경계를 지정합니다. 정수, 분수 부분에 위의 알고리즘을 사용합니다.

다음에 기회가 생기면이 알고리즘을 구현하는 파이썬 프로그램을 게시하겠습니다.

edit : 또한 각 단계의 연속 분수를 계산할 필요가 없다는 점에 유의하십시오 (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, 4th ed, Theorems 7.3-7.5. Wikipedia 참조 )

예 : [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]

및 샘플 출력 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은 처음부터 biginteger 수학을 처리하고이 프로그램은 정수 수학 (간격 계산 제외) 만 사용하므로 임의의 합리적으로 작동해야합니다.

---

편집 3 : 이것이 O (log ^ 2 q)가 아니라 O (log q)라는 증거의 개요 :

유리수를 찾을 때까지 각 새로운 연속 분수 항에 대한 단계 n _k 는 정확히 2b (a_k) -1입니다. 여기서 b (a_k)는 a_k = ceil (log2 (a_k)를 나타내는 데 필요한 비트 수입니다. )) : 이진 검색의 "net"을 넓히기위한 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> = 2 ^N
• 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 단계에 대해 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} .

Argh-여기서 어려운 부분은 a _k = 1이면 q가 해당 항에 대해 많이 증가하지 않을 수 있으며 q _k-2 를 사용해야 하지만 q _k-1 보다 훨씬 작을 수 있다는 것 입니다.

---

유리수를 축약 형으로 취해 분모, 분자 순으로 씁니다.

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이 될 때까지 목록을 따라갑니다. 그런 다음 그 목록을 검색하기 위해 세 번의 추측을 할 것입니다. 등등.

에서 n단계 우리는 첫 번째 다룰 당신이 찾고 있다고 효율성의 크기의 순서에 가능성을.2O(n)

업데이트 : 사람들은 이것에 대한 추론을 얻지 못했습니다. 추론은 간단합니다. 우리는 바이너리 트리를 효율적으로 걷는 방법을 알고 있습니다. 최대 분모 가있는 분수 가 있습니다 . 따라서 단계적으로 특정 분모 크기까지 검색 할 수 있습니다. 문제는 검색 할 수있는 이론적 근거가 무한하다는 것입니다. 그래서 우리는 그것들을 모두 정렬하고 주문하고 검색을 시작할 수 없습니다.O(n2)nO(2*log(n)) = O(log(n))

따라서 내 생각은 몇 개를 정렬하고, 검색하고, 더 많이 정렬하고, 검색하는 것입니다. 줄을 더 많이 올릴 때마다 지난번에했던 것보다 두 배나 늘어납니다. 그래서 우리는 지난번보다 한 번 더 추측이 필요합니다. 따라서 첫 번째 패스는 1 개의 추측을 사용하여 1 개의 가능한 합리적을 통과합니다. 두 번째는 2 개의 추측을 사용하여 3 개의 가능한 합리를 탐색합니다. 세 번째는 3 개의 추측을 사용하여 7 개의 가능한 합리를 탐색합니다. 그리고 우리 k는 k추측을 사용 하여 가능한 합리성 을 탐색 합니다. 특정 rational의 경우 결국 이진 검색을 효율적으로 수행하는 방법을 알고있는 상당히 큰 목록에 해당 rational을 넣을 것입니다.2k-1m/n

우리가 바이너리 검색을 한 경우에, 우리는 더 많은 유리수를 잡아 때 우리가 배운했던 모든 것을 무시, 우리는을 포함하여 최대 유리수를 모두 넣어 줄 m/n에 O(log(n))전달합니다. (그 시점까지 우리는를 포함하는 모든 합리성을 포함 할 수있는 충분한 합리적 결과를 얻을 수 있기 때문 m/n입니다.) 그러나 각 통과는 더 많은 추측이 필요하므로 추측이됩니다.O(log(n)2)

그러나 우리는 실제로 그보다 훨씬 더 잘합니다. 우리의 첫 번째 추측으로 우리는 목록에서 너무 크거나 작은 합리적 절반을 제거합니다. 다음 두 가지 추측은 공간을 4 분의 1로 쪼개지는 않지만 너무 멀지는 않습니다. 다음 세 번의 추측은 공간을 8 분의 1로 잘라내지는 않지만 너무 멀지 않습니다. 등등. 당신이 그것을 합치면, 나는 당신 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 개의 추측과이를 생성하는 데 약 1 초가 필요했습니다. (참고로, 합리적인 숫자를 인수로 사용하여 프로그램을 호출하면 모든 추측이 채워집니다. 이것은 매우 유용한 편의입니다.)

---

나는 그것을있어! 당신이해야 할 일은 이분법과 연속 분수 와 함께 병렬 검색을 사용하는 것 입니다.

이분법은 2의 거듭 제곱으로 표시되는 특정 실수에 대한 제한을 제공하며 연속 분수는 실수를 취하여 가장 가까운 유리수를 찾습니다.

병렬로 실행하는 방법은 다음과 같습니다.

각 단계에서, 당신은 l및 u양분의되는 하부 및 상부 경계입니다. 아이디어는 이분법 범위를 절반으로 줄이는 것과 연속 분수 표현으로 추가 항을 추가하는 것 중에서 선택할 수 있다는 것입니다. 두 때 l와는 u지속적인 분수와 같은 다음 학기를 가지고, 당신은 계속 분수 검색에서 다음 단계를 취할하고 지속적인 부분을 사용하여 쿼리를 확인합니다. 그렇지 않으면 이분법을 사용하여 범위를 절반으로 줄입니다.

두 방법 모두 분모를 적어도 상수 인자만큼 증가 시키므로 (양분 율은 2 배, 연속 분수는 최소 phi = (1 + sqrt (5)) / 2 배), 이는 검색이 O 여야 함을 의미합니다. (로그 (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에 매우 가깝습니다)을 사용하겠습니다.

[계속하려면 어딘가에 가야 해]

---

더 깊이 생각해 보면, 다음 항을 결정하는 것 외에는 이분법을 신경 쓰지 마십시오. 내가 돌아올 때 더.

---

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가 트리에 있는지 확인합니다. p / q가 트리에 없는지 확인하려면 O (log k ^ 2) = O (log k) 쿼리가 필요합니다.

우리는 2 (p + q)보다 큰 k 값을 결코 추측하지 않을 것입니다. 따라서 우리는 T = O (log (p + q))를 취할 수 있습니다.

k에 대한 정확한 값 (즉, k = p + q)을 추측하면 k에 대한 추측을 확인하는 과정에서 도전자에게 쿼리 p / q를 제출하고 게임에서 이깁니다.

총 쿼리 수는 O (log ^ 2 (p + q))입니다.

---

좋아요, 이 문제에 대한 O (lg ² q) 알고리즘을 찾았다 고 생각합니다. 이 알고리즘은 연속 분수 사용에 대한 Jason S의 가장 뛰어난 통찰력을 기반으로합니다. 런타임 분석과 함께 완전한 솔루션을 얻을 수 있도록 여기까지 알고리즘을 구체화 할 것이라고 생각했습니다.

알고리즘의 직관은 범위 내의 모든 유리수 p / q를 다음과 같이 쓸 수 있다는 것입니다.

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

_i 의 적절한 선택을 위해 . 이것을 연속 분수 라고합니다 . 더 중요한 것은 이러한 a _i 는 분자와 분모에서 유클리드 알고리즘을 실행하여 파생 될 수 있다는 것입니다. 예를 들어 11/14를 이런 식으로 표현한다고 가정합니다. 우리는 14가 11 번의 0 번에 들어간다는 것에 주목하여 시작합니다. 따라서 대략적인 11/14는 다음과 같습니다.

0 = 0

이제, 우리는 = 1 11분의 14 얻기 위해이 비율의 역수를 취한다고 가정 ³ / ₁₁ . 그래서 우리가 쓰면

0 + (1/1) = 1

우리는 11/14로 약간 더 나은 근사치를 얻습니다. 이제 우리는 11분의 3 남아 있다는 것을, 우리는 11/3 = 3 얻기 위해 다시 역수를 취할 수 ² / _3를 우리가 고려할 수 있도록,

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

11/14에 대한 또 다른 좋은 근사치입니다. 이제 2/3가 있으므로 3/2 = 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}입니다.

이 두 가지 사실을 감안할 때, 모든 계수를 복구하기 위해 한 번에 하나씩 임의의 정수 n을 추측하는 일반 알고리즘을 적용하여 0과 1 사이의 합이 아닌 모든 유리수 p / q를 복구하는 알고리즘을 만들 수 있습니다. p / q에 대한 연속 분수. 그러나 지금은 (0, 1] 범위의 숫자에 대해서만 걱정할 것입니다. 임의의 유리수를 처리하는 논리는 이것을 서브 루틴으로 쉽게 수행 할 수 있기 때문입니다.

첫 번째 단계로 1 / a ₁ 이 p / q에 최대한 가깝고 a ₁ 이 정수가 되도록 ₁ 의 최상의 값을 찾고 싶다고 가정 해 보겠습니다 . 이를 위해 매번 역수를 사용하여 임의의 정수를 추측하는 알고리즘을 실행할 수 있습니다. 이렇게하면 두 가지 중 하나가 발생합니다. 첫째, 우연의 일치로 어떤 정수 k에 대해 p / q = 1 / k라는 것을 발견 할 수 있습니다.이 경우 우리는 끝났습니다. 그렇지 않으면, 우리는 P / q는 1 / (A 사이에 끼워 찾을 수 ₁ 과 1 / A - 1) ₀ 일부 A에 대한 ₁ . 이렇게하면 p / q가 1 / (a ₁ + 1 / a ) 사이가 되는 a ₂ 를 찾아서 한 단계 더 깊은 연속 분수 작업을 시작 합니다.₂ ) 및 1 / (a ₁ + 1 / (a ₂ + 1)). 마술처럼 p / q를 찾으면 대단합니다! 그렇지 않으면, 우리는 연속 분수에서 한 단계 더 아래로 이동합니다. 결국 우리는 이런 식으로 번호를 찾을 수 있으며 너무 오래 걸리지 않습니다. 계수를 찾기위한 각 이진 검색은 최대 O (lg (p + q)) 시간이 걸리며 검색에 최대 O (lg (p + q)) 수준이 있으므로 O (lg ² (p + q)) p / q를 복구하기위한 산술 연산 및 프로브.

제가 지적하고 싶은 한 가지 세부 사항은 검색을 할 때 홀수 수준인지 짝수 수준인지 추적해야한다는 것입니다. 우리가 찾고 있던 것은 상위 또는 하위 분수였습니다. 나는에 대한 증거없이 진술거야 _난 내가 가진 이상한 당신이 두 숫자의 상단을 사용하려면, 그리고 함께 _나는 심지어는 두 숫자의 하단을 사용합니다.

이 알고리즘이 작동한다고 거의 100 % 확신합니다. 나는이 추론의 모든 틈을 메우는 좀 더 공식적인 증거를 작성하려고 노력할 것이며, 그럴 때 여기에 링크를 게시 할 것입니다.

이 솔루션이 작동하는 데 필요한 통찰력을 제공해 주신 모든 분들께 감사드립니다. 특히 연속 분수에 대한 이진 검색을 제안 해 주신 Jason S에게 감사드립니다.

---

(0, 1)의 모든 유리수는 고유 한 (양수 또는 음수) 단위 분수의 유한 한 합으로 표현 될 수 있습니다. 예를 들어 2/3 = 1/2 + 1/6 및 2/5 = 1/2-1/10입니다. 이를 사용하여 간단한 이진 검색을 수행 할 수 있습니다.

---

여기에 또 다른 방법이 있습니다. 관심이 충분하다면 오늘 밤 세부 사항을 적어 보겠습니다 만, 가족 책임이있어서 지금은 할 수 없습니다. 다음은 알고리즘을 설명해야하는 구현의 스텁입니다.

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해당 크기의 가능한 모든 부분을 통해 이진 검색에 가까운 무언가를 얻을 수 있습니다. 때때로 우리는 우리가해야 할 것보다 더 멀리 경계를 늘릴 때까지 특정 분수를 찾지 못할 것입니다. 그러나 우리는 멀리 떨어져 있지 않을 것입니다.

그래서 거기에 있습니다. 폴리 로그 작업에서 찾은 대수 질문 수입니다.

업데이트 : 그리고 완전한 작동 코드.

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

It appears slightly more efficient in guesses than the previous solution, and does a lot fewer operations. For 101/1024 it required 19 guesses and 251 operations. For .98765 it needed 27 guesses and 623 operations. For 0.0123456789 it required 66 guesses and 889 operations. And for giggles and grins, for 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (that's 10 copies of the previous one) it required 665 guesses and 23289 operations.

---

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 ;-) )

참고URL : https://stackoverflow.com/questions/5440688/the-guess-the-number-game-for-arbitrary-rational-numbers