Artikel ini menjelaskan algoritma Java untuk menyelesaikan pembagi umum terbesar dari dua bilangan bulat non-negatif. Bagikan untuk referensi Anda, sebagai berikut:
Fungsi Kode:
1. Implementasi Java (kode sumber penuh dengan kasus uji);
2. Selesaikan pembagi umum terbesar dari dua bilangan bulat non-negatif P dan Q (p> = q);
3. Dua solusi: metode loop dan metode rekursif;
Kode Sumber Lengkap:
/ * GCD: Greateast Common Divisor */kelas publik GCD {public static void main (string args []) {/ * test case */int p = 32; int q = 24; System.out.println ("Divisior terhebat"+P+"dan"+Q+"IS /N"+"[GCD1]:"+GCD1 (p, q)+" /n"+"[gcd2]:"+gcd2 (p, q)); } // (q % gcd == 0 dan p % gcd == 0 [gcd dari q ke 1]) public static int gcd1 (int p, int q) {int gcd = 1; int d = q; while (d> 0) {d--; if (q%d == 0 && p%d == 0) {gcd = d; merusak; }} return GCD; } // gcd (p, q) = gcd (q, p%q) [if q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) return p; int r = p%q; //System.out.println("("+q+","+r+ ")"); return gcd2 (q, r); }}Menjalankan tangkapan layar:
Penjelasan Kode:
Metode melingkar GCD1 (P, Q)
Deskripsi Bahasa Alami: Loop Metode memecahkan pembagi umum terbesar dari dua bilangan bulat non-negatif P, q (p> = q), yaitu, memecahkan nilai maksimum pembagi umum Q yaitu p. Biarkan penurunan D (dibagi) dari P (langkah penurunan = 1) D selalu "nilai maksimum dari kondisi yang akan dipenuhi". Ketika D memenuhi syarat (dapat dibagi dengan p dan dibagi dengan p), D adalah pembagi umum p dan q, dan d adalah pembagi umum terbesar dari p dan q;
Metode Rekursif GCD2 (P, Q)
Deskripsi Bahasa Alami: Metode rekursif memecahkan pembagi umum terbesar dari dua bilangan bulat non-negatif P, q (p> = q). Ketika Q sama dengan 0, pembagi umum terbesar adalah P; Kalau tidak, ambil sisa P dan Q untuk mendapatkan r = p%q, dan pembagi umum terbesar dari p dan q adalah pembagi umum terbesar dari q dan r;
Pengalaman Kode:
Mengenai metode loop, pada awalnya, yang saya pikirkan adalah menulis metode untuk menyelesaikan pembagi umum, menggunakan array integer untuk menyimpan semua pembagi umum dari bilangan bulat non-negatif, dan kemudian membandingkan dan mencari tahu pembagi umum terbesar yang umum di P dan Q, yang merupakan pembagi umum terbesar dari dua angka. Kemudian, saya pikir, karena itu untuk menemukan maksimum, bukankah lebih mudah untuk secara langsung berkurang dari belakang ke depan? Mengurangi dari belakang ke depan dapat memastikan bahwa jumlah ini selalu yang terbesar saat ini, karena orang yang lebih besar daripada tidak memenuhi persyaratan (dapat dibagi dengan P dan Q pada saat yang sama) dihilangkan, yang menghindari kesulitan menemukan maksimum pada awalnya. Meskipun ada banyak cara untuk menemukan yang maksimal, jika Anda memiliki atau tidak perlu membuktikan dan mencari, haha, mengapa Anda merasa sedikit tentang filsafat?
Mengenai rekursi, apa yang dapat saya pahami sepenuhnya berdasarkan intuisi saya adalah satu -satunya kalimat bahwa pembagi umum terbesar dari P dan Q adalah pembagi umum terbesar dari Q dan R (r = p%q), yang merupakan awal dari cincin, tetapi saya masih tidak cukup mengerti bahwa kondisi akhir cincin adalah 0, dan mengembalikan P;
Meskipun ini adalah solusi yang sangat sederhana untuk algoritma pembagi umum terbesar, saya harus menulisnya dalam dua cara, terutama untuk merasakan metode rekursi yang tidak saya kenal. Di masa lalu, saya melihat formula yang jelas dari algoritma rekursi untuk menyelesaikan menara Hannover dan angka fibonacci yang diterangi di sana, dan saya menghela nafas bahwa ini benar -benar matematika! Perasaan yang saya pelajari hari ini bahkan lebih mengejutkan daripada saat itu. Saya bertanya -tanya apa yang terjadi dan menyelesaikannya dengan aneh. Pada saat itu, saya tidak terlalu peduli dengan memori, efisiensi, dan indikator lainnya. Saya hanya berpikir bahwa orang -orang yang bisa memikirkan ini sangat pintar. Bagi mereka, apakah itu komputer atau bahasa pemrograman, itu hanya alat untuk menyelesaikan masalah. Beberapa orang mengatakan bahwa rekursi adalah algoritma yang memungkinkan otak untuk berpikir tentang komputer untuk menghitung, dan rasanya sangat tepat.
Referensi
Seri Pemrograman Turing: Algoritma (Edisi ke -4) Robert Sedgewick (penulis), Kevin Wayne (penulis), Xie Luyun (penerjemah)
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.