Gambaran:
Dari Wikipedia : Fraksi Mesir adalah jumlah fraksi unit yang berbeda. Artinya, setiap fraksi dalam ekspresi memiliki pembilang yang sama dengan 1 dan penyebut yang merupakan bilangan bulat positif, dan semua penyebut berbeda satu sama lain. Nilai ekspresi tipe ini adalah bilangan rasional positif a / b. Setiap bilangan rasional positif dapat diwakili oleh fraksi Mesir.
Tantangan:
Tulis fungsi terpendek yang akan mengembalikan nilai semua penyebut untuk sekumpulan fraksi satuan terkecil yang berjumlah hingga pecahan tertentu.
Aturan / Kendala:
- Input akan menjadi dua nilai integer positif.
- Ini bisa pada
STDIN
,,argv
dipisahkan koma, dibatasi ruang, atau metode lain yang Anda inginkan.
- Ini bisa pada
- Nilai input pertama harus pembilang dan nilai input kedua penyebut.
- Nilai input pertama harus kurang dari yang kedua.
- Keluaran mungkin menyertakan nilai yang melebihi batasan memori sistem / bahasa Anda (RAM, MAX_INT, atau apa pun kendala kode / sistem lainnya). Jika ini terjadi, cukup potong hasilnya pada nilai setinggi mungkin dan catat itu entah bagaimana (yaitu
...
). - Output harus dapat menangani nilai penyebut hingga setidaknya 2.147.483.647 (2 31 -1, ditandatangani 32-bit
int
).- Nilai yang lebih tinggi (
long
, dll.) Sangat dapat diterima.
- Nilai yang lebih tinggi (
- Keluaran harus berupa daftar semua nilai penyebut dari sekumpulan pecahan unit terkecil yang ditemukan (atau pecahan itu sendiri, yaitu
1/2
). - Output harus dipesan naik sesuai dengan nilai penyebut (turun dengan nilai fraksi).
- Output dapat dibatasi dengan cara apa pun yang Anda inginkan, tetapi harus ada beberapa karakter di antara untuk membedakan satu nilai dari yang berikutnya.
- Ini kode golf, jadi solusi terpendek menang.
Exmaples:
Input 1:
43, 48
Output 1:
2, 3, 16
Input 2:
8/11
Output 2:
1/2 1/6 1/22 1/66
Input 3:
5 121
Output 3:
33 121 363
code-golf
math
rational-numbers
Gaffi
sumber
sumber
8, 11
dan2, 6, 22, 66
benar?1/2 1/6 1/22 1/66
akan lebih disukai1/2 1/5 1/37 1/4070
untuk input8/11
.5/121 = 1/33+1/121+1/363
pada kasus uji. Semua program serakah (termasuk program saya) memberikan 5 fraksi untuk itu. Contoh diambil dari Wikipedia .Jawaban:
Lisp umum, 137 karakter
(z 43/48) -> (2 3 16)
(z 8/11) -> (2 5 37 4070)
(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)
Tidak perlu khawatir tentang jumlah besar, atau menangani notasi fraksional!
sumber
Python 2,
169167 karakterMengambil args yang dipisahkan koma pada stdin dan mencetak daftar python di stdout.
sumber
PHP 82 byte
Ini bisa dibuat lebih pendek, tetapi pembilang dan penyebut saat ini harus dijaga sebagai bilangan bulat untuk menghindari kesalahan pembulatan titik mengambang (alih-alih menjaga fraksi saat ini).
Penggunaan sampel:
sumber
5 121
atau31 311
, itu akan memberikan jawaban yang salah (setelah waktu yang sangat lama).C,
163177 karakter6/6 : Akhirnya, program sekarang menangani pemotongan dengan benar dalam semua kasus. Butuh lebih banyak karakter daripada yang saya harapkan, tetapi itu sepadan. Program harus 100% mematuhi persyaratan masalah sekarang.
Program mengambil pembilang dan penyebut pada input standar. Penyebut dicetak ke output standar, satu per baris. Output terpotong ditandai dengan mencetak nol penyebut di akhir daftar:
Penyebut dalam contoh kedua berjumlah 95485142815/107645519046, yang berbeda dari 6745/7604 dengan kira-kira 1e-14.
sumber
31 311
misalnya).31 311
meluap, tetapi program gagal menandainya.Python, 61 karakter
Input dari STDIN, dipisahkan koma.
Output ke STDOUT, baris baru dipisahkan.
Tidak selalu mengembalikan representasi terpendek (mis. Untuk 5/121).
Karakter dihitung tanpa baris baru yang tidak diperlukan (yaitu, menggabungkan semua garis dalam
while
penggunaan;
).Fraksi adalah
a/b
.i
adalahb/a
dibulatkan, jadi aku tahu1/i <= a/b
.Setelah mencetak
1/i
, saya gantia/b
dengana/b - 1/i
, yaitu(a*i-b)/(i*b)
.sumber
C, 94 byte
Cobalah secara Online
sunting: Versi kode yang lebih pendek telah diposting di komentar jadi saya menggantinya. Terima kasih!
sumber
for(i=2;n>0&&i>0;i++)
bisafor(i=1;n>0&++i>0;)
; kurung for-loop dapat dihapus (karena hanya memiliki bagianif
dalam);d=d*i;
bisad*=i;
; dan saya tidak sepenuhnya yakin, tapi saya pikir#include <stdio.h>
bisa tanpa spasi:#include<stdio.h>
. Oh, dan mungkin menarik untuk membaca Tip untuk bermain golf di C dan Tips untuk bermain golf di <semua bahasa>Stax , 18 byte
Jalankan dan debug itu
Pada setiap langkah, ia mencoba untuk meminimalkan pembilang berikutnya . Tampaknya berhasil, tetapi saya tidak dapat membuktikannya.
sumber
AXIOM, 753 byte
Idenya akan menerapkan "Greedy Algorithm" dengan poin awal yang berbeda, dan menyimpan daftar yang memiliki panjang minimum. Tetapi tidak selalu akan menemukan solusi min dengan kurang difined: "array A akan kurang dari array B jika dan hanya jika A memiliki beberapa elemen B, atau jika jumlah elemen A sama dengan jumlah elemen B , dari A lebih kecil dari B jika elemen A yang lebih kecil lebih besar daripada angka, daripada elemen B "yang lebih kecil. Tidak disatukan dan diuji
referensi dan nomor dari: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html
untuk menambahkan sesuatu, ini di bawah ini akan menjadi yang dioptimalkan untuk mencari fraksi panjang min yang memiliki penyebut maks kurang (dan tidak dioptimalkan untuk lengh)
hasil:
Tampaknya banyak penyebut yang baik sebagai pembagi faktor dari penyebut fraksi input.
sumber
C,
8578 byteDitingkatkan oleh @ceilingcat , 78 byte:
Cobalah online!
Jawaban asli saya, 85 byte:
Cobalah online!
Bagian dari kredit harus pergi ke Jonathan Frech , yang menulis ini solusi 94 byte yang saya diperbaiki.
sumber
APL (NARS), 2502 byte
Traslation dari kode AXIOM untuk masalah ini, ke APL, menggunakan untuk pertama kalinya (untuk saya) tipe fraksi (yaitu bignum ...).
103r233 berarti fraksi 103/233. Uji:
sumber