Baca tanpa iklan
TRIBUNNEWS.COM - Simak kunci jawaban Informatika kelas 11 halaman 42 Kurikulum Merdeka dalam artikel berikut ini.
Mata pelajaran Informatika kali ini membahas Bab 2: Strategi Algoritmik dan Pemrograman.
Kunci jawaban Informatika Kelas 11 Kurikulum Merdeka dalam artikel ini bisa menjadi referensi atau panduan siswa dalam belajar.
Kunci jawaban Informatika Kelas 11 Halaman 42
Baca juga: Kunci Jawaban Pendidikan Pancasila Kelas 12 Halaman 76 Kurikulum Merdeka Bab 3: Aktivitas 3.2
Bab 2 Tentang Informatika Strategi Algoritmik dan Pemrograman : Ayo Berlatih
Ani dan Budi sedang bermain dengan sebuah permainan angka: pertama Ani akan memilih sebuah angka bilangan bulat positif n. Selanjutnya, Budi harus mengubah bilangan n ini menjadi angka 1 dengan menerapkan serangkaian langkah sebagai berikut:
1. Budi boleh mengganti bilangan n dengan n - 1.
2. Jika bilangan saat ini adalah genap (habis dibagi 2), maka Budi boleh menggantinya dengan n/2.
3. Jika bilangan saat ini habis dibagi 3, maka Budi boleh menggantinya dengan n/3.
Proses ini harus dilakukan oleh Budi secara terus menerus sampai bilangan yang dimilikinya menjadi 1. Misalnya, jika Ani memilih n = 5, maka Budi dapat melakukan proses mengubah 5 menjadi 1 sebagai berikut: 5 > 4 > 2 > 1 (dalam tiga langkah).
Tentukan, berapakah jumlah langkah minimum yang diperlukan, jika Ani memilih n = 25?
Kunci Jawaban
Asumsikan jumlah langkah yang diperlukan untuk mengubah sebuah bilangan n menjadi 1, sesuai dengan ketentuan pada soal, dinyatakan sebagai barisan L(n).
Jawaban yang ingin dihitung adalah L(25). Pertama-tama, perlu dipahami terlebih dahulu bahwa algoritma greedy disini juga tidak selalu menghasilkan nilai yang optimal.
Misalnya, jika n = 10, maka dengan menerapkan algoritma greedy, kita akan cenderung untuk menerapkan langkah pembagian dengan 2 terlebih dahulu (karena 10 genap dan tidak habis dibagi 3). Dengan cara ini kita akan memerlukan 4 langkah, yaitu 10→5→4→2→1.
Namun ternyata ada cara yang lebih singkat, yaitu 10→9→3→1 (3 langkah), sehingga L(10) = 3.
Ini berarti kita harus memperhatikan semua kemungkinan jalur yang ada untuk mencapai 1, dan mencari yang terpendek.
Namun, jika kita mencoba semua kemungkinan, akan banyak sekali kemungkinan nilai yang berulang yang harus kita hindari supaya tidak dihitung lebih dari sekali (seperti pada kasus menghitung bilangan Fibonacci).
Misalnya, saat menghitung L(25), kita bisa menggunakan jalur langkah:
25 → 24 → 8 → 4 →…
Atau
25 → 24 →12 → 4 → …
Sehingga nilai L(4) dapat dihitung beberapa kali. Ini yang harus dihindari pada penyelesaian soal dengan teknik DP, yaitu dengan menggunakan tabel memoisasi. Dengan tabel memoisasi, kita dapat menyimpan nilai L yang sudah dihitung dan menggunakannya untuk menghitung nilai-nilai L yang lebih besar.
Berikut ini adalah langkah-langkah yang kita lakukan:
Pertama, simpan nilai L(1) = 0 (tidak perlu melakukan apa-apa).
Untuk setiap nilai n selanjutnya, ambil 3 buah nilai:
● A = L(n – 1) dari tabel memoisasi.
● Jika n habis dibagi 2, ambil nilai B = L(n/2) dari tabel memoisasi.
● Jika n habis dibagi 2, catat pula C = L(n/3) dari tabel memoisasi
Kemudian, ambil nilai terkecil dari A, B dan C. Misalkan hasilnya adalah D.
Maka, selanjutnya, isikan pada tabel memoisasi, nilai L(n) = D + 1.
Perhatikan bahwa untuk setiap nilai n, berlaku bahwa n – 1, n/2 (jika n habis dibagi 2) dan n/3 (jika n habis dibagi 3) adalah bilangan bulat positif yang lebih kecil dari n. Dengan demikian, kita yakin bahwa jika kita membangun tabel memoisasi ini dari bawah (bottom up), maka nilai A, B dan C pada langkah 2, 3 dan 4 di atas pasti sudah tersedia/terisi sebelumnya, sehingga tidak perlu kita hitung lagi.
Berikut ini adalah hasil tabel memoisasi yang dibangun dengan cara di
atas (sampai n = 25). Dari tabel tersebut, dapat disimpulkan bahwa jawaban
dari soal tersebut adalah L(25) = 5.
Disclaimer:
- Kunci jawaban Informatika di atas hanya digunakan oleh orang tua atau wali untuk memandu proses belajar anak.
- Sebelum melihat kunci jawaban, pastikan anak mengerjakan sendiri terlebih dahulu.
(Tribunnews.com/Rinanda)