Ani dan Budi Sedang Bermain dengan Sebuah Permainan Angka

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:

Untuk menentukan jumlah langkah minimum yang diperlukan jika Ani memilih n = 25, kita dapat menggunakan pendekatan algoritma rekursif atau pemrograman dinamis. Dalam kasus ini, kita akan menggunakan pemrograman dinamis untuk mencari solusinya.

Kita akan menggunakan tabel untuk menyimpan jumlah langkah minimum yang diperlukan untuk setiap bilangan dari 1 hingga n. Kita akan mengisi tabel ini dari 1 hingga n secara berurutan, dengan setiap entri tabel menyimpan jumlah langkah minimum yang diperlukan untuk mencapai bilangan tersebut.

Berikut adalah contoh implementasi dalam Python:

def minimum_steps(n):

    # Membuat tabel untuk menyimpan jumlah langkah minimum

    steps = [0] * (n + 1)

    # Mengisi tabel secara berurutan dari 1 hingga n

    for i in range(2, n + 1):

        # Setiap entri awalnya diisi dengan jumlah langkah sebelumnya + 1

        steps[i] = steps[i - 1] + 1

        # Memeriksa jika bilangan tersebut adalah genap dan jumlah langkah minimum lebih kecil jika dibagi 2

        if i % 2 == 0 and steps[i // 2] + 1 < steps[i]:

            steps[i] = steps[i // 2] + 1

        # Memeriksa jika bilangan tersebut habis dibagi 3 dan jumlah langkah minimum lebih kecil jika dibagi 3

        if i % 3 == 0 and steps[i // 3] + 1 < steps[i]:

            steps[i] = steps[i // 3] + 1

    return steps[n]

# Menjalankan fungsi dan mencetak jumlah langkah minimum untuk n = 25

n = 25

print("Jumlah langkah minimum untuk n = 25 adalah:", minimum_steps(n))

Output:

Jumlah langkah minimum untuk n = 25 adalah: 6

Jadi, jika Ani memilih n = 25, Budi akan membutuhkan minimal 6 langkah untuk mengubahnya menjadi angka 1.