Isi
tampilkan
KSN-K 2021
Pak Dengklek memiliki 5 buah apel dengan bobot yang berbeda dan sebuah timbangan 2 lengan. Apabila 2 buah apel berbeda diletakkan di timbangan tersebut, dapat diketahui apel mana yang lebih berat. Berapa minimal banyaknya penimbangan yang harus dilakukan agar dapat diketahui secara pasti urutan bobot apel mulai dari yang terberat hingga teringan?
Jawabanya: 8 penimbangan
Ulasan:
Masalah ini bisa dituntaskan dengan memakai algoritme sorting, lebih persisnya ialah merge sort. Dengan algoritme ini, array akan dipisah jadi bagian-bagian sampai berpasangan. Contoh 5 apel (a-b-c-d-e) maka jadi a-b, c-d dan e. Karena itu bandingkan lebih dulu a-b dan c-d (2 perbedaan) dan tetapkan posisi kecil besarnya. Misalnya ab, cd.
Soal Lainya:
- Berapa banyak cara memasang 8 ubin
- Seekor semut berada di bidang dimensi dua
- Pak dengklek mempunyai 3 jenis ubin
- Basa rinengga, dumadi telung warna, yaikua.
- Pisah array jadi bagian-bagian, contoh apel a-b-c-d-e jadi a-b, c-d dan e.
- Bandingkan masing-masing sisi dan urutkan kecil besarnya. Contoh a lebih berat dari b dan c lebih berat dari d (ab, cd). [2 perbandingan]
- Bandingkan apel paling akhir dengan salah satunya sisi, contoh dengan cd. Untuk memperoleh hasil yang jelas, pakai worst case skenario di mana c dibanding dengan e dan d dengan
- e (kasus di mana c lebih berat dari e). Hingga sisi ke-2 jadi cde. [2 perbandingan]
- Satukan ke-2 sisi dengan lakukan perbedaan. Contoh: a dengan c dan c lebih berat. Sampai sisa [c], ab, de. [1 perbandingan]
- Bandingkan a dengan d dan a lebih berat. Sampai [ca], b, de. [1 perbandingan]
- Bandingkan b dengan d dan d lebih berat. Sampai [cad], b, e. [1 perbandingan]
- Bandingkan 2 apel paling akhir, hingga keseluruhan perbedaan ialah 8 penimbangan.
