Pertanyaan Game "tebak angka" untuk angka rasional sewenang-wenang?


Saya pernah mendapat yang berikut sebagai pertanyaan wawancara:

Saya sedang berpikir tentang bilangan bulat positif n. Muncul dengan algoritma yang dapat menebaknya dalam O (lg n) queries. Setiap kueri adalah sejumlah pilihan Anda, dan saya akan menjawab "lebih rendah," "lebih tinggi," atau "benar."

Masalah ini dapat diselesaikan dengan pencarian biner yang dimodifikasi, di mana Anda mendaftarkan kekuatan dua sampai Anda menemukan satu yang melebihi n, kemudian jalankan pencarian biner standar di atas rentang itu. Apa yang saya pikir sangat keren tentang ini adalah bahwa Anda dapat mencari ruang tak terbatas untuk nomor tertentu lebih cepat daripada hanya kekuatan brute.

Pertanyaan yang saya miliki, adalah sedikit modifikasi dari masalah ini. Alih-alih memilih bilangan bulat positif, misalkan saya memilih nomor rasional sewenang-wenang antara nol dan satu. Pertanyaan saya adalah: algoritma apa yang dapat Anda gunakan untuk menentukan secara efisien bilangan rasional mana yang saya pilih?

Saat ini, solusi terbaik yang saya miliki dapat menemukan p / q dalam paling banyak waktu O (q) dengan berjalan secara implisit Pohon Stern-Brocot, pohon pencarian biner di atas semua rationals. Namun, saya berharap untuk mendapatkan runtime lebih dekat ke runtime yang kami dapatkan untuk kasus integer, mungkin sesuatu seperti O (lg (p + q)) atau O (lg pq). Apakah ada yang tahu cara untuk mendapatkan runtime semacam ini?

Awalnya saya mempertimbangkan untuk menggunakan pencarian biner standar dari interval [0, 1], tetapi ini hanya akan menemukan bilangan rasional dengan representasi biner yang tidak berulang, yang merindukan hampir semua rasionalnya. Saya juga berpikir untuk menggunakan cara lain untuk menghitung rationals, tetapi saya tidak dapat menemukan cara untuk mencari ruang yang diberikan hanya perbandingan yang lebih besar / sama / kurang.


75
2018-03-26 06:19


asal


Jawaban:


Oke, inilah jawaban saya menggunakan fraksi lanjutan sendirian.

Pertama mari kita dapatkan beberapa terminologi di sini.

Biarkan X = p / q menjadi fraksi yang tidak diketahui.

Biarkan Q (X, p / q) = tanda (X - p / q) menjadi fungsi query: jika 0, kita sudah menebak nomornya, dan jika itu +/- 1 yang memberitahu kita tanda kesalahan kita .

Itu notasi konvensional untuk fraksi lanjutan adalah A = [a0; Sebuah1, Sebuah2, Sebuah3, ... Sebuahk]

= a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / (... + 1 / ak) ...)))


Kami akan mengikuti algoritma berikut untuk 0 <p / q <1.

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

  2. Lingkar luar: The prakondisi apakah itu:

    • Y dan Z adalah fraksi lanjutan dari k + 1 istilah yang identik kecuali dalam elemen terakhir, di mana mereka berbeda dengan 1, sehingga Y = [y0; y1, y2, y3, ... yk] dan Z = [y0; y1, y2, y3, ... yk + 1]

    • (-1)k(Y-X) <0 <(-1)k(Z-X), atau dalam istilah yang lebih sederhana, untuk k even, Y <X <Z dan untuk k aneh, Z <X <Y.

  3. Memperpanjang derajat fraksi lanjutan dengan 1 langkah tanpa mengubah nilai angka. Secara umum, jika istilah terakhir adalah yk dan yk+ 1, kami mengubahnya menjadi [... yk, yk + 1= ∞] dan [... yk, zk + 1= 1]. Sekarang tingkatkan k 1.

  4. Loop batin: Ini pada dasarnya sama dengan pertanyaan wawancara @ templatetypedef tentang bilangan bulat. Kami melakukan pencarian biner dua fase untuk lebih dekat:

  5. Lingkaran dalam 1: yk = ∞, zk  = a, dan X adalah antara Y dan Z.

  6. Istilah terakhir Z Double: Hitung M = Z tetapi dengan mk = 2 * a = 2 * zk.

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

  8. Jika q = 0, kami memiliki jawaban kami dan lanjut ke langkah 17.

  9. Jika q dan Q (X, Y) memiliki tanda yang berlawanan, itu berarti X adalah antara Y dan M, jadi atur Z = M dan lanjutkan ke langkah 5.

  10. Jika tidak, tetapkan Y = M dan lanjutkan ke langkah berikutnya:

  11. Lingkaran dalam 2. yk = b, zk  = a, dan X adalah antara Y dan Z.

  12. Jika a dan b berbeda dengan 1, tukarkan Y dan Z, lanjutkan ke langkah 2.

  13. Lakukan pencarian biner: hitung M di mana mk = floor ((a + b) / 2, dan query q = Q (X, M).

  14. Jika q = 0, kita sudah selesai dan lanjut ke langkah 17.

  15. Jika q dan Q (X, Y) memiliki tanda yang berlawanan, itu berarti X adalah antara Y dan M, jadi atur Z = M dan lanjutkan ke langkah 11.

  16. Jika tidak, q dan Q (X, Z) memiliki tanda yang berlawanan, itu berarti X adalah antara Z dan M, jadi tetapkan Y = M dan lanjutkan ke langkah 11.

  17. Selesai: X = M.

Contoh konkret untuk 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!

Pada setiap langkah komputasi M, rentang interval berkurang. Ini mungkin cukup mudah untuk dibuktikan (meskipun saya tidak akan melakukan ini) bahwa interval dikurangi dengan faktor setidaknya 1 / sqrt (5) pada setiap langkah, yang akan menunjukkan bahwa algoritma ini adalah langkah-langkah O (log q).

Perhatikan bahwa ini dapat dikombinasikan dengan pertanyaan wawancara asli templatetypedef dan berlaku apa saja bilangan rasional p / q, bukan hanya antara 0 dan 1, dengan komputasi pertama Q (X, 0), kemudian untuk bilangan bulat positif / negatif, melompat-lompat antara dua bilangan bulat berturut-turut, dan kemudian menggunakan algoritma di atas untuk bagian pecahan.

Ketika saya memiliki kesempatan berikutnya, saya akan memposting program python yang mengimplementasikan algoritma ini.

sunting: juga, perhatikan bahwa Anda tidak perlu menghitung fraksi lanjutan setiap langkah (yang akan menjadi O (k), ada sebagian perkiraan untuk pecahan lanjutan yang dapat menghitung langkah berikutnya dari langkah sebelumnya dalam O (1).)

sunting 2: Definisi rekursif dari perkiraan parsial:

Jika sebuahk = [a0; Sebuah1, Sebuah2, Sebuah3, ... Sebuahk] = pk/ qk, lalu pk = akpk-1 + pk-2, dan qk = akqk-1 + qk-2. (Sumber: Niven & Zuckerman, 4th ed, Theorems 7.3-7.5. Lihat juga Wikipedia)

Contoh: [0] = 0/1 = p0/ q0, [0; 7] = 1/7 = p1/ q1; jadi [0; 7, 16] = (16 * 1 + 0) / (16 * 7 + 1) = 16/113 = p2/ q2.

Ini berarti bahwa jika dua fraksi lanjutan Y dan Z memiliki ketentuan yang sama kecuali yang terakhir, dan fraksi lanjutan tidak termasuk term terakhir adalah pk-1/ qk-1, maka kita dapat menulis Y = (ykpk-1 + pk-2) / (ykqk-1 + qk-2) dan Z = (zkpk-1 + pk-2) / (zkqk-1 + qk-2). Seharusnya mungkin untuk menunjukkan dari ini bahwa | Y-Z | menurun setidaknya satu faktor 1 / sqrt (5) pada setiap interval yang lebih kecil yang dihasilkan oleh algoritma ini, tetapi aljabar tampaknya berada di luar saya saat ini. :-(

Inilah program Python saya:

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]

dan contoh keluaran untuk 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

Sejak Python menangani matematika biginteger dari awal, dan program ini hanya menggunakan matematika integer (kecuali untuk perhitungan interval), itu harus bekerja untuk rationsals sewenang-wenang.


sunting 3: Garis besar bukti bahwa ini adalah O (log q), bukan O (log ^ 2 q):

Pertama perhatikan bahwa sampai bilangan rasional ditemukan, nomor langkah nk untuk setiap fraksi lanjutan baru adalah persis 2b (a_k) -1 di mana b (a_k) adalah # bit yang diperlukan untuk mewakili a_k = ceil (log2 (a_k)): itu b (a_k) langkah-langkah untuk memperluas "net" dari pencarian biner, dan b (a_k ) -1 langkah untuk mempersempitnya). Lihat contoh di atas, Anda akan perhatikan bahwa # langkahnya selalu 1, 3, 7, 15, dll.

Sekarang kita bisa menggunakan relasi pengulangan qk = akqk-1 + qk-2 dan induksi untuk membuktikan hasil yang diinginkan.

Mari menyatakannya dengan cara ini: bahwa nilai q setelah Nk = jumlah (nk) langkah-langkah yang diperlukan untuk mencapai kth term memiliki minimum: q> = A * 2cn untuk beberapa konstanta tetap A, c. (jadi untuk membalikkan, kita akan mendapatkan bahwa # langkah N adalah <= (1 / c) * log2 (q / A) = O (log q).)

Casing dasar:

  • k = 0: q = 1, N = 0, jadi q> = 2N
  • k = 1: untuk N = 2b-1 langkah, q = a1 > = 2b-1 = 2(N-1) / 2 = 2N / 2/ sqrt (2).

Ini berarti A = 1, c = 1/2 dapat memberikan batas yang diinginkan. Kenyataannya, q mungkin tidak gandakan setiap istilah (counterexample: [0; 1, 1, 1, 1, 1] memiliki faktor pertumbuhan phi = (1 + sqrt (5)) / 2) jadi mari kita gunakan c = 1/4.

Induksi:

  • untuk istilah k, qk = akqk-1 + qk-2. Sekali lagi, untuk nk = 2b-1 langkah diperlukan untuk istilah ini, ak > = 2b-1 = 2(nk-1) / 2.

    Jadi akqk-1 > = 2(Nk-1) / 2 * qk-1 > = 2(nk-1) / 2 * A * 2Nk-1/ 4 = A * 2Nk/ 4/ sqrt (2) * 2nk/ 4.

Argh - bagian yang sulit di sini adalah bahwa jika ak = 1, q tidak boleh bertambah banyak untuk satu istilah itu, dan kita perlu menggunakan qk-2 tapi itu mungkin jauh lebih kecil dari qk-1.


49
2018-03-26 22:56



Mari kita ambil bilangan-bilangan rasional, dalam bentuk yang dikurangi, dan tuliskan mereka dalam urutan pertama penyebut, lalu pembilang.

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

Tebakan pertama kita akan menjadi 1/2. Kemudian kita akan masuk daftar sampai kita memiliki 3 dalam jangkauan kita. Kemudian kita akan mengambil 2 tebakan untuk mencari daftar itu. Kemudian kita akan masuk daftar sampai kita memiliki 7 dalam rentang yang tersisa. Kemudian kami akan mengambil 3 tebakan untuk mencari daftar itu. Dan seterusnya.

Di n langkah-langkah yang akan kami bahas pertama 2Di) kemungkinan, yang berada di urutan besarnya efisiensi yang Anda cari.

Memperbarui: Orang-orang tidak mendapatkan alasan di balik ini. Alasannya sederhana. Kami tahu cara berjalan pohon biner secara efisien. Ada O(n2) fraksi dengan denominator maksimum n. Oleh karena itu, kami dapat mencari ukuran penyebut tertentu O(2*log(n)) = O(log(n)) tangga. Masalahnya adalah bahwa kita memiliki jumlah rasion yang tidak terbatas untuk dicari. Jadi kita tidak bisa membariskan semuanya, memesannya, dan mulai mencari.

Oleh karena itu ide saya adalah untuk berbaris beberapa, mencari, berbaris lebih banyak, mencari, dan seterusnya. Setiap kali kita berbaris lebih banyak kita berbaris sekitar dua kali lipat dari apa yang kita lakukan terakhir kali. Jadi kita butuh satu tebakan lebih banyak daripada yang kita lakukan terakhir kali. Oleh karena itu, umpan pertama kami menggunakan 1 tebakan untuk melintasi 1 kemungkinan rasional. Kedua kami menggunakan 2 tebakan untuk melintasi 3 rational yang mungkin. Ketiga kami menggunakan 3 tebakan untuk melintasi 7 rational yang mungkin. Dan kita k'Th menggunakan k tebak untuk melintasi 2k-1 rationalals mungkin. Untuk rasional tertentu m/n, akhirnya itu akan berakhir menempatkan rasional pada daftar yang cukup besar yang ia tahu bagaimana melakukan pencarian biner secara efisien.

Jika kami melakukan pencarian biner, maka mengabaikan semua yang kami pelajari ketika kami mengambil lebih banyak rational, kemudian kami akan memasukkan semua rujukan ke dan termasuk m/n di O(log(n)) berlalu. (Itu karena pada titik itu kita akan mendapatkan umpan dengan cukup banyak rationals untuk memasukkan setiap rasional hingga dan termasuk m/n.) Tapi setiap pass membutuhkan lebih banyak tebakan, jadi itu akan menjadi O(log(n)2) tebakan.

Namun kami sebenarnya jauh lebih baik dari itu. Dengan tebakan pertama kami, kami mengeliminasi setengah rasionya di daftar kami sebagai terlalu besar atau kecil. Dua tebakan kami berikutnya tidak cukup memotong ruang menjadi empat, tetapi mereka tidak datang terlalu jauh dari itu. Tebakan kami berikutnya 3 tidak cukup memotong ruang menjadi delapan, tetapi mereka tidak datang terlalu jauh dari itu. Dan seterusnya. Ketika Anda menyatukannya, saya yakin bahwa hasilnya adalah yang Anda temukan m/n di O(log(n)) tangga. Meskipun saya sebenarnya tidak punya bukti.

Cobalah: Di sini adalah kode untuk menghasilkan tebakan sehingga Anda dapat bermain dan melihat seberapa efisiennya.

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

Sebagai contoh untuk mencobanya, saya mencoba 101/1024 (0.0986328125) dan menemukan bahwa butuh 20 tebakan untuk menemukan jawabannya. Saya mencoba 0,98765 dan butuh 45 tebakan. Saya mencoba 0,0123456789 dan dibutuhkan 66 tebakan dan sekitar satu detik untuk menghasilkan mereka. (Perhatikan, jika Anda memanggil program dengan bilangan rasional sebagai argumen, itu akan mengisi semua tebakan untuk Anda. Ini adalah kenyamanan yang sangat membantu.)


6
2018-03-26 07:40



Aku memahaminya! Yang perlu Anda lakukan adalah menggunakan pencarian paralel dengan pembelahan dan fraksi lanjutan.

Biseksi akan memberi Anda batas menuju bilangan real spesifik, yang direpresentasikan sebagai kekuatan dua, dan fraksi lanjutan akan mengambil bilangan real dan menemukan bilangan rasional terdekat.

Cara Anda menjalankannya secara paralel adalah sebagai berikut.

Di setiap langkah, Anda punya l dan u menjadi batas bawah dan atas dari pembelahan. Idenya adalah, Anda memiliki pilihan antara mengurangi separuh rentang pembelahan, dan menambahkan istilah tambahan sebagai representasi fraksi lanjutan. Kapan keduanya l dan u memiliki istilah berikutnya yang sama sebagai fraksi lanjutan, kemudian Anda mengambil langkah berikutnya dalam pencarian fraksi lanjutan, dan membuat kueri menggunakan fraksi lanjutan. Jika tidak, Anda membagi dua rentang menggunakan pembelahan.

Karena kedua metode meningkatkan penyebut dengan setidaknya faktor konstan (pembelahan berjalan dengan faktor 2, fraksi lanjutan berlalu paling tidak satu faktor phi = (1 + sqrt (5)) / 2), ini berarti pencarian Anda harus O (log (q)). (Mungkin ada perhitungan fraksi lanjutan yang berulang, sehingga mungkin berakhir sebagai O (log (q) ^ 2).)

Pencarian fraksi lanjutan kami perlu membulatkan ke bilangan bulat terdekat, tidak menggunakan lantai (ini lebih jelas di bawah).

Di atas adalah semacam handwavy. Mari kita gunakan contoh konkret dari r = 1/31:

  1. l = 0, u = 1, query = 1/2. 0 tidak dapat diekspresikan sebagai fraksi lanjutan, jadi kami menggunakan pencarian biner sampai l! = 0.

  2. l = 0, u = 1/2, query = 1/4.

  3. l = 0, u = 1/4, query = 1/8.

  4. l = 0, u = 1/8, query = 1/16.

  5. l = 0, u = 1/16, query = 1/32.

  6. l = 1/32, u = 1/16. Sekarang 1 / l = 32, 1 / u = 16, ini memiliki reparasi cfrac yang berbeda, jadi tetap membagi dua., Query = 3/64.

  7. l = 1/32, u = 3/64, query = 5/128 = 1 / 25.6

  8. l = 1/32, u = 5/128, query = 9/256 = 1 / 28.4444 ....

  9. l = 1/32, u = 9/256, permintaan = 17/512 = 1 / 30.1176 ... (putaran ke 1/30)

  10. l = 1/32, u = 17/512, pertanyaan = 33/1024 = 1 / 31.0303 ... (putaran ke 1/31)

  11. l = 33/1024, u = 17/512, pertanyaan = 67/2048 = 1 / 30,5672 ... (putaran ke 1/31)

  12. l = 33/1024, u = 67/2048. Pada titik ini baik l dan u memiliki fraksi lanjutan yang sama 31, jadi sekarang kita menggunakan tebakan fraksi lanjutan.   query = 1/31.

KEBERHASILAN!

Untuk contoh lain, gunakan 16/113 (= 355/113 - 3 di mana 355/113 cukup dekat dengan pi).

[untuk dilanjutkan, saya harus pergi ke suatu tempat]


Pada refleksi lebih lanjut, fraksi lanjutan adalah cara untuk pergi, jangankan perpisahan kecuali untuk menentukan istilah berikutnya. Lebih banyak ketika saya kembali.


4
2018-03-26 14:11



Saya rasa saya menemukan algoritma O (log ^ 2 (p + q)).

Untuk menghindari kebingungan dalam paragraf berikutnya, sebuah "query" mengacu pada saat tebakan memberi penantang tebakan, dan penantang merespon "lebih besar" atau "lebih kecil". Ini memungkinkan saya untuk menyimpan kata "tebakan" untuk sesuatu yang lain, tebakan untuk p + q yang tidak ditanyakan langsung kepada penantang.

Idenya adalah untuk pertama menemukan p + q, menggunakan algoritma yang Anda gambarkan dalam pertanyaan Anda: tebak nilai k, jika k terlalu kecil, gandakan dan coba lagi. Kemudian setelah Anda memiliki batas atas dan bawah, lakukan pencarian biner standar. Ini mengambil O (log (p + q) T) queri, di mana T adalah batas atas untuk jumlah kueri yang diperlukan untuk memeriksa tebakan. Mari kita temukan T.

Kami ingin memeriksa semua fraksi r / s dengan r + s <= k, dan double k hingga k cukup besar. Perhatikan bahwa ada fraksi O (k ^ 2) yang Anda perlukan untuk memeriksa nilai k tertentu. Buat pohon pencarian biner yang seimbang yang berisi semua nilai ini, kemudian cari untuk menentukan apakah p / q ada di pohon. Dibutuhkan O (log k ^ 2) = O (log k) queri untuk mengkonfirmasi bahwa p / q tidak ada di pohon.

Kami tidak akan pernah menebak nilai k lebih besar dari 2 (p + q). Oleh karena itu kita dapat mengambil T = O (log (p + q)).

Saat kami menebak nilai yang benar untuk k (yaitu, k = p + q), kami akan mengirimkan kueri p / q ke penantang selama memeriksa tebakan kami untuk k, dan memenangkan permainan.

Jumlah total queri kemudian O (log ^ 2 (p + q)).


3
2018-03-26 08:15



Oke, saya pikir saya menemukan O (lg2 q) algoritma untuk masalah ini yang didasarkan pada wawasan paling baik Jason S tentang penggunaan fraksi lanjutan. Saya pikir saya akan menyempurnakan algoritmanya sampai tuntas di sini sehingga kami memiliki solusi lengkap, bersama dengan analisis runtime.

Intuisi di balik algoritme adalah bahwa setiap bilangan rasional p / q dalam rentang dapat ditulis sebagai

Sebuah0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / ...))

Untuk pilihan yang tepat dari suatusaya. Ini disebut a fraksi lanjutan. Lebih penting lagi, meskipun ini asaya dapat diturunkan dengan menjalankan algoritma Euclidean pada pembilang dan penyebut. Misalnya, anggap kita ingin mewakili 11/14 dengan cara ini. Kami mulai dengan mencatat bahwa 14 masuk ke sebelas nol kali, sehingga perkiraan kasar 11/14 akan

0 = 0

Sekarang, anggaplah kita mengambil timbal balik dari fraksi ini untuk mendapatkan 14/11 = 1 3/11. Jadi kalau kita menulis

0 + (1/1) = 1

Kami mendapatkan pendekatan yang sedikit lebih baik ke 11/14. Sekarang kita tinggal dengan 3/11, kita dapat mengambil timbal balik lagi untuk mendapatkan 11/3 = 3 2/3, jadi kita bisa mempertimbangkan

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

Yang merupakan perkiraan bagus untuk 11/14. Sekarang, kita memiliki 2/3, jadi pertimbangkan timbal balik, yaitu 3/2 = 1 1/2. Jika kita menulis

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

Kami mendapatkan perkiraan yang bagus untuk 11/14. Akhirnya, kita pergi dengan 1/2, yang timbal baliknya adalah 2/1. Jika akhirnya kita menulis

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

itulah fraksi yang kami inginkan. Terlebih lagi, lihat urutan koefisien yang akhirnya kita gunakan. Jika Anda menjalankan algoritma Euclidean diperpanjang pada 11 dan 14, Anda mendapatkan itu

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

Ternyata (menggunakan lebih banyak matematika daripada yang saya ketahui sekarang bagaimana melakukannya!) Bahwa ini bukanlah suatu kebetulan dan bahwa koefisien dalam fraksi lanjutan dari p / q selalu dibentuk dengan menggunakan algoritma Euclidean yang diperluas. Ini luar biasa, karena ia memberi tahu kita dua hal:

  1. Paling banyak terdapat koefisien O (lg (p + q)), karena algoritma Euclidean selalu berakhir dalam banyak langkah ini, dan
  2. Setiap koefisien paling banyak maksimal {p, q}.

Dengan adanya dua fakta ini, kita dapat membuat suatu algoritma untuk memulihkan setiap bilangan rasional p / q, bukan hanya antara 0 dan 1, dengan menerapkan algoritma umum untuk menebak bilangan bulat acak n satu per satu untuk memulihkan semua koefisien dalam fraksi lanjutan untuk p / q. Untuk saat ini, meskipun, kita hanya akan khawatir tentang angka dalam rentang (0, 1), karena logika untuk menangani nomor rasional sewenang-wenang dapat dilakukan dengan mudah diberikan ini sebagai subrutin.

Sebagai langkah pertama, anggaplah kita ingin menemukan nilai terbaik dari1 jadi 1 / a1 sedekat mungkin dengan p / q dan a1 adalah bilangan bulat. Untuk melakukan ini, kita bisa menjalankan algoritma kita untuk menebak bilangan bulat acak, mengambil timbal balik setiap kali. Setelah melakukan ini, satu dari dua hal akan terjadi. Pertama, kita mungkin dengan kebetulan belaka menemukan bahwa p / q = 1 / k untuk beberapa integer k, dalam hal ini kita sudah selesai. Jika tidak, kita akan menemukan bahwa p / q terjepit di antara 1 / (a1- 1) dan 1 / a0 untuk beberapa a1. Ketika kita melakukan ini, maka kita mulai mengerjakan fraksi lanjutan satu tingkat lebih dalam dengan mencari a2 sedemikian rupa sehingga p / q adalah antara 1 / (a1 + 1 / a2) dan 1 / (a1 + 1 / (a2 + 1)). Jika kita secara ajaib menemukan p / q, itu hebat! Jika tidak, kita kemudian naik satu tingkat lebih rendah di fraksi lanjutan. Pada akhirnya, kita akan menemukan nomornya dengan cara ini, dan itu tidak boleh terlalu lama. Setiap pencarian biner untuk menemukan koefisien membutuhkan paling banyak waktu O (lg (p + q)), dan ada paling banyak O (lg (p + q)) ke pencarian, jadi kita hanya perlu O (lg2(p + q)) operasi aritmatika dan probe untuk memulihkan p / q.

Satu detail yang ingin saya tunjukkan adalah bahwa kita perlu melacak apakah kita berada pada level ganjil atau bahkan level ketika melakukan pencarian karena ketika kita mengaplikasikan p / q antara dua fraksi lanjutan, kita perlu mengetahui apakah koefisien yang kami cari adalah fraksi atas atau bawah. Saya akan menyatakan tanpa bukti bahwa untuk asaya dengan saya aneh Anda ingin menggunakan bagian atas dari dua angka, dan dengansaya bahkan Anda menggunakan yang lebih rendah dari dua angka.

Saya hampir 100% yakin bahwa algoritme ini berfungsi. Saya akan mencoba untuk menulis bukti yang lebih formal tentang ini di mana saya mengisi semua celah dalam alasan ini, dan ketika saya melakukannya saya akan memposting tautan di sini.

Terima kasih kepada semua orang untuk berkontribusi wawasan yang diperlukan untuk mendapatkan solusi ini bekerja, terutama Jason S untuk menyarankan pencarian biner selama fraksi lanjutan.


3
2018-03-26 22:51



Ingat bahwa bilangan rasional apa pun dalam (0, 1) dapat direpresentasikan sebagai jumlah fraksi unit yang jelas (positif atau negatif). Misalnya, 2/3 = 1/2 + 1/6 dan 2/5 = 1/2 - 1/10. Anda dapat menggunakan ini untuk melakukan pencarian biner langsung ke depan.


2
2018-03-26 12:45



Inilah cara lain untuk melakukannya. Jika ada minat yang cukup, saya akan mencoba untuk mengisi detail malam ini, tetapi saya tidak bisa sekarang karena saya memiliki tanggung jawab keluarga. Berikut ini adalah rintisan implementasi yang harus menjelaskan algoritme:

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)

Dan inilah penjelasannya. Apa best_continued_fraction(x, bound) harus lakukan adalah menemukan pendekatan fraksi lanjutan terakhir untuk x dengan penyebut paling banyak bound. Algoritma ini akan mengambil langkah-langkah polylog untuk menyelesaikan dan menemukan pendekatan yang sangat baik (meskipun tidak selalu yang terbaik). Jadi untuk masing-masing bound kita akan mendapatkan sesuatu yang dekat dengan pencarian biner melalui semua kemungkinan pecahan dari ukuran itu. Kadang-kadang kita tidak akan menemukan fraksi tertentu sampai kita meningkatkan batas lebih jauh dari yang seharusnya, tetapi kita tidak akan jauh.

Jadi begitulah. Sejumlah pertanyaan logaritmik yang ditemukan dengan pekerjaan polylog.

Memperbarui: Dan kode kerja penuh.

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

Tampaknya sedikit lebih efisien dalam tebakan daripada solusi sebelumnya, dan melakukan banyak operasi lebih sedikit. Untuk 101/1024 dibutuhkan 19 tebakan dan 251 operasi. Untuk .98765 dibutuhkan 27 tebakan dan 623 operasi. Untuk 0,0123456789 diperlukan 66 tebakan dan 889 operasi. Dan untuk cekikikan dan nyengir, untuk 0,0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (itu 10 salinan dari yang sebelumnya) diperlukan 665 tebakan dan 23289 operasi.


2
2018-03-26 21:02



Anda dapat mengurutkan angka-angka rasional dalam interval tertentu oleh misalnya pasangan (penyebut, pembilang). Kemudian mainkan game yang Anda bisa

  1. Temukan jeda [0, N] menggunakan pendekatan penggandaan-langkah
  2. Diberikan interval [a, b] menembak untuk rasional dengan denominator terkecil dalam interval yang paling dekat ke pusat interval

Namun ini mungkin masih O(log(num/den) + den) (tidak yakin dan terlalu dini di pagi hari untuk membuat saya berpikir jernih ;-))


0
2018-03-26 07:37