Urutan Stern-Brocot adalah urutan seperti Fibonnaci yang dapat dibangun sebagai berikut:
- Inisialisasi urutan dengan
s(1) = s(2) = 1
- Atur penghitung
n = 1
- Tambahkan
s(n) + s(n+1)
ke urutan - Tambahkan
s(n+1)
ke urutan - Bertambah
n
, kembali ke langkah 3
Ini setara dengan:
Di antara sifat-sifat lain, urutan Stern-Brocot dapat digunakan untuk menghasilkan setiap angka rasional positif yang mungkin. Setiap bilangan rasional akan dihasilkan tepat satu kali, dan akan selalu muncul dalam term yang paling sederhana; misalnya, 1/3
adalah bilangan rasional keempat dalam urutan, tetapi bilangan yang setara 2/6
, 3/9
dll tidak akan muncul sama sekali.
Kita dapat mendefinisikan bilangan rasional ke-n sebagai r(n) = s(n) / s(n+1)
, di mana s(n)
bilangan Stern-Brocot ke-n, seperti dijelaskan di atas.
Tantangan Anda adalah menulis program atau fungsi yang akan menghasilkan bilangan rasional ke-n yang dihasilkan menggunakan urutan Stern-Brocot.
- Algoritma yang dijelaskan di atas adalah 1-diindeks; jika entri Anda diindeks 0, sebutkan jawaban Anda
- Algoritma yang dijelaskan hanya untuk tujuan ilustrasi, output dapat diturunkan dengan cara apa pun yang Anda suka (selain hard-coding)
- Input dapat melalui STDIN, parameter fungsi, atau mekanisme input lain yang masuk akal
- Ouptut dapat berupa STDOUT, konsol, nilai pengembalian fungsi, atau aliran output wajar lainnya
- Output harus berupa string dalam bentuk
a/b
, di manaa
danb
merupakan entri yang relevan dalam urutan Stern-Brocot. Mengevaluasi fraksi sebelum output tidak diizinkan. Misalnya, untuk input12
, output seharusnya2/5
, bukan0.4
. - Celah standar tidak diijinkan
Ini kode-golf , jadi jawaban tersingkat dalam byte akan menang.
Uji kasus
Kasus uji di sini diindeks 1.
n r(n)
-- ------
1 1/1
2 1/2
3 2/1
4 1/3
5 3/2
6 2/3
7 3/1
8 1/4
9 4/3
10 3/5
11 5/2
12 2/5
13 5/3
14 3/4
15 4/1
16 1/5
17 5/4
18 4/7
19 7/3
20 3/8
50 7/12
100 7/19
1000 11/39
Entri OEIS: A002487
Video Numberphile Luar Biasa membahas urutan: Fraksi Tak Terbatas
True
s bukannya1
s?True/2
bukan fraksi yang valid (sejauh yang saya ketahui). Selain itu,True
tidak selalu1
- beberapa bahasa digunakan-1
untuk menghindari potensi kesalahan saat menerapkan operator bitwise. [rujukan?]True
sama dengan1
danTrue/2
akan1/2
.Jawaban:
Jelly , 14 byte
Cobalah online!
Ooh, sepertinya saya bisa mengalahkan jawaban yang diterima oleh @ Dennis, dan dalam bahasa yang sama pada saat itu. Ini bekerja menggunakan rumus dari OEIS: jumlah cara untuk mengekspresikan (angka minus 1) dalam hiperbinari (yaitu biner dengan 0, 1, 2 sebagai digit). Tidak seperti kebanyakan program Jelly (yang berfungsi baik sebagai program penuh atau fungsi), program ini hanya berfungsi sebagai program penuh (karena mengirimkan sebagian dari output ke stdout, dan mengembalikan sisanya; ketika digunakan sebagai program penuh, nilai pengembalian dikirim ke stdout secara implisit, jadi semua output berada di tempat yang sama, tetapi ini tidak akan berfungsi untuk pengiriman fungsi).
Versi program ini sangat tidak efisien. Anda dapat membuat program yang jauh lebih cepat yang bekerja untuk semua input hingga 2ⁿ melalui penempatan n tepat setelah
ẋ
pada baris pertama; program ini memiliki kinerja O ( n × 3ⁿ), jadi menjaga n kecil sangat penting di sini. Program yang ditulis set n sama dengan input, yang jelas cukup besar, tetapi juga jelas terlalu besar di hampir semua kasus (tapi hei, menghemat byte).Penjelasan
Seperti biasa dalam penjelasan Jelly saya, teks dalam kurung kurawal (misalnya
{the input}
) menunjukkan sesuatu yang secara otomatis diisi oleh Jelly karena operan yang hilang dalam program asli.Fungsi pembantu (menghitung dengan n th denominator, yaitu n + pembilang 1th):
Lima byte pertama pada dasarnya hanya menghasilkan semua angka hiperbiner yang mungkin hingga panjang tertentu, misalnya dengan input 3, outputnya
Ḷ
adalah [[0,1,2], [0,1,2], [0,1,2 ]] jadi produk kartesius adalah [[0,0,0], [0,0,1], [0,0,2], [0,1,0], ..., [2,2,1], [2,2,2]].Ḅ
pada dasarnya hanya mengalikan entri terakhir dengan 1, entri kedua dari belakang dengan 2, entri antepenultimate oleh 4, dll, dan kemudian menambahkan; Meskipun ini biasanya digunakan untuk mengkonversi biner ke desimal, ia dapat menangani digit 2 dengan baik, dan dengan demikian bekerja untuk hiperbinari juga. Kemudian kami menghitung berapa kali input muncul dalam daftar yang dihasilkan, untuk mendapatkan entri yang sesuai dalam urutan. (Untungnya, pembilang dan penyebutnya mengikuti urutan yang sama).Program utama (meminta pembilang dan penyebut, dan memformat output):
Entah bagaimana saya terus menulis program yang membutuhkan byte hampir sebanyak untuk menangani I / O seperti yang mereka lakukan untuk memecahkan masalah yang sebenarnya ...
sumber
CJam (20 byte)
Demo online . Perhatikan bahwa ini diindeks 0. Untuk menjadikannya 1-diindeks, ganti inisial
1_
denganT1
.Pembedahan
Ini menggunakan karakterisasi karena Moshe Newman itu
Kalau
x = s/t
begitu kita dapatkanSekarang, jika kita mengasumsikan itu
s
dant
menjadi koprime makaJadi
a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))
berfungsi dengan sempurna.sumber
Haskell,
78 77 6558 byteTanpa malu-malu mencuri pendekatan yang dioptimalkan memberi kita:
Terima kasih kepada @nimi karena bermain golf beberapa byte menggunakan fungsi infix!
(Tetap) menggunakan pengindeksan berbasis 0.
Pendekatan lama:
Sial format output ... Dan operator pengindeksan. EDIT: Dan diutamakan.
Fakta menyenangkan: jika daftar heterogen adalah sesuatu, baris terakhir bisa menjadi:
sumber
s!!n
harus satu byte lebih pendek:f n|x<-s!!n=x:x+x+1:f$n+1
s!!n+1
tidak(s!!n)+1
tetapis!!(n+1)
itulah sebabnya saya tidak bisa melakukan itu: /s!!n
di sana!++'/':(show.s$n+1)
dir
untuk menyimpan byte.(s#t)0=show...
,(s#t)n=t#(s+t-2*mod s t)$n-1
,r=1#1
. Anda bahkan dapat menghilangkanr
, yaitu baris terakhir adalah adil1#1
.Jelly , 16 byte
Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
05AB1E ,
34332523 bytePenjelasan
Cobalah online
Disimpan 2 byte berkat Adnan.
sumber
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý
.ý
bisa memformat daftar. Bagus.MATL , 20 byte
Ini menggunakan karakterisasi dalam hal koefisien binomial yang diberikan pada halaman OEIS .
Algoritma bekerja secara teori untuk semua angka, tetapi dalam praktiknya dibatasi oleh ketepatan numerik MATL, sehingga tidak berfungsi untuk entri besar. Hasilnya akurat untuk input
20
setidaknya.Cobalah online!
Penjelasan
sumber
Python 2,
8581 byteKiriman ini diindeks 1.
Menggunakan fungsi rekursif, 85 byte:
Jika output suka
True/2
diterima, ini adalah 81 byte:sumber
JavaScript (ES6), 43 byte
1-diindeks; ubah ke
n=1
untuk 0-diindeks. Halaman OEIS yang ditautkan memiliki hubungan perulangan yang berguna untuk setiap istilah dalam dua istilah sebelumnya; Saya hanya menafsirkannya sebagai pengulangan untuk setiap fraksi dalam hal fraksi sebelumnya. Sayangnya kami tidak memiliki TeX sebaris sehingga Anda hanya perlu menempelkannya ke situs lain untuk mengetahui bagaimana format ini:sumber
Python 2, 66 byte
Menggunakan rumus rekursif.
sumber
C (GCC), 79 byte
Menggunakan pengindeksan berbasis 0.
Ideone
sumber
x?:y
adalah ekstensi gcc.Sebenarnya, 18 byte
Cobalah online!
Solusi ini menggunakan rumus Peter dan juga diindeks 0. Terima kasih kepada Leaky Nun untuk satu byte.
Penjelasan:
sumber
MATL ,
3230 byteIni menggunakan pendekatan langsung: menghasilkan cukup anggota urutan, mengambil dua yang diinginkan dan memformat output.
Cobalah online!
sumber
R, 93 byte
Secara harfiah implementasi paling sederhana. Berusaha sedikit bermain golf.
sumber
m4, 131 byte
Mendefinisikan makro
r
yangr(n)
mengevaluasi sesuai dengan spesifikasi. Tidak benar-benar bermain golf sama sekali, saya hanya memberi kode formula.sumber
Ruby, 49 byte
Ini diindeks 0 dan menggunakan rumus Peter Taylor. Saran golf diterima.
sumber
> <> , 34 + 2 = 36 byte
Setelah melihat jawaban Peter Taylor yang luar biasa, saya menulis ulang jawaban tes saya (yang merupakan 82 byte yang memalukan, menggunakan rekursi yang sangat canggung).
Ia mengharapkan input hadir pada stack, jadi +2 byte untuk
-v
flag. Cobalah online!sumber
Oktaf, 90 byte
sumber
C #,
9190 byteDiputar ke
Func<int, string>
. Ini adalah implementasi rekursif.Tidak Disatukan:
Edit: -1 byte. Ternyata C # tidak membutuhkan spasi di antara
return
dan$
untuk string yang diinterpolasi.sumber
Python 2, 59 byte
Menggunakan rumus Peter dan juga diindeks 0.
Cobalah online
sumber
J, 29 byte
Pemakaian
Nilai n yang besar membutuhkan akhiran
x
yang menunjukkan penggunaan bilangan bulat yang diperluas.sumber
100
dianggap sebagai "nilai besar"?Mathematica,
108106101 bytesumber
R , 84 byte
Cobalah online!
The pelaksanaan R tua tidak mengikuti spesifikasi, mengembalikan floating point bukan string, jadi inilah salah satu yang tidak.
sumber