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/1
dan 1/0
sebagai "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 n
iterasi th), ada 2^n + 1
unsur-unsur dalam urutan, yang kita dapat menganggap fraksi dari 0/2^n
ke 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.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
, dll). Jika angka yang dihasilkan untuk suatu simpul adalahn
, maka2^lg n
(log biner) adalah bit tertinggi yang diaturn
, 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).Jawaban:
GolfScript (
49 4846 karakter)atau
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):
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).
sumber
Mathematica,
130 114111 karakterContoh:
sumber
Ruby,
132125Rubied & golf solusi referensi dari @ Joz.
Contoh penggunaan:
sumber
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.
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 membungkusf(a,b,x,y)
fungsig(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 diC&&P||Q
sini karenaP
tidak akan pernah palsu.Alternatif yang bisa dibilang lebih elegan, tapi tak kalah pendek, adalah mengganti pengurangan berulang dengan pembagian dan modulo:
(65 karakter; demo online ). Menulisnya dengan cara ini memaparkan hubungan dengan algoritma Euclid.
sumber
a<b
yang menghemat satu arang. Inliningc
memberi dua lagi. Anda juga dapat mempertimbangkan sintaksf=->a,b,x=0,y=1{...}
untuk definisi yang lebih pendek.c=a<b ?
dengan ruang ekstra setelahnyab
. Kalau tidak, tanda tanya diperlakukan sebagai bagian darib
.Python - 531
Solusi ungolfed dalam Python, untuk berfungsi sebagai solusi referensi tempat terakhir:
Ini hanya melakukan pencarian biner antara fraksi, mengambil keuntungan dari fakta bahwa perantara dua fraksi akan selalu antara nilai dua fraksi tersebut.
sumber
GolfScript, 54 karakter
Input harus diberikan pada STDIN dalam bentuk yang ditentukan dalam tugas. Anda dapat mencoba kode online .
sumber
Mathematica 138
Tidak seramping prosedur alephalpha, tapi itu yang terbaik yang bisa saya hasilkan sejauh ini.
Pengujian
sumber
JavaScript 186
bisa jadi kurang, tapi saya suka golf yang bisa dibaca
sumber
Haskell , 125 byte
Cobalah online!
Input dan output dalam bentuk pasangan
(n,d)
.Penjelasan singkat:
n
membangun 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. Thet
fungsi iterates bahwa fungsi tanpa batas didasarkan dari keadaan awal dengan hanya dua fraksi batas.t
kemudian mengindeks setiap baris (i
) dan setiap item di baris (j
) dan mencari fraksi pertama yang cocok dengan apa yang kita cari. Ketika menemukannya menghasilkanj
sebagai pembilang dan2^i
sebagai penyebut.sumber