Saya mencoba untuk menemukan algoritma yang efisien di Jawa untuk menemukan bagian desimal berulang dari dua bilangan bulat a
dan di b
mana a/b
.
misalnya. 5/7 = 0.714258 714258 ....
Saat ini saya hanya tahu metode pembagian panjang.
algorithms
math
Jun Hao
sumber
sumber
Jawaban:
Saya percaya bahwa ada dua pendekatan umum di sini, Anda pada dasarnya dapat "brute force" mencari string berulang berulang, atau Anda dapat menyelesaikannya sebagai masalah teori bilangan.
Sudah lama sejak saya menemukan masalah ini, tetapi kasus khusus (1 / n) adalah masalah # 26 di Project Euler, jadi Anda mungkin dapat menemukan informasi lebih lanjut dengan mencari solusi efisien untuk nama spesifik tersebut. Satu pencarian membawa kita ke situs web Eli Bendersky, tempat dia menjelaskan solusinya . Berikut beberapa teori dari halaman Desimal Ekspansi Mathworld :
Teori bilangan saya agak berkarat saat ini, jadi yang terbaik yang bisa saya lakukan adalah mengarahkan Anda ke arah itu.
sumber
Biarkan
n < d
, dan Anda mencoba mencari tahu bagian yang berulangn/d
. Membiarkanp
menjadi jumlah digit di bagian berulang: lalun/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...)
. Bagian kurung adalah deret geometris, sama dengan1/(10^p - 1)
.Jadi
n / d = R / (10^p - 1)
. Atur ulang untuk mendapatkanR = n * (10^p - 1) / d
. Untuk menemukan R, loopp
dari 1 hingga tak terbatas, dan berhenti segera setelahd
membagi secara meratan * (10^p - 1)
.Berikut ini adalah implementasi dengan Python:
(
k
melacak panjang urutan berulang, sehingga Anda dapat membedakan antara 1/9 dan 1/99, misalnya)Perhatikan bahwa implementasi ini (ironisnya) berulang selamanya jika ekspansi desimal terbatas, tetapi berakhir jika tidak terbatas! Anda dapat memeriksa kasus ini, karena
n/d
hanya akan memiliki representasi desimal terbatas jika semua faktor primad
yang bukan 2 atau 5 juga adan
.sumber
0.123123... = 123/999
0.714258714258... = 714258/999999 (=5/7)
dll.Divisi panjang? : /
Ubah hasilnya menjadi string, dan kemudian terapkan algoritma ini ke sana. Gunakan BigDecimal jika string Anda tidak cukup panjang dengan tipe biasa.
sumber