Page 47 - EMODUL INFORMATIKA XI FASE F

4. Tugas Algoritma Program Dinamis

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:
2. Budi boleh mengganti bilangan n dengan n - 1.

3. Jika bilangan saat ini adalah genap (habis dibagi 2), maka Budi
boleh menggantinya dengan n/2.
4. 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?

47