Diberikan: 12 koin, salah satunya palsu, beratnya hanya berbeda. Tidak diketahui lebih ringan atau lebih berat. Timbangan leverage diberikan yang menunjukkan bahwa beban di satu sisi lebih berat. Untuk 3 penimbangan, Anda perlu menemukan koin palsu.
Dari pengalaman, saya menyarankan Anda untuk tidak terburu-buru, untuk memutuskan secara tertulis. Teka-teki "12 koin, 3 berat" muncul beberapa kali dalam hidup saya. Pertama kali teman saya bertanya kepada saya, dia memutuskan setelah Olimpiade dan saya harus mematahkan kepala selama beberapa jam. Dan beberapa tahun kemudian itu tidak diberikan kepada saya segera. Jika Anda ingin memutuskan sendiri - lakukan di selembar kertas.
Di bawah ini akan menjadi analisis dan tahapan solusi. Tahapan akan dilakukan sesuai dengan metodologi universal untuk memecahkan masalah, yang berlaku baik untuk pemrograman dan kehidupan. Dengan pendekatan itu, memecahkan teka-teki akan mudah.
Saya sarankan Anda, sebelum membaca, menawarkan solusi. Apakah Anda punya jawaban? Terverifikasi?
Jika itu perangkat lunak, pertanyaannya adalah: “Sudahkah Anda memprogram, menguji algoritme? Sudahkah Anda memeriksa test case dan memeriksanya? ”
Seperti yang ditunjukkan pengalaman, untuk menyelesaikannya diperlukan menggambar pohon keputusan dan memeriksa semua 12 kasus.
1. TipsDalam proses penyelesaiannya akan membantu:1) Penurunan entropi (ukuran ketidakpastian) dan jawaban atas pertanyaan:
- Apa yang Anda pelajari di langkah sebelumnya?
- Apa yang mengurangi ketidakpastian?
- Informasi apa yang kami miliki?
- Apa lagi yang perlu Anda ketahui?
Pertanyaan cocok untuk tugas apa pun, proyek. Jawaban untuk mereka membantu dalam mengurangi risiko kegagalan memenuhi tenggat waktu, pembengkakan anggaran, dan mengejar ketinggalan dari atasan.
2) Dekomposisi. Pendekatannya dari yang sederhana sampai yang kompleks. Jika Anda menyiapkan solusi untuk kasus yang paling sederhana, kemudian menggunakannya untuk menyelesaikan masalah (bagi dan taklukkan algoritma), itu akan lebih mudah daripada mewakili seluruh situasi di kepala Anda.
Algoritma membagi dan menaklukkan memecah tugas menjadi dua atau lebih subtugas dari jenis yang sama, tetapi lebih kecil untuk tugas-tugas dasar, dan menggabungkan solusi mereka untuk mendapatkan jawaban atas masalah aslinya.Tulis pertanyaan untuk dekomposisi. Mana yang akan Anda sarankan?
2. PenguraianPertanyaan apa yang Anda rumuskan untuk dekomposisi? Adakah yang cocok?
1) Apa situasi yang paling mendasar? Apa yang bisa kita lakukan dalam penimbangan?
Untuk satu penimbangan, kita dapat menentukan koin mana yang lebih berat, apakah berat koinnya sama.
2) Jika kita memiliki 2 koin, dan, seperti yang Anda tahu, palsu lebih sulit atau lebih ringan. Bagaimana cara menentukan palsu dalam satu penimbangan?
Penting untuk menimbang koin, dan tergantung pada panah timbangan, tentukan yang palsu.
3) Jika kita memiliki 2 koin, dan, tidak diketahui, uang palsu lebih sulit atau lebih mudah, bagaimana kita dapat menentukan uang palsu dalam satu berat?
Setelah menimbang, salah satu dari 2 koin yang disajikan dengan koin ketiga, yang diketahui asli.
4) Jika kita memiliki 3 koin, dan, seperti yang Anda tahu, palsu lebih sulit atau lebih ringan. Bagaimana cara menentukan palsu dalam satu penimbangan?
Penting untuk membandingkan dua dari koin-koin ini, jika mereka sama, koin ketiga salah.
5) Jika kita memiliki 3 koin, dan, tidak diketahui, palsu lebih sulit atau lebih mudah. Apakah mungkin menentukan palsu dalam berat satu?
Sayangnya tidak.
6) Jika kita memiliki 4 koin, dan palsu yang tidak diketahui lebih sulit atau lebih ringan, dapatkah kita menentukan palsu dalam satu penimbangan?
Sayangnya tidak.
7) Jika kita memiliki 4 koin, dan, tidak diketahui, palsu lebih sulit atau lebih ringan, berapa berat yang dapat Anda tentukan palsu?
Untuk dua penimbangan.
Selanjutnya, dari kasus dasar, kami mengumpulkan situasi 8, 9, 10, 11, dan 12 koin. Bagaimana Anda melihat solusinya?
Di bawah ini adalah solusi lengkap.
3. KeputusanLangkah pertama: bagi koin menjadi 3 kelompok 4: 1 2 3 4, 5 6 7 8, 9 10 11 12.
Bandingkan dua kelompok pertama. Ada tiga opsi yang mungkin:
- kelompok pertama lebih berat;
- kelompok kedua lebih berat;
- sama.
1) Jika kelompoknya sama, maka koin palsu ada di kelompok ketiga. Hal ini diperlukan untuk menemukan koin palsu dari 4 koin dalam dua penimbangan.
Bagilah kelompok ketiga menjadi dua: 9 10 11 12
Bandingkan 9 dan 10:
- jika mereka sama, maka koin palsu dalam kelompok kedua - bandingkan 9 dan 11. Jika 9 dan 11 sama, maka palsu - 12, jika tidak -11
- jika mereka tidak sama, maka salah dalam kelompok pertama - bandingkan 10 dan 12. Jika 10 dan 12 sama - salah - 9, jika tidak - 10.
Jadi kami menemukan koin palsu.
2) Pertimbangkan kasus kedua. Jika grup pertama lebih berat dari yang kedua, maka kami menetapkan grup pertama tanda ">", grup kedua tanda "<", grup ketiga - "0".
Kami membagi koin menjadi kelompok-kelompok 1 9 10 11 dan 5 2 3 4, ditimbang. Ada tiga opsi yang mungkin:
- Sama. Koin palsu ada di antara angka: 6 7 8. Bandingkan 6 dan 7, jika sama, koin palsu 8, jika 6 lebih besar, palsu - 7, jika 7 lebih besar, palsu - 6, karena dalam kasus ini koin palsu lebih mudah.
- Kelompok pertama lebih berat, maka koin palsu adalah 1 atau 5. Bandingkan 1 dan 9 jika mereka sama - koin palsu - 5, jika tidak - 1.
- Kelompok pertama lebih mudah, kemudian palsu di antara koin 2 3 4, karena diketahui bahwa 9, 10 dan 11 adalah nyata, dan kelompok kedua dapat dikalahkan hanya dengan koin 2, 3 dan 4. Bandingkan 2 dan 3, jika mereka sama, palsu 4, jika 2 lebih berat, maka palsu 2, jika tidak 3 palsu.
3) Kasus ketika kelompok kedua lebih berat dari yang pertama mirip dengan yang kedua.
Diagram umum dari Pohon Keputusan disajikan di bawah ini.
KesimpulanKetika tugas tiba untuk revisi atau debugging, ada baiknya menerapkan pendekatan di atas:
- Putuskan apa yang diberikan?
- Kasus / tugas dasar apa yang dapat diurai?
- Apa yang tidak diketahui untuk menyelesaikan masalah? Eksperimen apa yang perlu dilakukan untuk mengurangi entropi?
- Lari.
- Apakah masalah terpecahkan? Tidak Kembali ke langkah 1.
Solusi yang berhasil.