Temukan posisi pecahan di pohon Stern-Brocot

11

Pohon Stern-Brocot adalah pohon biner fraksi di mana setiap fraksi diperoleh dengan menambahkan pembilang dan penyebut dari dua fraksi yang berdekatan di tingkat di atas.

Ini dihasilkan dengan memulai dengan 0/1dan 1/0sebagai "fraksi titik akhir", dan dari sana, iterasi dengan menempatkan satu fraksi antara setiap pasangan fraksi berturut-turut dengan menambahkan pembilang dan penyebut dari fraksi tersebut bersama-sama, seperti:

0.  0/1                                                             1/0
1.  0/1                             1/1                             1/0
2.  0/1             1/2             1/1             2/1             1/0
3.  0/1     1/3     1/2     2/3     1/1     3/2     2/1     3/1     1/0
4.  0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0

Dalam setiap iterasi dari pohon Stern-Brocot (yang niterasi th), ada 2^n + 1unsur-unsur dalam urutan, yang kita dapat menganggap fraksi dari 0/2^nke 2^n/2^n. Setiap iterasi baru hanya menyisipkan satu fraksi "setengah" antara setiap pasangan fraksi berturut-turut.

Ini membuat pohon Stern-Brocot pemetaan satu-ke-satu antara bilangan rasional positif dan pecahan biner antara 0 dan 1, dengan demikian juga berfungsi sebagai bukti bahwa kedua himpunan memiliki kardinalitas yang sama.

Tugas Anda adalah menulis sebuah program atau fungsi yang, mengingat pembilang dan penyebut bilangan rasional positif dalam istilah terendah, menentukan fraksi biner yang sesuai dengan posisi fraksi itu di pohon Stern-Brocot.

Contoh input dan output disediakan di bawah ini:

2/3 -> 3/8   (4th number in iteration 3)
4/7 -> 9/32  (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2   (middle number in the first iteration)

Input yang tidak perlu Anda dukung, tetapi disertakan untuk referensi:

0/1 -> 0/1   (0/1 is considered the left number)
1/0 -> 1/1   (1/0 is considered the rightmost number)

Program terpendek dalam bahasa apa pun untuk mencapai tujuan ini menang.

Joe Z.
sumber
Apakah ada persyaratan input / output? mis. Apakah hanya fungsi yang memadai seperti dalam solusi referensi Anda, atau apakah itu perlu program yang berdiri sendiri? Apakah format output fraksi penting?
Darren Stone
Suatu fungsi sudah cukup. Saya akan membuatnya lebih jelas dalam deskripsi masalah.
Joe Z.
Agak terlambat bagi saya untuk memikirkannya; Saya mungkin akan mencoba menjelaskannya besok.
Joe Z.
2
Ok, saya pikir bijih yang ada dalam pikiran Anda adalah untuk menetapkan untuk setiap kedalaman di pohon penyebut konstan 2 ^ (kedalaman + 1) dan pembilang 1, 3, 5, 7, ... dari kiri.
Peter Taylor
1
Cara alternatif untuk membangun itu adalah untuk angka pertama node dari pohon di luasnya-urutan pertama mulai pada 1 (yaitu 1/1 => 1, 1/2 => 2, 2/1 => 3, 1/3 => 4, dll). Jika angka yang dihasilkan untuk suatu simpul adalah n, maka 2^lg n(log biner) adalah bit tertinggi yang diatur n, dan fraksi biner yang diinginkan adalah (2*(n - 2^lg n) + 1) / 2^(lg n + 1). (Siapa pun yang mencoba solusi assembler dalam set instruksi dengan get-set-set-bit tertinggi mungkin ingin menggunakan pendekatan ini).
Peter Taylor

Jawaban:

1

GolfScript ( 49 48 46 karakter)

{0\@{}{@2*2$2$>!+@@{{\}3$)*}:j~1$-j}/\)\,?}:f;

atau

{0:x;\{}{.2$<!2x*+:x){\}*1$-{\}x)*}/x@)@,?}:g;

Keduanya adalah fungsi yang mengambil pembilang dan penyebut di tumpukan dan meninggalkan pembilang dan penyebut di tumpukan. Demo online .

Gagasan inti dinyatakan dalam pseudocode dalam bagian Matematika Beton bagian 4,5 (hal122 dalam edisi saya):

while m != n do
    if m < n then (output(L); n := n - m)
             else (output(R); m := m - n)

Jika string Ls dan Rs ditafsirkan sebagai nilai biner dengan L = 0 dan R = 1 maka dua kali nilai ditambah satu adalah pembilang, dan penyebutnya sedikit lebih lama.

Sebagai hal yang menarik bagi penulis naskah Golf, ini adalah salah satu kesempatan langka ketika saya merasa berguna. (Ok, saya hanya menggunakannya sebagai penghitung lingkaran, tapi itu lebih baik daripada tidak sama sekali).

Peter Taylor
sumber
1

Mathematica, 130 114 111 karakter

f=#~g~0&;0~g~q_=q;p_~g~q_:=g[#,(Sign[p-#]+q)/2]&@FromContinuedFraction[ContinuedFraction@p/.{x___,n_}:>{x,n-1}]

Contoh:

f[2/3]

3/8

f[4/7]

9/32

f[1]

1/2

alephalpha
sumber
1

Ruby, 132 125

Rubied & golf solusi referensi dari @ Joz.

def t(n,d)u=k=0;v,j,f,g,b=[1,]*5;c=2
while(z=(f*d).<=>(g*n))!=0;z>0?(j,k=f,g):(u,v=f,g);b=b*2-z;f,g=u+j,v+k;c*=2;end
[b,c]end

Contoh penggunaan:

>> t(2,3)
=> [3, 8]
>> t(4,7)
=> [9, 32]
>> t(1,1)
=> [1, 2]
Darren Stone
sumber
1

Ruby (69 karakter) CoffeeScript (59 karakter)

Ini adalah fungsi yang mengambil pembilang dan penyebut sebagai argumen dan mengembalikan array yang berisi pembilang dan penyebut setelah penambangan.

g=(a,b,x=0,y=1)->c=a>=b;a&&g(a-b*c,b-a*!c,2*x+c,2*y)||[x,y]

Demo online

Ini menggunakan pendekatan yang sama dengan solusi GolfScript saya di atas, tetapi jauh lebih mudah dibaca karena saya bisa menggunakan 4 variabel tanpa harus khawatir tentang tinju dan unboxing ke dalam array. Saya memilih CoffeeScript karena tidak awalan variabel dengan $(20 karakter disimpan misalnya PHP), memiliki sintaks definisi fungsi pendek yang memungkinkan nilai parameter default (jadi tidak perlu membungkus f(a,b,x,y)fungsi g(a,b) = f(a,b,0,1)), dan memungkinkan saya menggunakan Boolean sebagai bilangan bulat di ekspresi dengan nilai yang bermanfaat. Bagi mereka yang tidak mengetahuinya, CoffeeScript tidak memiliki operator ternary C-style standar ( C?P:Q), tetapi saya dapat menggantikannya di C&&P||Qsini karena Ptidak akan pernah palsu.

Alternatif yang bisa dibilang lebih elegan, tapi tak kalah pendek, adalah mengganti pengurangan berulang dengan pembagian dan modulo:

f=(a,b,x=0,y=1,p=0)->a&&f(b%a,a,(x+p<<b/a)-p,y<<b/a,1-p)||[x+p,y]

(65 karakter; demo online ). Menulisnya dengan cara ini memaparkan hubungan dengan algoritma Euclid.

Peter Taylor
sumber
Anda tidak perlu tanda kurung di sekitar a<byang menghemat satu arang. Inlining cmemberi dua lagi. Anda juga dapat mempertimbangkan sintaks f=->a,b,x=0,y=1{...}untuk definisi yang lebih pendek.
Howard
@Howard, saya tidak tahu versi Ruby yang Anda gunakan, tetapi di IDEOne saya mendapatkan kesalahan sintaks jika saya mencoba menghapus tanda kurung itu atau menggunakan sintaks fungsi tersebut.
Peter Taylor
Coba c=a<b ?dengan ruang ekstra setelahnya b. Kalau tidak, tanda tanya diperlakukan sebagai bagian dari b.
Howard
0

Python - 531

Solusi ungolfed dalam Python, untuk berfungsi sebagai solusi referensi tempat terakhir:

def sbtree(n, d): 
    ufrac = [0, 1]
    lfrac = [1, 0]
    frac = [1, 1]
    bfrac = [1, 2]
    while(frac[0] * d != frac[1] * n): 
        if(frac[0] * d > frac[1] * n): 
            # push it towards lfrac
            lfrac[0] = frac[0]
            lfrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 - 1 
        elif(frac[0] * d < frac[1] * n): 
            # push it towards ufrac
            ufrac[0] = frac[0]
            ufrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 + 1 
        frac[0] = ufrac[0] + lfrac[0]
        frac[1] = ufrac[1] + lfrac[1]
        bfrac[1] *= 2
    return bfrac

Ini hanya melakukan pencarian biner antara fraksi, mengambil keuntungan dari fakta bahwa perantara dua fraksi akan selalu antara nilai dua fraksi tersebut.

Joe Z.
sumber
0

GolfScript, 54 karakter

'/'/n*~][2,.-1%]{[{.~3$~@+@@+[\]\}*].2$?0<}do.@?'/'@,(

Input harus diberikan pada STDIN dalam bentuk yang ditentukan dalam tugas. Anda dapat mencoba kode online .

> 4/7
9/32

> 9/7
35/64

> 5/1
31/32
Howard
sumber
0

Mathematica 138

Tidak seramping prosedur alephalpha, tapi itu yang terbaik yang bisa saya hasilkan sejauh ini.

q_~r~k_:=Nest[#+Sign@k/(2Denominator@# )&,q,Abs@k]  
g@d_:=
Module[{l=ContinuedFraction@d,p=-1},
l[[-1]]-=1;
(p=-p;# p)&/@l]
h[q_]:=Fold[r,1/2,g@q]

Pengujian

h[2/3]
h[4/7]
h[1]

3/8
9/32
1/2

DavidC
sumber
0

JavaScript 186

f=(p1,q1,p2,q2)=>{if(p1*q2+1==p2*q1){return{p:p1+p2,q:q1+q2}}let p,q,pl=0,ql=1,ph=1,qh=0;for(;;){p=pl+ph;q=ql+qh;if(p*q1<=q*p1){pl=p;ql=q}else if(p2*q<=q2*p){ph=p;qh=q}else return{p,q}}}

bisa jadi kurang, tapi saya suka golf yang bisa dibaca

caub
sumber
0

Haskell , 125 byte

n((a,b):(c,d):r)=(a,b):(a+c,b+d):n((c,d):r)
n a=a
z=zip[0..]
t x=[(j,2^i)|(i,r)<-z$iterate n[(0,1),(1,0)],(j,y)<-z r,x==y]!!0

Cobalah online!

Input dan output dalam bentuk pasangan (n,d).

Penjelasan singkat:

nmembangun baris berikutnya dari yang sebelumnya dengan melihat setiap pasangan fraksi dan memasukkan yang baru antara yang pertama dan rekursi (yang akan menempatkan fraksi kedua di sana). Kasus dasar sangat sederhana karena pada dasarnya hanya fungsi identitas. The tfungsi iterates bahwa fungsi tanpa batas didasarkan dari keadaan awal dengan hanya dua fraksi batas. tkemudian mengindeks setiap baris ( i) dan setiap item di baris ( j) dan mencari fraksi pertama yang cocok dengan apa yang kita cari. Ketika menemukannya menghasilkan jsebagai pembilang dan 2^isebagai penyebut.

pengguna1472751
sumber