Keluarkan nomor rasional ke-n sesuai dengan urutan Stern-Brocot

30

Urutan Stern-Brocot adalah urutan seperti Fibonnaci yang dapat dibangun sebagai berikut:

  1. Inisialisasi urutan dengan s(1) = s(2) = 1
  2. Atur penghitung n = 1
  3. Tambahkan s(n) + s(n+1)ke urutan
  4. Tambahkan s(n+1)ke urutan
  5. Bertambah n, kembali ke langkah 3

Ini setara dengan:

s (n) = \ begin {cases} 1 & \ textrm {if} n = 1 \ s (\ frac n 2) & \ textrm {if} n \ textrm {is even} \ s (\ frac {n-1 } 2) + s (\ frac {n + 1} 2) & \ textrm {kalau tidak} \ end {cases}

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/3adalah bilangan rasional keempat dalam urutan, tetapi bilangan yang setara 2/6, 3/9dll 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 mana adan bmerupakan entri yang relevan dalam urutan Stern-Brocot. Mengevaluasi fraksi sebelum output tidak diizinkan. Misalnya, untuk input 12, output seharusnya 2/5, bukan 0.4.
  • Celah standar tidak diijinkan

Ini , 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

Sok
sumber
Bisakah output menggunakan Trues bukannya 1s?
Loovjo
1
@Loovjo Tidak, True/2bukan fraksi yang valid (sejauh yang saya ketahui). Selain itu, Truetidak selalu 1- beberapa bahasa digunakan -1untuk menghindari potensi kesalahan saat menerapkan operator bitwise. [rujukan?]
Sok
terkait
flawr
2
Kutipan
mbomb007
1
@ Oke tetapi dengan Python, Truesama dengan 1dan True/2akan 1/2.
Leaky Nun

Jawaban:

3

Jelly , 14 byte

3ẋḶŒpḄċ
’Ç”/⁸Ç

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

3ẋḶŒpḄċ
3ẋ       3, repeated a number of times equal to {the argument}
  Ḷ      Map 3 to [0, 1, 2]
   Œp    Take the cartesian product of that list
     Ḅ   Convert binary (or in this case hyperbinary) to a number
      ċ  Count number of occurrences of {the argument} in the resulting list

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

’Ç”/⁸Ç
’Ç      Helper function (Ç), run on {the input} minus 1 (‘)
  ”/    {Output that to stdout}; start again with the constant '/'
    ⁸Ç  {Output that to stdout}; then run the helper function (Ç) on the input (⁸)

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
Astaga, Anda tidak bercanda tentang hal itu menjadi tidak efisien - pada TIO 12 dibutuhkan 20-an untuk menyelesaikan, dan 13 kali keluar sepenuhnya! Diterima, meskipun saya tidak dapat memverifikasi semua kasus uji.
Sok
11

CJam (20 byte)

1_{_@_2$%2*-+}ri*'/\

Demo online . Perhatikan bahwa ini diindeks 0. Untuk menjadikannya 1-diindeks, ganti inisial 1_dengan T1.

Pembedahan

Ini menggunakan karakterisasi karena Moshe Newman itu

fraksi a(n+1)/a(n+2)dapat dihasilkan dari fraksi sebelumnya a(n)/a(n+1) = xoleh1/(2*floor(x) + 1 - x)

Kalau x = s/tbegitu kita dapatkan

  1 / (2 * floor(s/t) + 1 - s/t)
= t / (2 * t * floor(s/t) + t - s)
= t / (2 * (s - s%t) + t - s)
= t / (s + t - 2 * (s % t))

Sekarang, jika kita mengasumsikan itu sdan tmenjadi koprime maka

  gcd(t, s + t - 2 * (s % t))
= gcd(t, s - 2 * (s % t))
= gcd(t, -(s % t))
= 1

Jadi a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))berfungsi dengan sempurna.

1_           e# s=1, t=1
{            e# Loop...
  _@_2$%2*-+ e#   s, t = t, s + t - 2 * (s % t)
}
ri*          e# ...n times
'/\          e# Separate s and t with a /
Peter Taylor
sumber
Sukai metodologi di sini, jawaban yang luar biasa!
Sok
Jika Anda menggulir lebih jauh ke bawah entri OEIS Anda akan menemukan bahwa Mike Stay sudah mengirimkan formula itu.
Neil
11

Haskell, 78 77 65 58 byte

Tanpa malu-malu mencuri pendekatan yang dioptimalkan memberi kita:

(s#t)0=show s++'/':show t
(s#t)n=t#(s+t-2*mod s t)$n-1
1#1

Terima kasih kepada @nimi karena bermain golf beberapa byte menggunakan fungsi infix!

(Tetap) menggunakan pengindeksan berbasis 0.


Pendekatan lama:

s=(!!)(1:1:f 0)
f n=s n+s(n+1):s(n+1):(f$n+1)
r n=show(s n)++'/':(show.s$n+1)

Sial format output ... Dan operator pengindeksan. EDIT: Dan diutamakan.

Fakta menyenangkan: jika daftar heterogen adalah sesuatu, baris terakhir bisa menjadi:

r n=show>>=[s!!n,'/',s!!(n+1)]
ThreeFx
sumber
Menggunakan penjaga untuk mengikat s!!nharus satu byte lebih pendek:f n|x<-s!!n=x:x+x+1:f$n+1
Laikoni
@Laikoni s!!n+1tidak (s!!n)+1tetapi s!!(n+1)itulah sebabnya saya tidak bisa melakukan itu: /
ThreeFx
Memang, itu seharusnya sudah jelas. Hanya ... begitu banyak s!!ndi sana!
Laikoni
1
Anda dapat menggunakan ++'/':(show.s$n+1)di runtuk menyimpan byte.
nimi
1
Beralih ke fungsi infiks: (s#t)0=show..., (s#t)n=t#(s+t-2*mod s t)$n-1, r=1#1. Anda bahkan dapat menghilangkan r, yaitu baris terakhir adalah adil 1#1.
nimi
6

Jelly , 16 byte

L‘Hị⁸Sṭ
1Ç¡ṫ-j”/

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

1Ç¡ṫ-j”/  Main link. Argument: n

1         Set the return value to 1.
 Ç¡       Apply the helper link n times.
   ṫ-     Tail -1; extract the last two items.
     j”/  Join, separating by a slash.


L‘Hị⁸Sṭ   Helper link. Argument: A (array)

L         Get the length of A.
 ‘        Add 1 to compute the next index.
  H       Halve.
   ị⁸     Retrieve the item(s) of A at those indices.
          If the index in non-integer, ị floors and ceils the index, then retrieves
          the items at both indices.
    S     Compute the sum of the retrieved item(s).
     ṭ    Tack; append the result to A.
Dennis
sumber
5

05AB1E , 34 33 25 23 byte

XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý

Penjelasan

XX‚                        # push [1,1]
   ¹G           }          # input-1 times do
     Â                     # bifurcate
      2£                   # take first 2 elements of reversed list
        DO¸                # duplicate and sum 1st copy, s(n)+s(n+1)
           s¦              # cut away the first element of 2nd copy, s(n)
             ìì            # prepend both to list
               ¨           # remove last item in list
                 R2£       # reverse and take the first 2 elements
                    '/ý    # format output
                           # implicitly print

Cobalah online

Disimpan 2 byte berkat Adnan.

Emigna
sumber
Apakah ini juga berfungsi ?: XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý.
Adnan
@Adnan Memang. Saya lupa ýbisa memformat daftar. Bagus.
Emigna
4

MATL , 20 byte

FT+"@:qtPXnosV47]xhh

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 20setidaknya.

Cobalah online!

Penjelasan

FT+      % Implicitly take input n. Add [0 1] element-wise. Gives [n n+1]
"        % For each k in [n n+1]
  @:q    %   Push range [0 1 ... k-1]
  tP     %   Duplicate and flip: push [k-1 ... 1 0]
  Xn     %   Binomial coefficient, element-wise. Gives an array
  os     %   Number of odd entries in that array
  V      %   Convert from number to string
  47     %   Push 47, which is ASCII for '\'
]        % End for each
x        % Remove second 47
hh       % Concatenate horizontally twice. Automatically transforms 47 into '\'
         % Implicitly display
Luis Mendo
sumber
4

Python 2, 85 81 byte

x,s=input(),[1,1]
for i in range(x):s+=s[i]+s[i+1],s[i+1]
print`s[x-1]`+"/"+`s[x]`

Kiriman ini diindeks 1.

Menggunakan fungsi rekursif, 85 byte:

s=lambda x:int(x<1)or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`

Jika output suka True/2diterima, ini adalah 81 byte:

s=lambda x:x<1 or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`
Loovjo
sumber
3

JavaScript (ES6), 43 byte

f=(i,n=0,d=1)=>i?f(i-1,d,n+d-n%d*2):n+'/'+d

1-diindeks; ubah ke n=1untuk 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:

abba+b2(amodb)
Neil
sumber
3

Python 2, 66 byte

f=lambda n:1/n or f(n/2)+n%2*f(-~n/2)
lambda n:`f(n)`+'/'+`f(n+1)`

Menggunakan rumus rekursif.

Tidak
sumber
3

C (GCC), 79 byte

Menggunakan pengindeksan berbasis 0.

s(n){return!n?:n%2?s(n/2):s(-~n/2)+s(~-n/2);}r(n){printf("%d/%d",s(n),s(n+1));}

Ideone

betseg
sumber
1
x?:yadalah ekstensi gcc.
rici
3

Sebenarnya, 18 byte

11,`│;a%τ@-+`nk'/j

Cobalah online!

Solusi ini menggunakan rumus Peter dan juga diindeks 0. Terima kasih kepada Leaky Nun untuk satu byte.

Penjelasan:

11,`│;a%τ@-+`nk'/j
11                  push 1, 1
  ,`│;a%τ@-+`n      do the following n times (where n is the input):
                      stack: [t s]
    │                 duplicate the entire stack ([t s t s])
     ;                dupe t ([t t s t s])
      a               invert the stack ([s t s t t])
       %              s % t ([s%t s t t])
        τ             multiply by 2 ([2*(s%t) s t t])
         @-           subtract from s ([s-2*(s%t) s t])
           +          add to t ([t+s-2*(s%t) t])
                      in effect, this is s,t = t,s+t-2*(s%t)
              k'/j  push as a list, join with "/"
Mego
sumber
@ LeakyNun saya akan menunda perbaikan itu sampai ada klarifikasi dari OP.
Mego
2

MATL , 32 30 byte

1i:"tt@TF-)sw@)v]tGq)V47bG)Vhh

Ini menggunakan pendekatan langsung: menghasilkan cukup anggota urutan, mengambil dua yang diinginkan dan memformat output.

Cobalah online!

Luis Mendo
sumber
2

R, 93 byte

f=function(n)ifelse(n<3,1,ifelse(n%%2,f(n/2-1/2)+f(n/2+1/2),f(n/2)))
g=function(n)f(n)/f(n+1)

Secara harfiah implementasi paling sederhana. Berusaha sedikit bermain golf.

pengguna5957401
sumber
2

m4, 131 byte

define(s,`ifelse($1,1,1,eval($1%2),0,`s(eval($1/2))',`eval(s(eval(($1-1)/2))+s(eval(($1+1)/2)))')')define(r,`s($1)/s(eval($1+1))')

Mendefinisikan makro ryang r(n)mengevaluasi sesuai dengan spesifikasi. Tidak benar-benar bermain golf sama sekali, saya hanya memberi kode formula.

Program man
sumber
2

Ruby, 49 byte

Ini diindeks 0 dan menggunakan rumus Peter Taylor. Saran golf diterima.

->n{s=t=1;n.times{s,t=t,s+t-2*(s%t)};"#{s}/#{t}"}
Sherlock9
sumber
1

> <> , 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).

&01\$n"/"on;
&?!\:@}:{:@+@%2*-&1-:

Ia mengharapkan input hadir pada stack, jadi +2 byte untuk -vflag. Cobalah online!

Sok
sumber
1

Oktaf, 90 byte

function f(i)S=[1 1];for(j=1:i/2)S=[S S(j)+S(j+1) (j+1)];end;printf("%d/%d",S(i),S(i+1));end
dcsohl
sumber
1

C #, 91 90 byte

n=>{Func<int,int>s=_=>_;s=m=>1==m?m:s(m/2)+(0==m%2?0:s(m/2+1));return$"{s(n)}/{s(n+1)}";};

Diputar ke Func<int, string>. Ini adalah implementasi rekursif.

Tidak Disatukan:

n => 
{
    Func<int,int> s = _ => _; // s needs to be set to use recursively. _=>_ is the same byte count as null and looks cooler.
    s = m =>
        1 == m ? m               // s(1) = 1
        : s(m/2) + (0 == m%2 ? 0 // s(m) = s(m/2) for even
        : s(m/2+1));             // s(m) = s(m/2) + s(m/2+1) for odd
    return $"{s(n)}/{s(n+1)}";
};

Edit: -1 byte. Ternyata C # tidak membutuhkan spasi di antara returndan $untuk string yang diinterpolasi.

susu
sumber
1

J, 29 byte

([,'/',])&":&([:+/2|]!&i.-)>:

Pemakaian

Nilai n yang besar membutuhkan akhiran xyang menunjukkan penggunaan bilangan bulat yang diperluas.

   f =: ([,'/',])&":&([:+/2|]!&i.-)>:
   f 1
1/1
   f 10
3/5
   f 50
7/12
   f 100x
7/19
   f 1000x
11/39
mil
sumber
100dianggap sebagai "nilai besar"?
dcsohl
1
@ dcsohl Dalam metode ini, koefisien binomial dihitung, dan untuk n = 100, yang terbesar dihitung adalah C (72, 28) = 75553695443676829680> 2 ^ 64 dan akan membutuhkan bilangan bulat yang diperluas untuk menghindari nilai floating point.
mil
1

Mathematica, 108 106 101 byte

(s={1,1};n=1;a=AppendTo;t=ToString;Do[a[s,s[[n]]+s[[++n]]];a[s,s[[n]]],#];t@s[[n-1]]<>"/"<>t@s[[n]])&
numbermaniac
sumber
1

R , 84 byte

function(n,K=c(1,1)){for(i in 1:n)K=c(K,K[i]+K[i+1],K[i+1])
paste0(K[i],"/",K[i+1])}

Cobalah online!

The pelaksanaan R tua tidak mengikuti spesifikasi, mengembalikan floating point bukan string, jadi inilah salah satu yang tidak.

Giuseppe
sumber