Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 6
Diberikan sebuah fungsi F(x) = 1 - 2x - 3x2 - 4x3 dengan x bilangan bulat dimulai dari 1 sampai dengan 30. Berapakah x yang memenuhi F(x) = -20552?
Petunjuk: semakin besar nilai x, maka semakin kecil nilai F(x).
5 jawaban
Mamat Rahmat11 tahun lalu
TOKI 2012, IF ITB 2012. http://olimpiadeinformatika.com
12
Cara biasa yang tercepat adalah dengan menggunakan binary search (berdasarkan petunjuk f monoton turun di selang 1<=x<=30)
Algoritma bekerja dengan mencoba titik tengah selang. Jika hasil fungsi di titik tengah lebih besar dari -20552, maka pencarian dikurangi menjadi selang kanan. Sebaliknya jika hasil fungsi di titik tengah lebih kecil dari -20552, maka pencarian dikurangi menjadi selang kiri.
Selang pencarian 1<=x<=30, titik tengah = (1+30) div 2 = 15
f(15) = 1 - 2(15) - 3(15)2 - 4(15)3 = -14204
Karena -14204 > -20552 pencarian diperkecil menjadi selang 16<= x <=30
Selang pencarian 16<=x<=30, titik tengah = (16+30) div 2 = 23
f(23) = 1 - 2(23) - 3(23)2 - 4(23)3 = -50300
Karena -14204 < -20552 pencarian diperkecil menjadi selang 16 <= x <= 22
Selang pencarian 16<=x<=22, titik tengah = (16+22) div 2 = 19
f(19) = 1 - 2(19) - 3(19)2 - 4(19)3 = -28556.
Karena -28556 < -20552 pencarian diperkecil menjadi selang 16 <= x <= 8
Selang pencarian 16<=x<=18, titik tengah = (16+18) div 2 = 17
f(17) = 1 - 2(17) - 3(17)2 - 4(17)3 = -20552.
Diperoleh x yang memenuhi adalah 17
Ezra Anugerah Bangun11 tahun lalu
1
Dengan cara di atas benar, yaitu dengan menggunakan titik tengah, namun ketika sudah kecil rangenya, bisa dengan cara mencari angka satuannya saja agar mudah
Masuk untuk menulis jawaban
penjelasannya banyak yang salah ketik tuh