Anda dapat membuat daftar semua rasional 0 <r ≤ 1 dengan mencantumkannya diurutkan terlebih dahulu oleh penyebut dan kemudian oleh pembilang:
1 1 1 2 1 3 1 2 3 4 1 5 1 2 3 4 5
- - - - - - - - - - - - - - - - -
1 2 3 3 4 4 5 5 5 5 6 6 7 7 7 7 7
Perhatikan bahwa kami melewatkan angka rasional apa pun yang sudah terjadi sebelumnya. Misal 2/4 dilewati karena kami sudah mencantumkan 1/2.
Dalam tantangan ini, kami hanya tertarik pada pembilang. Melihat daftar di atas, tulislah fungsi atau program dengan mengambil bilangan bulat positif n yang mengembalikan pembilang ke - n dari daftar.
Testcases:
1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 3
7 -> 1
8 -> 2
9 -> 3
50 -> 4
80 -> 15
(0,1]
Jawaban:
MATL ,
1713 byteCobalah online! Atau verifikasi semua kasus uji .
Ukuran input mungkin dibatasi oleh akurasi floating point. Semua test case memberikan hasil yang benar.
Penjelasan
Ini menghasilkan semua fraksi
k/m
dengank
,m
dalam[1 2 ...n]
, sebagai matriksn
×n
. Baris menunjukkan pembilang dan kolom menunjukkan penyebut. Sebenarnya entri matriks berisi fraksi terbalikm/k
, bukank/m
, tetapi ini tidak relevan dan dapat diabaikan di sisa penjelasan.Entri matriks secara implisit dianggap diurutkan dalam urutan kolom-utama. Dalam hal ini sesuai dengan urutan yang disyaratkan: penyebut, kemudian pembilang.
Tiga jenis entri perlu diabaikan dari matriks ini:
k/m
,,k>m
yang memiliki nilai yang sama dengan entri sebelumnya (misalnya,2/4
diabaikan karena sama dengan1/2
)k/k
,k>1
. Entri yang memiliki pembilang melebihi penyebutk/m
,k<m
(ini bukan bagian dari masalah).Mengabaikan entri dilakukan dengan
unique
fungsi, yang secara stabil menghapus nilai duplikat dan menampilkan indeks entri yang bertahan. Dengan ini, entri tipe 1 di atas secara otomatis dihapus. Untuk menangani tipe 2 dan 3, entri matriks di diagonal dan di bawah ini diatur ke0
. Dengan cara ini, semua entri nol akan dihapus kecuali yang pertama (sesuai dengan fraksi yang valid1/1
).Pertimbangkan input
4
sebagai contoh.sumber
Jelly ,
119 byteCobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
Mathematica, 53 byte
sumber
Haskell, 40 byte
Fungsi anonim. Cukup mudah: menggunakan pemahaman daftar untuk menghasilkan daftar tanpa batas, mengulang semua pembilang
n
dan penyebut yang relatif primad
. Untuk mengonversi indeks-nol menjadi indeks-satu, kami menambahkan0
, yang memerlukan4
byte.sumber
n<-[0..d]
menambahkan nol dengan cara yang lebih singkat dan menyimpan 4 bytePyth, 13 byte
Cobalah online. Suite uji.
sumber
Pyth, 11 byte
Cobalah online: Demonstrasi
Penjelasan:
sumber
Sebenarnya , 15 byte
Jawaban ini didasarkan pada jawaban Dennis 'Jelly . Saya menggunakan
HN
di akhir untuk menghindari masalah dengan pengindeksan 0 dan perlu mengurangi n dan bertukar di awal atau akhir.H
mendapatn
anggota pertama dari daftar pembilang yang menghasilkan danN
mendapat anggota terakhir dari pilihan itu, yaitun
pembilang ke-5, semua tanpa mengotak-atik operasi tumpukan. Saran bermain golf diterima. Cobalah online!Tidak melakukanolf
sumber
Python,
111110 byteFraksi diwakili dengan
x/y
. Argumenn
dikurangi ketika fraksi pas baru ditemukan (gcd
darifractions
cek dapat fraksi dikurangi). Dalam setiap iterasi loop,x
ditambahkan, maka, jikax>=y
, serangkaian fraksi baruy+1
dimulai,>
karena "kasus khusus"(x,y)=(2,1)
, di-golfx>y
.Saya yakin ini bisa bermain golf lebih banyak, tetapi saya kehilangan tempat saya bisa memperbaikinya.Menemukannya.Tautan ke kode dan uji kasus
sumber
JavaScript (ES6), 95 byte
Bekerja dengan menghasilkan semua
n²
fraksi dengan pembilang dan penyebut dari1
ken
dan menyaring yang lebih besar dari1
atau yang sebelumnya terlihat, kemudian mengambil yangn
ke.sumber
Perl, 82 + 2 (
-pl
bendera) = 84 byteTidak Disatukan:
sumber
JavaScript (ES6), 76
Kurang golf
Uji
sumber
Clojure, 85 byte
Gunakan pemahaman daftar untuk menghasilkan daftar semua rasional, lalu filter untuk mendapatkan yang berbeda saja. Mengambil
nth
item dari daftar dan mengembalikan pembilangnya. Juga diperlukan kondisi terpisah untuk elemen pertama karena Clojure tidak dapat mengambil pembilang bilangan bulat. (untuk alasan apa pun yang menganggap bilangan bulat tidak Rasional - https://goo.gl/XETLo2 )Lihat online - https://ideone.com/8gNZEB
sumber