Kami memiliki angka floating point r
antara 0 dan 1, dan bilangan bulat p
.
Temukan fraksi bilangan bulat dengan penyebut terkecil, yang mendekati r
dengan setidaknya p
-digit presisi.
- Input:
r
(angka floating point) danp
(integer). - Output:
a
danb
bilangan bulat, di manaa/b
(as float) mendekatir
hinggap
digit.b
adalah bilangan bulat positif terkecil yang mungkin.
Sebagai contoh:
- jika
r=0.14159265358979
danp=9
, - maka hasilnya adalah
a=4687
danb=33102
, - karena
4687/33102=0.1415926530119026
.
Setiap solusi harus bekerja secara teori dengan tipe presisi arbitrer, tetapi batasan yang disebabkan oleh tipe presisi tetap implementasi tidak menjadi masalah.
Presisi berarti jumlah digit setelah " 0.
" dalam r
. Jadi, jika r=0.0123
dan p=3
, maka a/b
harus dimulai dengan 0.012
. Jika p
digit pertama dari bagian fraksional r
adalah 0, perilaku tidak terdefinisi dapat diterima.
Kriteria menang:
- Algoritme tercepat secara algoritmik menang. Kecepatan diukur dalam O (p).
- Jika ada beberapa algoritma tercepat, maka yang paling pendek menang.
- Jawaban saya sendiri dikecualikan dari himpunan pemenang yang mungkin.
Ps bagian matematika sebenarnya jauh lebih mudah seperti yang terlihat, saya sarankan untuk membaca posting ini .
sumber
padEnd
danmatch
? Tidak bisakah Anda hanyaslice
setiap string dengan panjang yang benar dan kemudian kurangi?padEnd
digunakan untuk testcasef(0.001,2)
danf(0.3,2)
.(r,p)=>{for(a=0,b=1;`${a/b}`.slice(0,p+2)-`${r}`.slice(0,p+2);a/b<r?a++:b++);return[a,b]}
(tidak sepenuhnya golf).Haskell , O (10 p ) dalam kasus terburuk
121119 byteCobalah online!
Disimpan 2 byte berkat Laikoni
Saya menggunakan algoritma dari /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .
Pada setiap langkah, interval baru adalah setengah dari interval sebelumnya. Jadi, ukuran intervalnya adalah
2**-n
, di manan
langkahnya saat ini. Kapan2**-n < 10**-p
, kami yakin memiliki perkiraan yang tepat. Namun jikan > 4*p
demikian2**-n < 2**-(4*p) == 16**-p < 10**-p
. Kesimpulannya adalah bahwa algoritma tersebutO(p)
.EDIT Seperti yang ditunjukkan oleh orlp dalam komentar, klaim di atas salah. Dalam kasus terburuk,
r = 1/10**p
(r= 1-1/10**p
mirip), akan ada10**p
langkah-langkah:1/2, 1/3, 1/4, ...
. Ada solusi yang lebih baik, tetapi saya tidak punya waktu sekarang untuk memperbaikinya.sumber
f=
dan menyimpan dua byte denganz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
TIO dalam kode Haskell.-cpp
flag kompiler dan menulisf=\
di header: Coba online!C, 473 byte (tanpa konteks), O (p), tidak bersaing
Solusi ini menggunakan bagian matematika yang diperinci dalam pos yang luar biasa ini . Saya menghitung hanya
calc()
ke dalam ukuran jawaban.sumber