Jawaban Informatika Kelas 11 SMA Halaman 42 Ayo Berlatih Aktivitas Individu Aktivitas SAP-K11-07-U

SRIPOKU.COM - Berikut ini disajikan kunci jawaban Informatika kelas 11 SMA/MA Halaman 42 Ayo Berlatih! Semester 1 Kurikulum Merdeka.

Pada artikel ini, akan menyajikan kunci jawaban serta pembahasan Ayo Berlatih! Aktivitas Individu Aktivitas SAP-K11-07-U Bermain Angka pada Bab 2 Strategi Algoritma dan Pemograman.

Untuk itu, simak kunci jawaban Informatika kelas 11 SMA/MA yang dapat dipelajari oleh siswa di rumah sebagai bahan pembelajaran.

Baca juga: Jawaban Informatika Kelas 11 SMA Halaman 34 Ayo Berlatih Aktivitas Individu Aktivitas SAP-K11-06-U

Baca juga: Jawaban Informatika Kelas 11 SMA Halaman 33 Ayo Berlatih Aktivitas Individu Aktivitas SAP-K11-05-U

Ayo Berlatih!

Aktivitas Berpasangan

Aktivitas SAP-K11-07-U: Bermain Angka

Deskripsi Tugas

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?

Jawaban dan Pembahasan :

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 bhabis 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 digitung lebih dari sekali (seperti pada kasus menghitung bilangan Fibonacci). Misalnya, saat menghitung L(25), kita bisa menggunakan jalur langkah :