Hari: 6 April 2012

Struktur Data 15

Kita bisa melihat bahwa

Tumpukan merupakan suatu senarai (list) yang mempunyai watak “masuk terakhir keluar pertama” (last in first out – LIFO).
Tumpukan adalah kumpulan data. Kita bisa menggunakan larik untuk menyajikan sebuah tumpukan.
PR buatlah program untuk menyusun permutasi dalam bahasa C++

Struktur Data 14

Tumpukan (stack)

Pengertian: secara sederhana, tumpukan bisa diartikan sebagai kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain.
Kita bisa menambah (menyisipkan) data dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack).
Contoh
Misalnya kita mempunyai dua kotak yang ditumpuk sehingga satu kotak diletakkan di atas kotak yang lain. Jika kemudian tumpukan 2 kotak itu kita tambah dengan kotak ke-3, ke-4, dst maka akan kita peroleh sebuah tumpukan kotak terdiri atas N kotak.
Ujung yang manakah yang kita anggap sebagai ujung atas tumpukan? Kita harus menentukan ujung mana yang digunakan untuk mengambil atau menyisipkan data yang baru.

Struktur Data 13

Menyusun permutasi

Dari sekelompok karakter. Contoh, jika kita mempunyai 3 buah karakter yaitu A,B,C, maka semua permutasi yang mungkin dari ketiga karakter adalah
ABC, BAC, CAB
ACB, BCA, CBA
Secara umum, banyaknya permutasi dari N buah karakter adalah N faktorial à 3! = 6.
Proses penyusunan permutasi
Cetak elemen ke-1, dan cetak permutasi elemen ke-2 sampai ke-N (permutasi dengan N-1 elemen).
Cetak elemen ke-2, dan cetak permutasi elemen ke-1, elemen ke-3 sampai ke-N (permutasi dengan N-1 elemen).
Dan seterusnya sampai langkah terakhir adalah cetak elemen ke-N, dan cetak permutasi elemen ke-1 sampai elemen ke-(N-1) [permutasi dengan N-1 elemen].

Struktur Data 12

Secara umum

Untuk menyelesaikan N buah piringan diperlukan pemindahan sebanyak 2^N -1 kali.
Secara sederhana, pemindahan seluruh piringan secara rekursif dapat dilaksanakan dengan:
1) Pindahkan (N-1) piringan yang paling atas dari tonggak asal (A) ke tonggak bantu (B).
2) Pindahkan piringan ke-N (piringan terakhir) ..
… Dari tonggak asal (A) ke tonggak tujuan (C).
3) Pindahkan (N-1) piringan dari tonggak bantu (B) ke tonggak tujuan (C).
Tentu saja piringan sebanyak (N-1) buah tidak boleh dipindah bersama-sama, tetapi harus satu per-satu. Dengan cara yang sama seperti di atas, bisa dipindahkan ke (N-1) piringan, satu piringan setiap saat, dari tonggak asal (A) ke tonggak bantu (B).

Struktur Data 11

MENARA HANOI

Permainan ini adalah contoh klasik dari proses rekursif. Berdasarkan legenda, pertama kali dimainkan secara manual oleh seorang Pendeta Budha di Hanoi.
Dalam permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu tonggak ke tonggak lainnya dan diperbolehkan melewati tonggak bantuan.
Aturannya?
Aturan permainan menara Hanoi
Semua piringan pada tonggak A akan dipindahkan ke tonggak C dengan ketentuan bahwa pemindahan piringan dilakukan satu per-satu dan piringan yang lebih besar tidak boleh diletakkan di atas piringan yang lebih kecil.
Menurut legenda dikatakan bahwa jika anda selesai memindahkan seluruh 64 piringan, pada saat itu juga dunia kiamat. Bayangkan jika untuk setiap pemindahan perlu satu detik.

Struktur Data 10

Proses rekursi di program p_318b

Mempunyai kondisi pengakhiran rekursi yaitu jika nilai n sudah lebih kecil atau sama dengan nol. Setiap kali fungsi memanggil dirinya sendiri, nilai dari n dikurangi dengan nilai satu, sehingga nilai n akhirnya akan menjadi nol dan proses rekursi akan diakhiri, sehingga fungsi ini akan memanggil dirinya sendiri sebanyak n kali.
Program di p_319 merupakan program menghitung n! Yang akan dikerjakan secara rekursi.
Program di p_322 merupakan
Program untuk mengurutkan data dengan metode quick sort yang dilakukan secara rekursi. Metode ini menggunakan teknik memecah data menjadi partisi-partisi sehingga metode ini disebut dengan nama metode pengurutan pertukaran partisi (partition exchange sort).
Proses pengurutan dimulai dengan memilih sebuah elemen secara sembarang. Di program, elemen yang dipilih adalah elemen terbawah.