Pengenalan algoritma modulus daya cepat diusulkan oleh keterbatasan algoritma naif yang mengambil modulus dari desimal dalam jumlah besar. Dalam metode naif, kami menghitung angka seperti 5^1003%31, yang sangat menghabiskan sumber daya komputasi kami. Hal yang paling merepotkan dalam seluruh proses perhitungan adalah proses 5^1003 kami.
Kerugian 1: Dalam proses menghitung indeks nanti, angka yang dihitung tidak semuanya meningkat, yang memakan banyak sumber daya komputasi kami (terutama waktu, dan ruang)
Kerugian 2: Angka -angka dalam perhitungan kami sangat besar sehingga komputer kami yang ada tidak dapat merekam data panjang seperti itu, jadi kami harus memikirkan cara yang lebih efisien untuk menyelesaikan masalah ini.
Ketika kami menghitung AB%C, cara yang paling nyaman adalah dengan memanggil metode POW dalam fungsi matematika. Namun, kadang-kadang jumlah A ke kekuatan B terlalu besar, dan bahkan double-presisi ganda akan meluap. Pada saat ini, untuk mendapatkan hasil AB%C, kami akan memilih untuk menggunakan algoritma modulus daya cepat untuk mendapatkan hasil yang kami inginkan secara sederhana dan cepat.
Untuk mencegah angka meluap dan mengurangi kompleksitas, kita perlu menggunakan formula berikut:
ABMOD C = (A MOD C) BMOD C
Arti formula ini adalah: Produk mengambil sisa yang sama dengan produk mengambil sisanya. Sangat mudah untuk melihat bahwa formula ini transitif, sehingga kita dapat membuat yang lebih kecil dan lebih kecil dengan terus mengambil sisanya untuk mencegah luapan.
Secara teoritis, dengan formula ini, kita dapat menulis kode. Dengan terus memodulo A, kami memastikan bahwa hasilnya tidak akan meluap. Ini memang dapat menghitung modulus kekuatan ke kekuatan yang lebih besar, tetapi kompleksitas metode ini masih o (n) dan tidak cepat.
Untuk menghitung modulus kekuatan lebih cepat, kita juga perlu mengandalkan formula berikut:
ab mod c = (a2) b/2 mod C, b adalah angka genap
ab mod c = ((a2) b/2 ・ a) mod C, b adalah angka ganjil
Formula ini sangat sederhana. Prinsipnya adalah untuk terus mengganti B dengan kuadrat A dan mengganti B dengan setengah asli. Karena kita tahu melalui formula pertama bahwa modul angka memiliki kekuatan yang sama (kalimat ini agak membingungkan, yang berarti Formula Satu). Maka efek menggunakan hasil*A%C bukannya A adalah sama.
Jadi menurut rumus di atas, kami mendapatkan metode untuk menghitung daya cepat dengan kompleksitas O (LOGN):
impor java.util.scanner; kelas publik utama {public static void main (string [] args) {scanner in = new scanner (system.in); int a = in.nextInt (), b = in.nextInt (), c = in.nextInt (); int res = 1; a %= c; untuk (; b! = 0; b /= 2) {if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } System.out.println (res); }}Algoritma ini kira -kira seperti ini. Langkah pertama adalah mengurangi%= C untuk mencegah angka meluap ketika A*A dilakukan untuk pertama kalinya. Dalam loop untuk, jika B adalah angka ganjil, biarkan res = res*a, dan kemudian kalikan A ke hasil terlebih dahulu, dan kemudian memprosesnya. Untuk mencegah angka meluap, hasil mod C dari res*A dioperasikan secara langsung. Dalam hal ini untuk loop, cepat atau lambat, B akan sama dengan 1, masukkan cabang IF, dan akhirnya menghitung nilai res dan mod C keluar dari loop for, dan kemudian hasil akhir.
Meringkaskan
Di atas adalah semua penjelasan terperinci dari artikel ini tentang menerapkan algoritma modulus daya cepat bahasa Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!