Tugas 3 Heap untuk antrian SIM di KOMDAK |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kantor KOMDAK di suatu
daerah melayani pembuatan SIM dari jam 10.00 sampai
dengan jam 15.00. Para pendaftar SIM di kantor ini
diproses per batch/kelompok. Artinya, setiap 30 menit
akan ada batch/kelompok yang SIM-nya telah selesai dibuat
dan dapat diambil. Setiap batch paling banyak ada 5
orang. Batch pertama keluar jam 10.00, berikutnya jam
10.30, lalu jam 11.00, seterusnya sampai batch terakhir
keluar pada jam 15.00. Jadi orang bisa mendaftar kapan saja antara jam 10.00 s/d jam 15.00, tapi dia harus menunggu sampai batch dikeluarkan sebelum SIM-nya bisa diambil. Idealnya, jika orang mendaftar pada jam X, maka SIM-nya bisa diambil pada batch pertama sesudah jam X tersebut. Misalnya, jika orang mendaftar pada jam 12.21, maka SIM-nya bisa diambil pada batch jam 12.30. Sayangnya, jumlah pendaftar seringkali melebihi kemampuan melayani SIM yang hanya 5 per batch, sehingga harus ada suatu sistim antrian. Sistem antrian pengolahan SIM di kantor KOMDAK ini memiliki sistem prioritas yang cukup menyedihkan: Prioritas tertinggi diberikan kepada orang yang membayar sogokan terbesar. Jika ternyata ada 2 orang yang jumlah sogokannya sama, barulah prioritas diberikan kepada orang yang datang lebih awal. Perhatikan bahwa tidak mungkin ada orang yang diproses sebelum dia memasukkan formulirnya! Misalnya: orang yang baru mendaftar pada jam 11.34 tidak mungkin ikut pada batch jam 11.30! Tidak ada 2 orang yang dapat mendaftar pada saat yang sama. Misalnya, A dan B mencoba sama-sama mendaftar pada jam 10.05. Paling-paling si A jam 10.05, lalu B jam 10.06. Dengan kata lain, anda *selalu* bisa menentukan prioritas siapa yang lebih tinggi. Jika ada orang yang sudah mendaftar, lalu pada 2 batch mendatang ia tidak diproses, maka ia akan menjadi marah. Jika ada orang yang marah, maka prioritasnya menjadi paling tinggi. Jika ada lebih dari satu orang yang marah, dilihat sogokannya lebih besar siapa. Kalau ternyata sogokannya sama, maka dilihat siapa yang datang lebih awal. Perhatikan bahwa bisa saja ada kemungkinan di mana orang yang marah tetap tidak dilayani. Tidak ada orang yang datang mendaftar tepat pada waktu batch diproses. Contoh: tidak mungkin ada orang yang mendaftar tepat jam 14.30. Paling-paling dia mendaftar pada jam 14.29, atau 14.31. Sebagai contoh, perhatikan data di bawah ini:
Dengan data di atas, maka 3 batch pertama adalah sebagai berikut:
Anda diminta untuk membuat sebuah program yang dapat menyelesaikan masalah pemrosesan batch ini. Gunakanlah sebuah priority queue yang diimplementasikan dengan sebuah Heap! Input anda berupa suatu file yang berisi data para pendaftar. Masing-masing baris mengandung data seorang pendaftar, dengan urutan: jam mendaftar, nama, lalu besar sogokan. Setiap data ini dipisah oleh karakter titik koma (;). Contoh file input untuk contoh data di atas: 1003;Driyardito;0 1006;Erio Prihastono;5000 1010;Rolis Kartiko;0 1020;Alfian;1000 1023;Hiro Wardhana;0 1029;Cahyanti Oktavia;1500 1032;Luthfy Ardiansyah;100 1037;Rini Dyah Astuti;2000 1044;Nisfia Marliani;1000 1045;Ronggo Gundala;10000 1057;Donny Darmawan;2000 1106;Buyung Pamungkas;20.000 1108;Dewi Utami Savitri;20.000 1112;Eko Prasetio;19.500 1120;Thomas Alfa Victorio;20.000 1134;Dave Basita;20.000 Perhatikan bahwa file input pasti terurut berdasarkan waktu datangnya pendaftar. Jadi program anda tinggal membaca baris-per-baris lalu meng-insertnya ke dalam priority queue. Jika ternyata sudah waktunya untuk melakukan pemrosesan suatu batch, anda tinggal me-remove item sebanyak 5 kail dari priority queue. Mudah saja! Output yang diharapkan adalah file yang berisi nama-nama pendaftar pada setiap batch, dan kalau ada, nama-nama pendaftar yang sampai batch terakhir (jam 15.00) tidak bisa dilayani. Contohnya: BATCH 10.30: Erio Prihastono Cahyanti Oktavia Alfian Driyardito Rolis Kartiko BATCH 11.00: Ronggo Gundala Rini Dyah Astuti Donny Darmawan Nisfia Marliani Luthfy Ardiansyah BATCH 11.30: Hiro Wardhana Buyung Pamungkas Dewi Utami Savitri Thomas Alfa Victorio Eko Prasetio dan kalau ada, file anda harus diakhiri dengan daftar berikut: YANG TIDAK SEMPAT DILAYANI: Anda harus mengimplementasikan Priority Queue anda sebagai sebuah ADT yang terpisah di file lain. Sediakan sebuah file header yang berisi interface dari fungsi-fungsi ADT Priority Queue. Program antrian SIM KOMDAK anda tinggal memanggil fungsi-fungsi yang tersedia di interface tersebut. Untuk contoh, coba lihat implementasi ADT List, Stack, dan Queue yang terdapat di buku Standish atau di http://www.cs.ui.ac.id/kuliah/IKI10100 Anda bebas untuk memilih cara representasi heap: apakah dengan representasi sekuensial (array), atau dengan representasi linked (pointer). Selamat mengerjakan tugas! |
klik di sini untuk download file
Microsoft Word dari tugas 3 (tugas3.doc)
klik di sini untuk kembali ke halaman
utama...