1. Pendahuluan
Penulis menemukan pertanyaan seperti itu dalam kompetisi algoritma di universitas. Sekarang saya akan membagikannya kepada Anda: ada delapan koin perak ABCDEFGH, dan salah satunya dikenal sebagai mata uang palsu, yang berbeda dari mata uang yang sebenarnya, tetapi saya tidak tahu apakah lebih ringan atau lebih berat. Cara menggunakan saldo untuk memutuskan koin mana yang merupakan mata uang palsu dengan jumlah perbandingan minimum, dan saya juga tahu bahwa mata uang palsu lebih ringan atau lebih berat daripada mata uang yang sebenarnya.
2. Analisis
Jika pertanyaan ini hanya untuk menyelesaikan mata uang palsu mana yang sangat sederhana, masalahnya tidak terlalu rumit, dan Anda hanya perlu kembali dan berulang untuk mendapatkan hasilnya. Kita perlu menggunakan langkah paling sedikit untuk mengatasi kesulitan masalah! Lai Lai
Dibandingkan dengan masalah struktur data sebelumnya, ada rekursi dan backtracking. Hari ini kita mungkin harus bersentuhan dengan konsep baru yang disebut pohon. Seperti namanya, struktur angka berarti bahwa diagram analisis kami seperti pohon, dengan berbagai informasi seperti node cabang. Struktur pohon adalah bab yang lebih besar dalam struktur data, bukan dalam diskusi kami. Dalam pertanyaan ini, kami akan memperkenalkan molekul kecil pohon, pohon keputusan.
Pertama mari kita bangun model matematika untuk memecahkan delapan koin perak. Situasi sederhana adalah seperti ini. Kami menyebutkan koin perak ABCDEFG, dll. Pada gilirannya, kami membandingkan A+B+C dan D+E+F. Jika sama, mata uang palsu harus g atau h. Kami pertama -tama membandingkan mana yang lebih berat, g atau h. Jika G lebih berat, maka bandingkan dengan A (A adalah mata uang nyata). Jika G sama dengan A, G adalah mata uang nyata, maka H adalah mata uang palsu. Karena H lebih ringan dari G dan G adalah mata uang nyata, berat mata uang palsu lebih ringan dari mata uang nyata.
Bagaimana jika itu tidak sama? Apa masalahnya? Kami akan membandingkan cabang secara bergantian sampai kami mendapatkan jawaban akhir!
3. Diagram sampel
Berdasarkan analisis di atas, kita dapat memiliki diagram pohon keputusan lengkap:
4. Kode
koin kelas publik {private int [] koin; koin publik () {koin = int baru [8]; untuk (int i = 0; i <8; i ++) Koin [i] = 10; } public void setFake (int bobot) {koin [(int) (math.random () * 7)] = berat; } public void palsu () {if (koin [0]+koin [1]+koin [2] == koin [3]+koin [4]+koin [5]) {if (koin [6]> koin [7]) bandingkan (6, 7, 0); lain Bandingkan (7, 6, 0); } lain jika (koin [0]+koin [1]+koin [2]> koin [3]+koin [4]+koin [5]) {if (koin [0]+koin [3] == koin [1]+koin [4]) Bandingkan (2, 5, 0); lain jika (koin [0]+koin [3]> koin [1]+koin [4]) Bandingkan (0, 4, 1); if (koin [0]+koin [3] <koin [1]+koin [4]) Bandingkan (1, 3, 0); } lain jika (koin [0]+koin [1]+koin [2] <koin [3]+koin [4]+koin [5]) {if (koin [0]+koin [3] == koin [1]+koin [4]) Bandingkan (5, 2, 0); lain jika (koin [0]+koin [3]> koin [1]+koin [4]) Bandingkan (3, 1, 0); if (koin [0]+koin [3] <koin [1]+koin [4]) Bandingkan (4, 0, 1); }} void protected membandingkan (int i, int j, int k) {if (koin [i]> koin [k]) system.out.print ("/nfake coins" + (i + 1) + "lebih berat"); else system.out.print ("/n mata uang palsu" + (j + 1) + "lebih ringan"); } public static void main (string [] args) {if (args.length == 0) {System.out.println ("Input bobot mata uang palsu (lebih besar atau lebih kecil dari 10)"); System.out.println ("Ex. Java Coins 5"); kembali; } Koin delapancoins = koin baru (); EightCoins.setFake (integer.parseint (args [0])); Eightcoins.fake (); }}hasil:
Masukkan bobot mata uang palsu (lebih besar atau lebih kecil dari 10)
mantan. Koin Java 5
Berikut adalah metode pemecahan masalah umum. Anda dapat dengan hati -hati mempertimbangkan kodenya. Untuk kode ini, analisis di atas sudah cukup. Setiap orang perlu memikirkannya dan mempelajari sisanya sendiri, sehingga mereka dapat memahaminya secara mendalam.
Meringkaskan
Di atas adalah semua konten artikel ini tentang memecahkan delapan kode koin perak untuk implementasi pemrograman 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!