Jawaban Informatika Kelas 11 SMA Halaman 27 Ayo Berlatih Aktivitas Individu Aktivitas SAP-K11-03-U

2. Kedua, apabila kita memilih untuk meletakkan keramik paling kiri secara horizontal, kita harus mengisi dua kolom dan baris pertama, dengan dua buah keramik secara horizontal. Hal ini berarti tersisa kolom (atau dengan kata lain, sebuah lantai berukuran ). Perhatikan ilustrasi pada gambar di bawah ini, untuk N = 4.

Dengan demikian, sisa kolom tadi dapat dipasang keramik dengan sebanyak cara.

a. Karena kedua cara tersebut di atas dapat dipilih secara bebas, banyaknya cara memasang keramik untuk lantai berukuran adalah hasil penjumlahan banyaknya cara dari kedua kasus di atas. Atau dengan kata lain, FN =FN-1+FN-2 . Relasi Rekurensi ini sama dengan relasi rekurensi pada barisan Fibonacci yang dijelaskan sebelumnya.

b. Terakhir, kita harus menentukan nilai basis dari rekurensi ini. Karena relasi rekurensi di atas melibatkan dua suku sebelumnya ( FN-1 dan FN-2 ), kita harus menentukan dua nilai pertama dari barisan FN , yaitu F1 dan F2. Untuk N =1 , jelas bahwa hanya ada
satu cara memasang keramik pada lantai berukuran 2×1 , yaitu secara vertikal saja. Untuk N =2 , terdapat 2 cara memasang keramik, yaitu keduanya secara horizontal, atau keduanya secara vertikal. Jadi, kita simpulkan bahwa F1 =1 dan F2 =2. Dari hasil perumusan secara rekursif baris FN di atas, kita dapat menghitung F8 dengan lebih mudah, yaitu: dimulai dengan nilai F1 =1 dan F2 =2 , setiap suku berikutnya didapat dengan cara menjumlahkan dua suku terakhir. Jadi, barisan FN yang didapatkan adalah sebagai berikut:

{FN} = 1,2,3,5,8,13,21,34,...

Sehingga, jawaban yang diinginkan adalah F8 =34 .

Permasalahan 2: Menumpuk Panekuk

Budi memiliki setumpuk panekuk yang memiliki ukuran dari besar sampai kecil. Panekuk-panekuk tersebut ditumpuk di atas sebuah piring, dengan aturan bahwa panekuk yang besar harus berada di bawah panekuk yang lebih kecil.

Budi ingin memindahkan panekuk ini dari satu piring ke piring lainnya, namun dalam prosesnya ia tetap ingin mengikuti aturan bahwa panekuk yang besar harus selalu berada di bawah panekuk yang lebih kecil. Selain itu, Budi juga hanya boleh memindahkan satu buah panekuk saja, pada satu waktu tertentu, dari satu piring ke pring lainnya. Budi menyadari bahwa ia memerlukan sebuah piring tambahan untuk dapat melakukan perpindahan ini. Jika piring asal panekuk diberi nama A, piring tujuan diberi nama C, maka Budi akan menyiapkan sebuah piring bantuan sebagai tempat sementara, yang diberi nama piring B.
Budi ingin mengetahui, berapa banyak langkah pemindahan panekuk yang harus ia lakukan, untuk dapat memindahkan
semua panekuk yang dimilikinya, dari piring A ke piring C (dengan mungkin menggunakan piring B sebagai tempat sementara). Misalnya, jika Budi memiliki 2 buah panekuk saja (diberi nama panekuk 1 dan, dimana panekuk 1 berukuran lebih kecil dari panekuk 2), maka ia akan membutuhkan minimal 3 langkah pemindahan:

1. Pindahkan panekuk 1 dari piring A ke piring B
2. Pindahkan panekuk 2 dari piring A ke piring C
3. Pindahkan panekuk 1 dari piring B ke piring C
Berapakah jumlah langkah minimal yang diperlukan apabila Budi memiliki 6 buah panekuk?

Jawaban dan Pembahasan :

Kita dapat menyelesaikan permasalahan penumpukan panekuk dengan berpikir secara rekursif sebagai berikut: untuk memindahkan sebanyak n buah panekuk-panekuk dari piring A ke piring C (menggunakan piring B sebagai tempat sementara), kita dapat melakukan 3 tahap berikut:

1. Pindahkan n - 1 buah panekuk paling atas dari piring A ke piring B (dengan menggunakan piring C sebagai tempat sementara)
2. Pindahkan panekuk paling bawah (paling besar) dari piring A ke piring C
3. Pindahkan n - 1 buah panekuk dari piring B ke piring C

Jika jumlah langkah minimal untuk memindahkan n buah panekuk dinyatakan sebagai barisan HN, maka kita memerlukan HN-1 langkah pemindahan untuk melakukan tahap no. 1 dan 3 di atas, sedangkan tahap no.2 hanya memerlukan 1 langkah. Oleh karena itu, kita dapat menyimpulkan bahwa barisan HN dapat didefinisikan secara rekursif dengan menggunakan relasi rekurensi sebagai berikut:

HN=HN-1+1+HN-1= 2HN-1+1

Sebagai basis dari rekurensi, jelas bahwa H1=1. Dari sini, kita dapat menghitung barisan HN sebagai berikut:

{HN} = 1, 3, 7, 15, 31, 63, ...

Sehingga jawaban yang diinginkan adalah H6=63.

Dapatkan konten pendidikan mata pelajaran lainnya dari Kurikulum Merdeka dan Kurikulum 2013 dengan klik Di Sini.

Dapatkan juga berita penting dan informasi menarik lainnya dengan mengklik Google News.