Untuk ulang tahun pak Dengklek, ibu Dengklek membuat kue yang dibubuhi dengan 8 macam zat pelezat. Ternyata, setelah dibakar, kuenya berwarna hijau. Walaupun demikian, para tamu mengatakan bahwa kue itu sangat enak. Bu Dengklek ingin membuat kue itu lagi, namun tak ingin warnanya hijau, dengan mengkombinasikan zat pelezat yang akan dicampurkan. Setelah melakukan konsultasi ke bu Ganesh, ternyata hanya salah satu zat pelezat yang menyebabkan warna kuenya hijau. Berapa kali usaha minimal terburuk pemilihan kombinasi yang harus dicoba bu Denglek hingga bisa diketahui zat yang menyebabkan kuenya berwarna hijau.
a. 2 b. 3 c. 5 d. 7 e. 8
Persoalan ini dapat diselesaikan dengan menggunakan Binary Search
Pertama-tama, dari 8 pelezat tersebut, kita kombinasikan 4 buah pelezat. ( 1x usaha )
- Jika yang kita kombinasikan tadi menghasilkan kue berwarna hijau, bagi lagi 4 buah pelezat tersebut menjadi 2 bagian sama banyak.
- Jika yang kita kombinasikan tadi tidak menghasilkan kue berwarna hijau, ambil 4 buah pelezat yang tidak dikombinasikan, dan bagi lagi menjadi 2 bagian sama banyak.
Lalu, dari 4 Pelezat yang kita bagi menjadi 2 bagian sama banyak tadi, ambil salah satu bagian ( Yaitu 2 buat pelezat) lalu kombinasikan lagi. ( 2x usaha )
-Lakukan pemilihan seperti cara tadi
Sehingga tersisalah 2 Pelezat. lalu pilih salah satu untuk dijadikan kue. ( 3 x usaha )
-Jika kue tersebut berwarna hijau. zat pelezat tersebutlah yang kita cari.
-Jika kue tersebut tak berwana hijau. berarti zat pelezat sebaliknya lah yang kita cari.
Jadi, usaha minimal untuk mengetahui zat penyebab kue berwarna hijau adalah 3x Usaha (B)
Masuk untuk menulis jawaban