Menerapkan Konsep Rekursi - Berpikir Komputasional - Rekursi
Summary
TLDRThis video focuses on computational thinking and recursion strategies in algorithmic programming. It presents two problems: the first involves determining how many ways tiles can be arranged on a 2xN floor using recursion. For N = 8, there are 34 ways, following a Fibonacci-like sequence. The second problem discusses stacking pancakes of varying sizes and moving them between plates according to specific rules. The recursive solution finds the minimal steps required to move six pancakes, resulting in 63 moves. The video demonstrates these concepts through step-by-step examples.
Takeaways
- 🧱 The problem involves placing tiles on a 2xN floor using 1x2 tiles, which can be placed either horizontally or vertically.
- 🔢 For N=8, the number of ways to place the tiles can be calculated using a recursive relation.
- 🔄 The recursive formula is based on the two previous terms: K(n) = K(n-1) + K(n-2).
- 📊 Example calculations: K(1) = 1, K(2) = 2, K(3) = 3, K(4) = 5, K(5) = 8, K(6) = 13, K(7) = 21, K(8) = 34.
- 🎯 The final answer for N=8 is 34 ways to arrange the tiles.
- 🥞 The second problem involves moving a stack of pancakes from one plate to another, following a size-order rule.
- 💡 The pancake problem is similar to the Tower of Hanoi problem, requiring a helper plate to transfer pancakes while maintaining the size-order.
- ⏳ The minimum steps to transfer pancakes follow a recursive pattern: P(n) = 2 * P(n-1) + 1.
- 📈 For example, 1 pancake takes 1 step, 2 pancakes take 3 steps, 3 pancakes take 7 steps, and 6 pancakes require 63 steps.
- 🚀 Both problems showcase the power of recursive thinking in solving algorithmic challenges.
Q & A
What is the first problem described in the script?
-The first problem is about tiling a 2xN floor with N tiles, where each tile is of size 1x2. The tiles can be placed either horizontally or vertically, and the task is to determine how many different ways the tiles can be arranged on the floor for N=8.
How does the script explain the solution to the tile placement problem?
-The script explains that for N=1, there is 1 way to place the tile (vertically), and for N=2, there are 2 ways (either both vertical or both horizontal). For higher values of N, the number of ways is calculated using a recursive relation: K(n) = K(n-1) + K(n-2), where K(n) represents the number of ways to tile the floor. This relation is similar to the Fibonacci sequence.
What is the recursive formula provided to solve the tile placement problem?
-The recursive formula is K(n) = K(n-1) + K(n-2), with base cases K(1) = 1 and K(2) = 2. This allows for calculating the number of ways to place tiles for any value of N.
How many ways can the tiles be arranged for N=8?
-For N=8, the number of ways to arrange the tiles is 34, as calculated by the recursive formula using the previously computed values for smaller N.
What is the second problem described in the script?
-The second problem is about moving a stack of pancakes from one plate to another. The largest pancake must always be at the bottom, and only one pancake can be moved at a time. Budi, the person in the problem, wants to know the minimum number of steps required to move 6 pancakes while following these rules.
What is the minimum number of steps required to move 6 pancakes?
-The minimum number of steps required to move 6 pancakes is 63, as derived from a recursive relation similar to the Tower of Hanoi problem.
How does the recursive relation for the pancake problem work?
-The recursive relation is P(n) = 2 * P(n-1) + 1, where P(n) is the minimum number of steps required to move n pancakes. The base case is P(1) = 1.
How many steps are required to move 3 pancakes?
-To move 3 pancakes, the minimum number of steps required is 7, following the recursive process described in the script.
What is the general strategy for solving the pancake problem?
-The strategy is to move the smallest pancake first, then progressively move larger pancakes while using an auxiliary plate to temporarily hold pancakes during the process. The recursive solution builds on smaller subproblems, similar to the Tower of Hanoi.
What are the key concepts covered in the script related to recursion?
-The key concepts covered include recursive problem-solving techniques, the use of base cases, and recursive relations. The tile placement problem uses a Fibonacci-like sequence, while the pancake problem uses a Tower of Hanoi-like approach.
Outlines
📚 Recursive Tile Arrangement Problem
The speaker introduces a problem where tiles need to be arranged on a 2xN floor using N tiles, each measuring 1x2. The challenge is to find the number of ways to arrange the tiles either horizontally or vertically. Examples with different values of N are given, including an illustration for N=4, where five distinct ways of arranging the tiles are possible. A formula for calculating the number of tile arrangements for larger values of N is outlined.
🔢 Recursive Solution for Tile Arrangements
This section provides further explanation on how the recursive relation works for calculating the number of tile arrangements. The base cases, K1=1 and K2=2, are presented, followed by the recursive relation that combines the two previous values to calculate the number of arrangements for larger N. The speaker demonstrates how this recursive relation is applied to calculate K8, which results in 34 ways to arrange tiles.
🥞 Pancake Stacking Problem
The speaker introduces the second problem about moving a stack of pancakes from one plate to another. The key rule is that larger pancakes must always remain beneath smaller ones. The example involves moving two pancakes with three steps, and the problem scales up to six pancakes. A step-by-step breakdown is provided for moving three pancakes, showing how the pancakes are transferred between plates.
⚙️ Recursive Formula for Pancake Moving
In this final section, a recursive relation for the number of steps required to move pancakes is introduced. The formula PN = 2*P(N-1) + 1 is derived, explaining how the process scales as more pancakes are added. The example progresses through 1, 2, 3, and 4 pancakes, where the steps increase to 63 for six pancakes. The speaker concludes with a motivational note for learners, encouraging them to continue practicing recursion.
Mindmap
Keywords
💡Recursion
💡Algorithmic strategy
💡Tile arrangement problem
💡Base case
💡Recursive relation
💡Pancake stacking problem
💡Tower of Hanoi
💡PN recursive formula
💡Computational thinking
💡Fibonacci sequence
Highlights
Introduction to solving problems using recursion with computational thinking and algorithmic strategies.
Explanation of the first problem: Tiling a 2xN floor with 1x2 tiles, emphasizing the recursive approach.
Illustration of tile placement: Horizontal and vertical arrangements for different values of N.
For N=4, five distinct ways to arrange the tiles are demonstrated.
A recursive formula is derived for determining the number of ways to tile a 2xN floor, where KN = K(N-1) + K(N-2).
Base cases are defined: K1 = 1 and K2 = 2 for N = 1 and N = 2 respectively.
For N=8, the recursive approach gives 34 ways to tile the floor, illustrating the growth in complexity.
Transition to the second problem: Moving pancakes between plates while maintaining the order based on size.
The pancake stacking problem introduces three plates (A, B, and C) and the rule that larger pancakes must always be below smaller ones.
A recursive strategy is used to determine the minimal number of moves required to transfer all pancakes between plates.
For 3 pancakes, the minimum number of moves is 7, and for 4 pancakes, it is 15.
The recursive formula for the pancake problem is PN = 2 * P(N-1) + 1, where P1 = 1.
For 6 pancakes, the total number of moves required is 63, following the recursive solution.
Both problems showcase the power of recursion in breaking down complex tasks into simpler, repeatable steps.
The session concludes with a reinforcement of computational thinking concepts through recursive problem-solving.
Transcripts
[Musik]
Assalamualaikum warahmatullahi
wabarakatuh kita lanjutkan latihan soal
terkait tentang rekursi berpikir
komputasional strategi algoritmik dan
pemrograman
[Musik]
aktivitas individu yaitu menerapkan
konsep rekursi dengan deskripsi tugas
sebagai berikut
selesaikanlah dua problem berikut dengan
menerapkan konsep rekursi yang telah
kalian pelajari
permasalahan pertama
yaitu tentang memasang keramik terdapat
sebuah lantai yang berukuran dua kali n
pada lantai tersebut ingin dipasang n
buah keramik yang masing-masing
berukuran satu kali dua
seperti ini ilustrasinya
ada keramik dan lantai
[Musik]
setiap keramik dapat dipasang secara
mendatar atau horizontal maupun secara
tegak atau vertikal sebagai contoh jika
n adalah 4 maka akan ada lima buah cara
berbeda memasang 4 keramik
yaitu cara pertama
semua keramik dipasang secara horizontal
cara kedua
semua keramik dipasang secara vertikal
Ya seperti ini
kemudian
cara yang ketiga
paling kiri ada dua keramik vertikal
dan yang kanan Sisanya adalah horizontal
Ya seperti ini
kemudian Cara yang keempat
paling kiri ada dua keramik horizontal
dan Sisanya adalah vertikal
cara yang kelima paling kiri dan paling
kanan vertikal dan sisanya horizontal
[Musik]
pertanyaannya adalah Tentukan Ada berapa
cara memasang keramik untuk n = 8
jawabannya seperti ini untuk N1 yaitu
ada satu cara yaitu keramik dipasang
secara vertikal kemudian N2
ada dua cara
semua keramik dipasang secara vertikal
atau semua keramik dipasang secara
horizontal untuk N2 ada dua cara
Kemudian untuk N3 itu ada tiga cara
yang pertama semua keramik dipasang
secara vertikal
kemudian cara yang kedua paling kiri ada
dua keramik horizontal dan satu vertikal
kemudian cara yang ketiga paling kiri
ada satu keramik vertikal dan sisanya
dua horizontal
Kemudian untuk N = 4 itu ada 5 cara dan
n = 5 ada 8 cara
Cara yang pertama
[Musik]
Cara yang pertama semua keramik dipasang
vertikal
kelima keramik dipasang secara vertikal
Kemudian untuk cara yang kedua
yaitu
horizontal horizontal dan terakhir
vertikal
untuk cara yang ketiga horizontal
vertikal kemudian horizontal
selanjutnya Cara yang keempat
dari 5 keramik
untuk n = 5 yaitu
vertikal horizontal vertikal vertikal
cara yang kelima
vertikal horizontal horizontal
[Musik]
selanjutnya cara yang keenam vertikal
vertikal horizontal vertikal
cara yang ketujuh vertikal vertikal
vertikal 3 kemudian sisanya horizontal
cara selanjutnya cara yang ke-8 kita
bisa
dengan cara horizontal vertikal vertikal
vertikal
kemudian
itu tadi 8 cara untuk n = 5 terakhir
kita harus menentukan nilai basis dari
referensi ini karena relasi referensi di
atas melibatkan dua suku sebelumnya
yaitu kn-1 dan k n -2
kita harus menentukan dua nilai pertama
dari barisan KN yaitu K1 dan K2 untuk N1
jelas bahwa hanya ada satu cara memasang
keramik pada lantai ukuran 2x1 yaitu
secara vertikal saja untuk n-nya sama
dengan 2 terdapat dua cara memasang
keramik yaitu keduanya secara horizontal
atau keduanya secara vertikal jadi kita
simpulkan bahwa
K1 = 1 dan K2 = 2
kesimpulannya seperti ini N = 1 ada satu
cara kemudian n = 2 ada dua cara
selanjutnya n = 3 ada 3 cara n = 4 ada 5
cara kemudian n = 5 ada 8 cara
sehingga untuk
an nya
pada
relasi referensi ini sama dengan 1 untuk
n-nya 1 dan untuk n-nya yang lebih dari
satu adalah KN -1 + k n - 2
sehingga
n6 adalah N4 + n5 ada 13 cara kemudian
n7 adalah n5 + n6 yaitu ada 21 cara
sedangkan N8 yaitu n6 + n7 13 + 21 yaitu
ada 34 cara
dari hasil perumusan secara rekursif
barisan KN di atas kita dapat menghitung
k8 dengan lebih mudah Yaitu dimulai
dengan nilai K1 yaitu sama dengan 1 dan
K2 = 2
setiap suku berikutnya didapat dengan
cara menjumlahkan dua suku terakhir jadi
barisan KN yang didapat adalah sebagai
berikut 1
2 3
5
8
13
21
34 dan seterusnya sehingga jawaban yang
diinginkan untuk k8 adalah 34
kita lanjutkan permasalahan kedua
menumpuk pancake
Budi memiliki setumpuk pancake yang
memiliki ukuran dari besar sampai kecil
pendek tersebut ditumpuk di atas sebuah
piring
dengan aturan bahwa pancake yang besar
harus berada di bawah pancake yang lebih
kecil
Budi ingin memindahkan bangkit ini dari
satu piring ke piring lainnya namun
dalam prosesnya Ia tetap ingin mengikuti
aturan bahwa pancake yang besar harus
selalu berada di bawah pancake yang
lebih kecil
Selain itu Budi juga hanya boleh
memindahkan satu buah pancake saja pada
satu waktu tertentu dari satu piring ke
piring lainnya
Budi menyadari bahwa ia memerlukan
sebuah piring tambahan untuk dapat
melakukan perpindahan ini
jika piring Asal pancake diberi nama a
kemudian 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 pancake yang harus ia
lakukan untuk dapat memindahkan semua
pancake yang dimilikinya dari piring a
ke piring C
dengan mungkin menggunakan piring B
sebagai tempat sementara
misalnya 3 Budi memiliki dua buah
pancake saja kita beri nama pancake 1
dan dimana teknik 1 berukuran lebih
kecil dari pancake 2 maka ia membutuhkan
minimal 3 langkah pemindahan
yang pertama pindahkan pancake satu dari
piring a ke piring B kemudian pindahkan
Pengki dua dari piring a ke piring c dan
selanjutnya langkah yang ketiga adalah
pindahkan page 1 dari piring B ke piring
C
sekarang pertanyaannya Berapakah jumlah
langkah minimal yang diperlukan apabila
Budi memiliki 6 buah pancake
dari pancake 3
kita ilustrasikan seperti ini
langkah yang pertama
paling atas pancake berwarna biru
kemudian
warna kuning dan warna orange
pancake yang berwarna biru dipindahkan
ke piring
[Musik]
kemudian Langkah kedua pancake yang
kuning dipindahkan ke piring B
selanjutnya Langkah ketiga
dan biru dipindahkan ke piring B di
atasnya pendek kuning
selanjutnya
pancake yang ada di piring a yang
berwarna orange dipindahkan ke piring C
dan langkah yang kelima
pancake yang ada di piring B pending
biru dipindahkan ke piring a
langkah yang keenam pancake kuning
dipindahkan ke
piring C diatas pancake orange
kemudian
langkah yang ketujuh
biru dipindahkan
ke piring C di atas pancake kuning
sehingga untuk 3 pancake membutuhkan 7
langkah
sekarang kita cari Berapa langkah untuk
tempat pancake
kita tinggal melanjutkan dari 3 pancake
sebelumnya
yaitu 7 langkah
[Musik]
kita lanjutkan yaitu langkah yang ke-8
pancake yang ada di piring a yang
berwarna merah dipindahkan ke
piring C
kemudian pancake yang berwarna biru yang
ada di piring B dipindahkan ke piring C
diatas pancake merah
selanjutnya langkah yang ke-10 pancake
kuning dari piring B pindah ke piring a
langkah yang ke-11
pancake biru yang ada di piring C
dipindahkan ke piring a di atas teknik
kuning
langkah yang ke-12
dari piring B dipindahkan ke piring C
kemudian langkah 13
dipindahkan dari piring a ke piring B
langkah yang ke-14
pancake kuning dari piring a dipindahkan
ke piring C
kemudian Langkah terakhir dari 4 pancake
yaitu langkah 15
pancake biru dari piring B dipindahkan
ke piring C
ya itu tadi dari 4 pancake berarti
membutuhkan 15 langkah
[Musik]
dari satu pancake itu ada satu langkah
kemudian 2 pancake 3 langkah 3 pancake 7
langkah 4 pancake 15 langkah
Oleh karena itu kita dapat menyimpulkan
bahwa
PN dapat didefinisikan secara rekursif
dengan menggunakan relasi rekursif
sebagai berikut
PN = P N -1 + 1 + pn-1 sehingga PN
adalah
sama dengan dua kali pn-1 + 1
[Musik]
sebagai basis dari referensi jelas bahwa
P1 adalah 1
dari sini kita dapat menghitung barisan
PN sebagai berikut
1 3
7 15 31
63 dan seterusnya sehingga jawaban yang
diinginkan adalah
untuk P6 adalah 63
[Musik]
demikian Tadi latihan soal menerapkan
konsep rekursi pada materi berpikir
komputasional bagian rekursi pada topik
strategi algoritmik dan pemrograman
Terima kasih semoga bermanfaat Selamat
belajar dan tetap semangat
[Musik]
Посмотреть больше похожих видео
Rekursi - Berpikir Komputasional
Re 3. Parameterised and Functional Recursion | Strivers A2Z DSA Course
Penjelasan Algoritma Rekursif | Algoritma Faktorial dan Pangkat | Algoritma Pertemuan 57
Re 2. Problems on Recursion | Strivers A2Z DSA Course
Latihan Soal Informatika Kelas 7 Bab 2 Dengan Pembahasan Lengkap
[TUTORIAL VIDEO] How To Make Cheat Codes For Tekken 6 | Tekken 8 Cheat Codes Making | Tekken 8 PSP
5.0 / 5 (0 votes)