Rabu, 02 Juni 2010

algoritma untuk menara hanoi

anoi, sudah pada tahu kan apa itu menara hanoi? menara hanoi adalah permainan tebak-tebakan, namun bukan sembarang tebak-tebakan, tapi harus ada algoritma dan perhitungan yang sistematis.

secara sepintas, tebak-tebakan menara hanoi adalah seperti ini (yang paling simpel): terdapat 3 buah tiang dengan 3 buah piringan diatas sebuah tiang pertama. Bagaimana caranya, kita harus memindah ketiga piringan itu menuju ke tiang ketiga, semuanya! Kita bisa bebas memindahkan ketiga piringan tersebut, namun ada satu syarat, piringan terkecil, harus selalu berada di atas piringan terbesar, sehingga membentuk sebuah kerucut.

Lihat animasi berikut ini:





Jika misalkan ada 4 buah piringan, maka akan ada 11 langkah pemindahan. Jika ada 3 buah piringan, maka akan ada 7 langkah pemindahan. Jika ada 2 maka akan ada 3 langkah. Dan jika hanya ada 1, maka akan hanya ada 1 langkah pemindahan.

Secara logika sistematis, jika kita lihat model angka yang dihasilkan oleh jumlah langkah pemindahan, maka akan membentuk sebuah bilangan suku. Coba deh hitung, maka akan kita dapatkan model suku tersebut, yang ternyata, sukunya adalah kelipata satu dari suku yang lainnya (gak tau, kalau di matematik disebut apaan)

fikir udah ngitung? ya kan, membentuk suku kan?

Lha, tugas kita adalah, membuat sebuah program bebas dengan c atau pascal, pokoknya, program tersebut harus bisa mengeluarkan hasil berupa langkah pemindahan dan jumlah langkah pemindahan.

Misalkan, user menginput 3. Maka yang keluar haruslah langkah-langkah pemindahan ketiga piringan tersebut ke menara paling akhir (menara ke-tiga) beserta jumlah langkah pemindahannya.

Silahkan dipikir, bagaimana algoritmanya. Kalo sudah, coba dipikir, bagaimana memprogramkannya. Aslinya sih, program ini tuh mudah, hanya menuliskan rekursi-nya yang terkadang bingung.

Oke, kalo sudah nyerah, gini nih programnya:

  1. #include
  2. #include
  3. void hanoey(int n, char asal, char bantu, char tujuan)
  4. {
  5. static int jml;
  6. if (n==0) return;
  7. hanoey(n-1,asal,tujuan,bantu);
  8. jml++;
  9. printf("Pindahkan piringan ke %d dari %c ke %c (%d)\n", n, asal,tujuan,jml);
  10. hanoey(n-1,bantu,asal,tujuan);
  11. }
  12. int main(void)
  13. {
  14. int n, jml;
  15. printf("jumlah piringan ? ");
  16. scanf("%d",&n);
  17. jml=n;
  18. hanoey(n,'a','b','c');
  19. getch();
  20. }


Intinya, menara hanoi selalu memindahkan piringan dari asal, lalu ke menara tujuan, lalu ke menara bantuan, lalu ke asal, lalu ke tujuan lagi. Begitulah inti dari algoritma hanoi.

dan sepertinya, saya nggak perlu menjelaskan kembali bukan, maksud kode diatas? karena kita pernah menyinggungnya di chapter lalu di sini.

kalau ada yang ditanyakan, tanya aja, bebas kok, akan berusaha aku jawab dengan sebisa mungkin. Keep smile and jangan tegang! sengihnampakgigi

Tidak ada komentar:

Poskan Komentar