Kunci Jawaban Informatika Kelas 11 Halaman 42 Kurikulum Merdeka: Strategi Algoritmik dan Pemrograman

AKURAT.CO Kunci jawaban Informatika untuk kelas 11 pada halaman 42 Kurikulum Merdeka akan dibahas dalam artikel ini.

Dalam Bab 2, buku tersebut membahas tentang Strategi Algoritmik dan Pemrograman.

Namun, kunci jawaban Informatika Kelas 11 Kurikulum Merdeka dalam artikel ini hanya digunakan sebagai referensi atau panduan siswa dalam belajar.  

Kunci jawaban Informatika Kelas 11 Halaman 42

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:

Artikel ini hanya boleh digunakan sebagai bahan referensi siswa ketika mengerjakan soal. Sebelum melihat kunci jawaban ini siswa diharuskan untuk mengerjakannya secara mandiri.