1. Sekolah Dasar
  2. Sekolah Menengah Pertama
  3. Sekolah Menengah Atas
  4. Mata Pelajaran
  5. Programming

Ani dan Budi sedang bermain dengan sebuah permainan angka: pertama

Berikut ini adalah pertanyaan dari oktavianierli90 pada mata pelajaran TI untuk jenjang Sekolah Menengah Atas

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: 5421 (dalam tiga langkah). Tentukan, berapakah jumlah langkah minimum yang diperlukan, jika Ani memilih n = = 25?​

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Banyak langkah minimum yang diperlukan, jika Ani memilih n = 25, adalah 5 langkah.
 

Pembahasan

Saya tulis kembali pertanyaannya, agar lebih jelas.

Pertanyaan

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?

Penyelesaian

Secara singkat, sesuai dengan aturan pada deskripsi di atas, maka terdapat beberapa jalur dengan langkah minimum , dengan pemilihan n = 25, yaitu:

  • 25 → 24 → 12 → 6 → 3 → 1
  • 25 → 24 → 12 → 4 → 2 → 1
  • 25 → 24 → 8 → 4 → 2 → 1

∴  Ketiga jalur tersebut menghasilkan banyak langkah minimum yang sama, yaitu 5 langkah.

_________________

Lebih lanjut lagi, dapat diperhatikan bahwa untuk memperoleh jalur dengan langkah minimum di atas, jika diimplementasikan dalam program, maka program akan memiliki lebih dari 1 alternatif jalur ketika nilai n yang dievaluasi memenuhi lebih dari 1 kondisi di atas. Operasi n – 1 selalu dapat dilakukan oleh program, karena tanpa kondisi yang membatasi. Maka, minimal program akan memiliki 2 alternatif untuk menentukan nilai selanjutnya.

Hal inilah yang harus dihindari dalam pemrograman dinamis (dynamic programming/DP). Kita dapat membangun sebuah tabel, yang dinamakan dengan tabel memoisasi (memoization table), sehingga untuk masukan n tertentu, kita tinggal memilih dari tabel yang sudah ditentukan. Hal ini terkait dengan efisiensi program dan mempercepat waktu eksekusi program.

Untuk soal di atas, jalur-jalur yang terbentuk dapat dianggap sebagai barisan L(n). Jelas bahwa L(1) = 0, karena kita tidak perlu melakukan apa-apa.

Untuk nilai n selanjutnya, ambil A, B, dan C sedemikian rupa sehingga:
A = L(n – 1) dari tabel memoisasi.

Jika n bilangan genap (habis dibagi 2), ambil B = L(n/2) dari tabel memoisasi.

Jika n habis dibagi 3, ambil C = L(n/3) dari tabel memoisasi.

Oleh karena itu, untuk setiap n:
⇒ L(n) = min(A, B, C) + 1

Tabel memoisasi yang dapat dibentuk adalah sebagai berikut.

\begin{array}{c|c|l}\ \ n\ \ &L(n)&\rm Keterangan\\1&\bf0&-\\2&\bf1&A=B=0,\ C=\rm kosong\\&&L(2)=\min(0,0)+1=1\\3&\bf1&A=1,\ B=\rm kosong,\ C=0\\&&L(3)=\min(1,0)+1=1\\4&\bf2&A=1,\ B=1,\ C=\rm kosong\\&&L(4)=\min(1,1)+1=2\\5&\bf3&A=2,\ B=C=\rm kosong\\&&L(5)=\min(2)+1=3\\6&\bf2&A=3,\ B=1,\ C=1\\&&L(6)=\min(3,1,1)+1=2\\7&\bf3&A=2,\ B=\rm kosong,\ C=\rm kosong\\&&L(7)=\min(2)+1=3\\8&\bf3&A=3,\ B=2,\ C=\rm kosong\\&&L(8)=\min(3,2)+1=3\end{array}

\begin{array}{c|c|l}\ \ n\ \ &L(n)&\rm Keterangan\\9&\bf2&A=3,\ B=\rm kosong,\ C=1\\&&L(9)=\min(3,1)+1=2\\10&\bf3&A=2,\ B=3,\ C=\rm kosong\\&&L(10)=\min(2,3)+1=3\\11&\bf4&A=3,\ B=\rm kosong,\ C=\rm kosong\\&&L(11)=\min(2,3)+1=4\\12&\bf3&A=4,\ B=2,\ C=2\\&&L(12)=\min(4,2,2)+1=3\\13&\bf4&A=3,\ B=\rm kosong,\ C=\rm kosong\\&&L(13)=\min(3)+1=4\\14&\bf4&A=4,\ B=3,\ C=\rm kosong\\&&L(14)=\min(4,3)+1=4\\15&\bf4&A=4,\ B=\rm kosong,\ C=3\\&&L(15)=\min(4,3)+1=4\end{array}

\begin{array}{c|c|l}\ \ n\ \ &L(n)&\rm Keterangan\\16&\bf4&A=4,\ B=3,\ C=\rm kosong\\&&L(16)=\min(4,3)+1=4\\17&\bf4&A=4,\ B=\rm kosong,\ C=\rm kosong\\&&L(17)=\min(4)+1=5\\18&\bf3&A=4,\ B=2,\ C=2\\&&L(18)=\min(4,2,2)+1=3\\19&\bf4&A=3,\ B=\rm kosong,\ C=\rm kosong\\&&L(19)=\min(3)+1=4\\20&\bf4&A=4,\ B=3,\ C=\rm kosong\\&&L(20)=\min(4,3)+1=4\\21&\bf4&A=4,\ B=\rm kosong,\ C=3\\&&L(21)=\min(4,3)+1=4\\22&\bf5&A=4,\ B=4,\ C=\rm kosong\\&&L(22)=\min(4,3)+1=5\end{array}

\begin{array}{c|c|l}\ \ n\ \ &L(n)&\rm Keterangan\\23&\bf5&A=5,\ B=\rm kosong,\ C=\rm kosong\\&&L(23)=\min(5)+1=6\\24&\bf4&A=4,\ B=4,\ C=3\\&&L(24)=\min(4,4,3)+1=4\\25&\bf5&A=4,\ B=\rm kosong,\ C=\rm kosong\\&&L(25)=\min(4)+1=5\\\end{array}

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Mon, 21 Nov 22
<< Previous Post
Next Post >>