Bermain Angka (Algoritma Dinamis)

     Selamat datang di blog aku, guys! Kali ini ada pertanyaan yang cukup bikin pusing, nih. Kira-kira bagaimana soal dan cara pengerjaannya, ya? Yuk, kita simak dulu soalnya! 

˖ ݁ ˓ ⨳  Soal 

     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:

① Budi boleh mengganti bilangan n dengan n - 1.

② Jika bilangan saat ini adalah genap (habis dibagi 2), maka Budi boleh menggantinya dengan n/2.

③ 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? 

˖ ݁ ˓ ⨳  Menggunakan Logika

➙  Langkah 1

25 - 1 = 24

➙  Langkah 2

24 : 2 = 12

➙  Langkah 3

12 : 3 = 4

➙  Langkah 4

4 : 2 = 2

➙  Langkah 5

2 : 2 = 1

     Jadi, jumlah langkah minimum yang diperlukan adalah 5 langkah.