Ketika Anda mengonversi pecahan menjadi angka desimal dan Anda ingin menyimpan angka itu, Anda sering harus membulatkannya, karena Anda hanya ingin menggunakan sejumlah memori. Katakanlah Anda hanya dapat menyimpan 5 angka desimal, kemudian 5/3 menjadi 1.6667. Jika Anda dapat menyimpan hanya 2 digit desimal, itu akan menjadi 1,7 (sekarang dengan asumsi selalu antara 0 dan 9,99 ...).
Jika Anda sekarang mencoba untuk membalik proses itu dengan 1,7 dan Anda ingin mendapatkan pecahan Anda kembali, itu bisa sulit, karena Anda tahu bahwa 1,7 hanya angka bulat. Tentu saja Anda dapat mencoba 17/10 tapi itu fraksi yang agak 'jelek' dibandingkan dengan 5/3 yang 'elegan'.
Jadi tujuannya sekarang menemukan pecahan a / b dengan penyebut terkecil b, yang menghasilkan angka desimal bulat ketika dibulatkan dengan benar.
Detail
Input berisi string dengan angka 1 hingga 5 digit antara 0 (termasuk) dan 10 (tidak termasuk) dengan tanda '.' setelah digit pertama. Katakanlah n
menunjukkan jumlah digit. Output harus berupa daftar / larik dua bilangan bulat [numerator, denominator]
atau tipe data rasional (Anda dapat membuat sendiri atau menggunakan built-in) di mana pembilangnya tidak negatif dan penyebutnya positif. Pembilang pecahan / penyebut harus sama dengan input ketika dibulatkan dengan benar ke n
digit (yang berarti n-1
digit setelah titik desimal).
Pembatasan: hanya satu pernyataan loop yang dibolehkan. Ini berarti bahwa Anda hanya dapat menggunakan satu pernyataan perulangan tunggal (seperti for
atau while
atau goto
dll. Serta loop fungsional seperti map
atau fold
yang menerapkan kode ke setiap elemen daftar / larik) di seluruh kode Anda, tetapi Anda bebas untuk 'menyalahgunakannya' atau gunakan rekursi dll.
Anda harus menulis fungsi. Jika bahasa Anda tidak memiliki fungsi (atau bahkan jika itu), Anda dapat mengasumsikan bahwa input disimpan dalam variabel (atau input melalui stdin) dan cetak hasilnya atau tulis ke file. Jumlah byte terendah menang.
Pembulatan
Pembulatan harus mengikuti aturan pembulatan 'konvensional', yaitu jika angka terakhir yang akan terpotong adalah 5 atau lebih besar, Anda akan dibulatkan ke atas, dan Anda akan dibulatkan ke bawah untuk kasus lain, jadi misalnya:
4.5494 akan dihasilkan saat pembulatan ke
- 1 digit: 5
- 2 digit: 4,5
- 3 digit: 4,55
- 4 digit: 4,549
Contohnya
Harap sertakan kasus uji berikut dan yang 'menarik' lainnya:
Input 1.7 Output 5/3
Input 0. Output 0/1
Input 0.001 Output 1/667
Input 3.1416 Output 355/113
repeat
membuat daftar argumennya yang tak terbatas. Sepertinya tidak, tetapi sebenarnya memiliki kompleksitas waktu O (1). Tapi saya kira menyortir setiap kasus secara individual lebih baik daripada tidak mengizinkan bahasa fungsional.for n in numbers: f(g(n))
setara denganmap(f, map(g, numbers))
. Versi fungsional menggunakanmap
dua kali, haruskah itu benar-benar dianulir?Jawaban:
CJam,
414036 byteAsuum string input disimpan dalam Q, yang secara eksplisit diizinkan oleh pertanyaan. Cobalah online.
Uji kasus
Bagaimana itu bekerja
sumber
T-SQL 254
Sementara T-SQL tidak benar-benar cocok untuk hal semacam ini, itu menyenangkan untuk dicoba. Kinerja semakin buruk semakin tinggi penyebutnya. Ini terbatas pada penyebut 1000.
Input adalah variabel float @
Rincian permintaan
sumber
3.14159
dan memberi saya dengan baik355/113
Haskell,
6259andai saja namanya tidak begitu panjang ...
ini adalah fungsi yang mengembalikan
Rational
nilai.Penjelasan: fungsi
approxRational
adalah fungsi yang mengambil angka float dan flo epsilon dan mengembalikan rasional paling sederhana yang ada di jarak epsilon input. pada dasarnya, mengembalikan perkiraan yang paling sederhana dari float ke rasional dalam jarak "kesalahan yang dapat dimaafkan".mari manfaatkan fungsi ini untuk kita gunakan. untuk ini kita perlu mencari tahu berapa luas float yang membulatkan ke angka yang diberikan. kemudian memasukkan ini ke dalam
approxRational
fungsi akan memberi kita jawaban.mari kita coba 1.7, misalnya. float terendah yang membulatkan ke 1,7 adalah 1,65. lebih rendah tidak akan membulatkan ke 1,7. sama halnya, batas atas float yang membulatkan ke 1.7 adalah 1.75.
kedua batasnya adalah batasnya adalah angka input +/- 0,05. dapat dengan mudah ditunjukkan bahwa jarak ini selalu
5 * 10 ^ -(the length of the input - 1)
(-1 karena selalu ada '.' dalam input). dari sini kodenya cukup sederhana.kasus uji:
sayangnya itu tidak bekerja pada "0." karena fungsi parser Haskell tidak mengenali a
.
di akhir float. ini dapat diperbaiki untuk 5 byte dengan menggantiread s
denganread$s++"0"
.sumber
Ruby,
127125 byteMenentukan fungsi
f
yang mengembalikan hasilnya sebagai aRational
. Misalnya jika Anda menambahkan kode iniAnda mendapatkan
Loopnya melewati penyebut. Saya mulai dengan fraksi penuh, misalnya
31416/10000
untuk contoh terakhir. Kemudian saya mengurangi penyebutnya, menurunkan pembilangnya secara proporsional (dan memutarnya). Jika putaran rasional yang dihasilkan sama dengan nomor input, saya ingat bagian terbaik baru.sumber
Mathematica,
4953 karakterPemakaian:
Keluaran:
Kasus uji:
Kasus 0,001 menurut saya aneh; karena fungsi rasionalisasi tidak berfungsi sesuai dengan deskripsinya, ketika tidak menemukan kasus 1/667. Ini harus menampilkan nomor dengan penyebut terkecil yang ada dalam batas yang ditentukan.
sumber
0.001
tidak cocok dengan OP karenaRationalize
tidak di bawah batasan untuk meminimalkan penyebut. Seperti yang saya sebutkan pada haskeller yang bangga, fungsi perkiraan rasional yang dapat meminimalkan penyebut adalah sangat esoterik (singkatnya karena ini adalah cara yang buruk dan tidak efisien untuk memperkirakan angka). Saya biasanya tidak berharap itu menjadi fungsi perpustakaan standar.1/999
. 999 menjadi penyebut terendah (dapat diterima) hanya untuk kesalahan antara sekitar 1e-6 dan 2e-6. Batas kesalahan jelas 5e-4. Jadi, apa pun yang dilakukan Mathematica dalam kasus itu, itu pasti tidak berfungsi secara spesifik. : PPython 2.7+, 111 karakter
Bukti bahwa Anda dapat menulis kode mengerikan dalam bahasa apa pun:
Keluaran
sumber
APL, 50
Selama Anda tidak menghitung
eval
dantoString
sebagai loopPenjelasan
Pendekatannya adalah untuk beralih lebih dari 1 hingga 10.000 sebagai penyebut dan menghitung pembilang yang paling cocok dengan float, kemudian periksa apakah kesalahannya masih dalam batas. Terakhir, pilih pasangan terkecil dari semua fraksi yang ditemukan.
(⍎x←⍞)
Ambil input string dari layar, tetapkan kex
, dan evaluasi⍳1e5
Hasilkan array dari 1 hingga 10.000{...}¨
Untuk setiap elemen array, panggil fungsi dengannya dan(⍎x←⍞)
dan argumen (loop)⍺×⍵
Mengalikan argumen⌊.5+
Membulatkan (dengan menambahkan 0,5 kemudian membulatkan)n←
Tetapkan untukn
⍺-⍵÷⍨
Membagi dengan argumen kanan, lalu kurangi dari argumen kiri(10*⍴x)×
Lipat ke 10 dengan kekuatan "panjangx
"|
Ambil nilai absolut50>
Periksa jika kurang dari 50 (panjangnyax
2 lebih daripada jumlah dp, jadi gunakan 50 di sini alih-alih 0,5):n ⍵⋄''
Jika cek sebelumnya mengembalikan true, maka kembalikan arrayn
dan argumen yang benar, kalau tidak kembalikan string kosong.⍎⍕
toString
dan kemudianeval
untuk mendapatkan array dari semua angka dalam array2↑
Pilih hanya 2 elemen pertama, yang merupakan pasangan pembilang-penyebut pertama yang ditemukansumber
GNU dc, 72 byte
Tidak ada loop - dc bahkan tidak memilikinya. Sebaliknya kontrol berasal dari makro ekor tunggal rekursif - idiomatik untuk dc.
Keluaran:
Fiuh. Penjelasan sebagian dalam jawaban ini .
sumber
Mathematica, 111 karakter
Cukup sederhana sebenarnya, dan saya tidak berpikir itu konvergen di mana saja secepat solusi lain, karena pembilang dan penyebut hanya bertambah satu per satu. Saya kebanyakan ingin menemukan solusi sederhana untuk ini. Saya harus melihat jawaban lain dan melihat apa yang terjadi di sana.
Keluaran
Apakah ada orang di sini yang merayakan Hari Perkiraan Pi ?
sumber
Applescript,> 300 byte
Saya ingin melakukan ini dalam bahasa yang secara native melakukan jenis pembulatan yang diperlukan. Ternyata Applescript sesuai dengan tagihan. Kemudian saya melihat enum
rounding as taught in school
, dan tidak bisa menolak menggunakannya, meskipun tidak ada daya saing Applescript untuk tujuan bermain golf:Ini bisa bermain golf sedikit lebih, tapi mungkin tidak sepadan.
Keluaran:
sumber
SM,
151148 byteEdit - versi lebih cepat dan lebih pendek
test case yang sama.
Banyak yang mirip dengan versi sebelumnya, tetapi alih-alih mencoba semua kombinasi n / d yang mungkin, kami mendaki bukit di atas sisa v dan quotients mundur dari kelipatan m == v * d dan penyebut d. Sekali lagi ketepatan perhitungannya sama.
Ini tidak terurai:
Versi ini benar-benar hanya memiliki satu loop dan hanya melakukan $ \ Theta \ left (\ operatorname {fractional_decimals} (v) \ right) $ operasi aritmatika.
Asli - versi lambat
Fungsi ini menghitung nominator n terkecil dan penyebut d sedemikian sehingga fraksi n / d dibulatkan ke fractional_decimals (v) digit sama dengan nilai desimal yang diberikan v.
Kasus cobaan:
Dan di sini tidak terurai:
Saya akui, saya sedikit curang dengan meniru loop dalam kedua di dalam loop luar tunggal, tetapi tanpa menggunakan pernyataan loop lebih lanjut. Dan itulah mengapa ia melakukan $ \ Theta \ left (v \ operatorname {fractional_decimals} (v) ^ 2 \ right) $ operasi aritmatika.
sumber
C, 233
Ini bekerja dengan memanggil fungsi rasionalisasi r () dengan penyebut awal 1. Fungsi mulai menambah pembilang, dan memeriksa setiap kenaikan apakah nomor yang dihasilkan, ketika dibulatkan ke jumlah digit yang sama seperti aslinya, memiliki string yang sama representasi seperti aslinya. Begitu pembilangnya bertambah sedemikian rupa sehingga hasilnya lebih besar dari yang asli, fungsinya menambah penyebut dan memanggil dirinya sendiri.
Ini tentu saja menggunakan kode yang jauh lebih banyak, tetapi saya pikir semangat masalah membebaskan pendekatan sederhana ini; yang kita tahu, fungsi rationalize internal () dari bahasa modern memiliki banyak loop internal.
Perhatikan bahwa ini tidak berfungsi untuk input "0." karena itu bukan cara standar untuk menulis float, jadi ketika menulis ulang float ke string, hasilnya tidak akan pernah menjadi "0.".
Spesifikasi menginginkan fungsi yang mengembalikan nilai alih-alih hanya mencetak ke layar, karenanya argumen-passing.
Kode (ungolfed):
Pemakaian:
Kode golf:
sumber
approxRational
memiliki hanya satu fungsi pembantu rekursif, dan tidak ada perulangan lebih dari itu.Pure Bash, 92 byte
Sebagai penjelasan parsial untuk jawaban ini , ini dia porting ke bash:
Terutama:
Keluaran:
sumber
int
port yang cukup mudah - hanya untuk cJavaScript (E6) 85
Tidak disatukan
Uji di konsol FireFox / FireBug
Keluaran
sumber