Fungsi Menghitung Rasional

11

Buat fungsi yang mengambil bilangan alami (mulai dari 0 inklusif), dan mengembalikan sepasang bilangan bulat positif, yang masing-masing adalah pembilang dan penyebut. Gunakan traversal diagonal. Nomor yang dihitung sebelumnya harus dilewati. (Anda dapat menghafal sekumpulan nilai yang dilewati)

Diagram:

masukkan deskripsi gambar di sini

Merah adalah nilai yang dilewati

Nilai:

  • f (0) = 1, 1
  • f (1) = 2, 1
  • f (2) = 1, 2
  • f (3) = 1, 3
  • f (4) = 3, 1 (perhatikan lompatan)
  • f (5) = 4, 1
  • f (6) = 3, 2
  • f (7) = 2, 3
  • f (8) = 1, 4
  • f (9) = 1, 5
  • f (10) = 5, 1 (perhatikan lompatan)

Anda dapat menggunakan struktur data Rasional dan operasi mereka jika ada. Kode terpendek menang.

Ming-Tang
sumber
1
Jumlah bilangan rasional yang dihitung dalam setiap diagonal adalah fungsi total dari jumlah umum diagonal itu.
Leaky Nun
Saya tahu tantangan ini sudah tua, tetapi ada jawaban yang lebih pendek dari yang diterima, jadi Anda mungkin ingin menerima kembali.
Buah Esolanging

Jawaban:

4

J, 41 36 karakter

Mengambil bilangan bulat dan mengembalikan vektor yang terdiri dari dua bilangan bulat. Solusi pertama saya yang tidak sepenuhnya diam-diam atau sepenuhnya eksplisit.

{3 :'~.;<`(<@|.)/.(,%+.)"0/~1+i.1+y'

Berikut adalah solusinya dengan spasi yang dimasukkan:

{ 3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

Sebuah penjelasan:

  1. x (, % +.) y–Sebuah vektor panjang 2 yang mewakili fraksi dengan pembilang xdan penyebut ydireduksi menjadi penyebut terkecil
  2. 1 + i. 1 + y–Sebuah vektor bilangan bulat dari 1key + 1
  3. (, % +.)"0/~ 1 + i. 1 + y–Sebuah matriks dari semua pecahan tereduksi dengan penyebut dan pembilang yang tidak direduksi dalam kisaran dari 1hingga y + 1.
  4. <`(<@|.)/. y–Sebuah array diagonal miring dari matriks y, masing-masing diagonal terbalik
  5. ~. ; y–Sebuah array diagonal diciutkan menjadi vektor elemen dengan duplikat dihapus
  6. x { y–Barang pada posisi xdiy
  7. (u v) y- sama seperti y u v y. Dalam kasus penggunaan khusus ini, uadalah {dan vsekarang3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'
FUZxxl
sumber
1
30 byte
FrownyFrog
8

Haskell, 78 karakter

q(r,f)=[(r-b,b)|b<-f[1..r-1],r`gcd`b==1]
d=reverse:id:d
f=((zip[2..]d>>=q)!!)

Contoh dijalankan:

> map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
> f 100
(17,1)
> f 1000
(3,55)

  • Sunting: (100 → 87) konyol saya, hanya menguji gcd sudah cukup!
  • Sunting: (87 → 85) trik pintar cycledan berfungsi untuk mengubah urutan baris
  • Sunting: (85 → 82) ganti cycledengan daftar tak terbatas buatan tangand
  • Sunting: (82 → 78) gcdidentitas yang diterapkan seperti yang disarankan oleh Matías
MtnViewMark
sumber
Menurut definisi, gcd (r-b) b == gcd r bdan Anda dapat mengurangi empat karakter lagi.
Matías Giovannini
3

Python, 144 karakter

def F(i):
 r,d,z=[1],1,[]
 while z[:i]==z:z+=[(x,y)for x,y in zip(r[::d],r[::-d])if all(x%j+y%j for j in r[1:])];d=-d;r+=[r[-1]+1]
 return z[i]
Keith Randall
sumber
2

Ruby 1.9, 109 106

F=->n{x=y=d=1
e=0
n.times{(x+=d).gcd(y+=e)>1&&redo
x<2?d<0?d=0:(d,e=1,-1):y<2?e<0?e=0:(d,e=-1,1):0}
[x,y]}
Lowjacker
sumber
2

OCaml + Baterai, 182 168 karakter

Ini adalah hal yang alami di Haskell tetapi hanya mungkin di OCaml:

open LazyList
let rec r(i,j)=lazy(let a,b=if(i+j)mod 2=0then i,j else j,i in
Cons((a,b),filter(fun(c,d)->a*d<>c*b)(r(if j=1 then 1,i+1else i+1,j-1))))
let f=nth(r(1,1))

Sunting: Diagonal tidak perlu

Matías Giovannini
sumber
0

Perl 6 , 75 byte

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique[$_]}

Menguji

Ini pada dasarnya menghasilkan seluruh urutan nilai-nilai rasional, hanya berhenti setelah nilai indeks dihasilkan.

(Berdasarkan golf saya untuk tantangan lain.)

Diperluas:

{  # bare block lambda with implicit parameter $_

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            
            1      # finish at one
          )

        }
         * # never stop generating values
      )


    Z/   # zip using &infix:« /  » (generates Rats)


      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            
            1
          )
        }
         * # never stop generating values
      )


  ).unique                # get only the unique values
  .[ $_ ]                 # index into the sequence
}

({1…($+=2)…1}…*)menghasilkan urutan pembilang yang tak terbatas ( |(…)digunakan di atas untuk meratakan)

(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)

(1,{1…(($||=1)+=2)…1}…*) menghasilkan urutan penyebut tanpa batas

1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
Brad Gilbert b2gills
sumber