Applied Recursion(Hours 12) part 1

Pemakaian rekursi pada bab ini ada 2 macam yaitu

• The Towers of Hanoi puzzle
  
• Mergesort
  

The Towers of Hanoi puzzle

Adalah sebuah puzze kuno dimana terdiri dari piringan silinder(disk) yang berbeda diameter yang disusun menjadi piramid dalam 1 kolom. Diharuskan untuk memindahkan kolom disk ke kolom lain dengan syarat bahwa disk yang lebih besar tidak boleh berada diatas disk yang lebih kecil. Pada gambar ditunjukkan semua disk berawal dari kolom A. Diharuskan memindahkan semua disk ke kolom C. Hanya 1 disk yang dapat di pindah dalam 1 waktu dan tidak boleh ada menempatkan disk yang lebih besar diatas disk yang lebih kecil.

Langkah untuk menyelesaikan puzzle ini adalah

Urutan pemindahan disk

1. Disk 1: A ke B
   
2. Disk 2: A ke C
   
3. Disk 1: B ke C
   
4. Disk 3: A ke B
   
5. Disk 1: C ke A
   
6. Disk 2: C ke B
   
7. Disk 1: A ke B
   
8. Disk 4: A ke C
   
9. Disk 1: B ke C
   
10. Disk 2: B ke A
    
11. Disk 1: C ke A
    
12. Disk 3: B ke C
    
13. Disk 1: A ke B
    
14. Disk 2: A ke C
    
15. Disk 1: B ke C
    

Jadi untuk memindah 4 disk dari kolom A ke C diperlukan 15 langkah

Setelah diketahui untuk memindahkan 4 disk diperlukan 15 langkah maka untuk memindahkan 5 disk dapat dilakukan seperti pada gambar diatas yaitu dengan memindahkan 4 disk ke kolom B(15 langkah) lalu memindahkan disk terbesar(disk ke 5) ke kolom C (1 langkah) lalu memindahkan 4 disk dari kolom B ke kolom C(15 langkah). Jadi untuk memindahkan 5 disk dari kolom A ke kolom C diperlukan 15+1+15 = 31 langkah
 

rumus umum jumlah langkah yang diperlukan untuk menyelesaikan puzzle ini adalah

jumlah langkah = 2ⁿ-1

dengan n adalah jumlah piringan disk



implementasi dalam pemrograman C++

//towers.cpp

//solves Towers of Hanoi puzzle

#include <iostream>

using namespace std;

void doTowers(int, char, char, char); //prototype

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

int main()

{

int nDisks; //number of disks

cout << "Enter number of disks: "; //get # of disks

cin >> nDisks;

doTowers(nDisks, 'A', 'B', 'C'); //solve it

return 0;

}

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

void doTowers(int topN, char src, char inter, char dest)

{

if(topN==1) //display

cout << "Disk 1 from " << src << " to " << dest << endl;

else

{

doTowers(topN-1, src, dest, inter); //src to inter

cout << "Disk " << topN //display

<< " from " << src << " to " << dest << endl;

doTowers(topN-1, inter, src, dest); //inter to dest

}

}


 
Output

Enter (3 disks): s=A, i=B, d=C

Enter (2 disks): s=A, i=C, d=B

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Move bottom disk 2 from A to B

Enter (1 disk): s=C, i=A, d=B

Base case: move disk 1 from C to B

Return (1 disk)

Return (2 disks)

Move bottom disk 3 from A to C

Enter (2 disks): s=B, i=A, d=C

Enter (1 disk): s=B, i=C, d=A

Base case: move disk 1 from B to A

Return (1 disk)

Move bottom disk 2 from B to C

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Return (2 disks)

Return (3 disks)

Disk 1 from A to C

Disk 2 from A to B

Disk 1 from C to B

Disk 3 from A to C

Disk 1 from B to A

Disk 2 from B to C

Disk 1 from A to C


 
Berlanjut ke part 2

sumber : Kuliah Logika dan Pemrograman Sistem II