modul pembinaan olimpiade bidang komputer.docx
TRANSCRIPT
MODUL PEMBINAAN OLIMPIADE BIDANG KOMPUTER
(OSK/OSP/OSN)
Oleh :
Anifuddin Azis, S.Si., M.Kom.
BAB I
PENDAHULUAN
Selain sebagai ajang prestasi tingkat nasional, OSN bertujuan juga untuk
mendapatkan calon peserta pembinaan dan seleksi lebih lanjut hingga dipilih empat siswa
terbaik untuk menjadi anggota TOKI (Tim Olimpiade Komputer Indonesia). Mereka itulah
yang akan mewakili negara dan bangsa untuk bertanding di tingkat dunia yaitu International
Olympiad in Informatics (IOI).
IOI adalah ajang kompetisi pemrograman di tingkat Internasional yang sudah
berlangsung sejak 1985. Indonesia mulai mengikuti IOI sejak 1995. Saat ini IOI diikuti oleh
80-an negara (termasuk semua negara maju) sehingga IOI merupakan lomba paling akbar
dalam bidang ini untuk tingkat SMA.
Dalam perjalanannya problem-problem yang diberikan mengalami peningkatan
tingkat kesulitannya terutama sejak akhir tahun 90-an, hingga pada saat ini pemrograman
hanya satu aspek kecil semata di dalam lomba ini. Dengan demikian, aspek utama yang diuji
adalah kemampuan menyelesaikan masalahnya sendiri. Sehingga bisa dikatakan bahwa
kompetisi IOI adalah menguji kemampuan peserta dalam problem solving dengan
pemrograman komputer. Setiap peserta dalamwaktu yang amat terbatas harus
mengerjakan sejumlah masalah yang diberikan dengan menyusun program yang
menyelesaikan masalah tersebut.
Proses seleksi OSN bidang Komputer idealnya adalah mengacu model IOI di atas
yaitu problem solving dengan pemrograman. Namun, berbeda dengan bidang OSN lain
seperti Fisika, Matematika, Kimia dan Biologi, bidang Informatika khususnya pemrograman
belum menjadi pelajaran resmi. Oleh sebab itu, materi uji IOI “diterjemahkan” ke dalam
materi yang menguji potensi akademis/skolastik tinggi yang relevan dengan aspek-aspek di
atas. Diharapkan dari proses seleksi ini, siswa yang berpotensi walaupun belum mahir dalam
pemrograman dapat terjaring untuk diberikan pembinaan yang intensif di Pelatnas.
Aspek yang sangat bergantung pada ketrampilan peserta dalam pemrograman
dikurangi dan digantikan dengan materi uji “analisa dan logika” dan materi uji kemampuan
algoritmika.
Tingkatan seleksi OSK-OSP dibedakan atas komposisi dari ketiga komponen materi
uji:
• Kemampuan analitika/logika/aritmatika (nonprogramming)
• Kemampuan algoritmika (programming)
Komponen uji pemrograman tidak mungkin untuk diadakan sehingga digantikan
dengan kemampuan dan algoritmika saja.
Metoda pengujiannya pun tidak bisa dihindari bersifat test obyektif (pilihan ganda).
Metoda ini memang banyak sekali kelemahannya yaitu memungkinkan jawaban asal tapi
benar, namun, memungkinkan pemeriksaan yang segera dan efisien. Dampak negatif
tersebut bisa
dikurangi dengan pembuatan soal dan pilihan jawaban yang dirancang dengan matang.
Komposisi analitika/logika di tingkat kabupaten/kota adalah yang paling besar.
Di tingkat propinsi pada dasarnya sama dengan di tingkat kabupaten/kota kecuali
komposisi algoritmika diperbesar dan sifat tesnya diganti dari tes obyektif menjadi test
essay. Ini adalah untuk memacu peserta yang lolos di tingkat kabupaten/kota untuk
memperdalam pemahamannya dan ketrampilan prakteknya dalam pemrograman dan tidak
asal benar tetapi benar-benar memahami algoritma dan pemrograman.
Materi uji tingkat OSN adalah mirip dengan di tingkat IOI. Peserta yang lolos ke
Tingkat Pelatihan Nasional (Pelatnas) diharapkan merupakan peserta yang memiliki
kemampuan analitikal dan merancang algoritma yang tinggi. Referensi mengenai hal
tersebut jauh lebih sulit ditemukan daripada referensi untuk pemrograman itu sendiri.
(Sumber : TOKI, Buku Panduan Olimpiade Sains Bidang Komputer)
BAB II
ANALISA LOGIKA
Dalam pemodelan masalah pemrograman selain dengan model aritmatika, juga
keterhubungan antara entitas/aspek dalam masalah perlu dipahami secara relational untuk
mendapatkan model algoritmis yang lebih akurat. Kemampuan analitis tsb diperlukan dalam
menghasilkan model keterhubungan/relasional tsb. Sayangnya tidak ada metodologi yang
sistematik karena pada dasarnya sangat bergantung pada kreatifitas peserta uji. Namun, ada
kesamaan umum dalampemecahan masalahnya, yaitu :
• penggunaan model diagram sangat membantu untuk menggambarkan keterhubungannya
secara menyeluruh berdasarkan keterhubungan yang fragmental (dari pernyataan-
pernyataan terpisah atau asumsi-asumsi yang dibuat),
• keterhubungan itu sendiri seringkali bersifat implisit sehingga perlu pemahaman yang
hati-hati dan perlu pemahaman akan gaya bahasa “penceritaannya”,
• khususnya untuk asumsi yang dibuat segera dieliminasi jika kontradiksi dengan model
diagram, dan
• model diagram yang telah dibentuk perlu diverifikasi (dikaji ulang) dengan pernyatan-
pernyataan yang diberikan agar terjaga konsistensi, dan
• Selalu berpikir adanya kemungkinan yang tertinggal atau tersamar yang belum dikaji ke
dalam model
Contoh :
1. Terdapat 7 bilangan bulat A, B, C, D, E, F, dan G yang jika diurutkan membentuk deret
bilangan cacah berurutan (misalnya 4,5,6,…) dengan pernyataan-pernyataan berikut:
(1) D berharga 3 kurangnya dari A
(2) B adalah angka di tengah jika semua diurutkan
(3) Kurangnya F dari B = kurangnya D dari C
(4) G lebih besar dari F
Jika diurutkan, urutannya adalah?
Untuk memudahkan urutan tsb misalnya [x1–x2–x3–x4–x5–x6–x7]
Dari perny. (2) diketahui x4=B, maka menjadi [x1–x2–x3–B–x5–x6–x7]
Dari perny. (3) F berada di ruas sebelah kiri B (bisa x1, x2 atau x2).
Jika F=x1 maka D adalah x2 dan C adalah x5 ([F–D–x3–B–C–x6–x7]), atau D adalah x3 dan C
adalah x6 ([F–x2–D–B–x5–C–x7]).
Akan tetapi dari perny. (1) membatalkan kedua kemungk. asumsi ini karena A harus berada
3 posisi di kanan D yang sudah ditempati C.
Jika F=x2 maka
D adalah x1 dan C adalah x3 ([D–F–C–B–x5–x6–x7]), atau
D adalah x3 dan C adalah x5 ([x1–F–D–B–C–x6–x7]), atau
D adalah x5 dan C adalah x7 ([x1–F–x3–B–D–x6–C]).
Akan tetapi dari perny. (1) hanya yang kedua yang mungkin karena yang pertama posisi A =
posisi B atau yang ketiga posisi A berada di luar (setelah x7). Untuk sementara
[x1–F–D–B–C–A–x7] dicatat sebagai salah satu solusi.
Jika F=x3 maka
D adalah x1 dan C adalah x2 ([D–C–F–B–x5–x6–x7]), atau
D adalah x5 dan C adalah x6 ([x1–x2–F–B–D–C–x7]), atau
D adalah x6 dan C adalah x7 ([x1–x2–F–B–x5–D–C]).
tetapi dari (1) semua tidak mungkin (yang pertama posisi A = posisi B, kedua
yang lain posisi A ada di luar).
Jadi ternyata hanya tinggal satu kemungkinan yaitu [x1–F–D–B–C–A–x7].
Dari perny. (4) diperoleh G=x7, sehingga diperoleh juga E=x1. Hasilnya
diketahui urutannya adalah E, F, D, B, C, A, G
2. Delegasi-delegasi dari negara W dan negara R duduk berhadap-hadapan pada meja
perundingan. Masing-masing delegasi terdiri atas seorang ketua, dua atase militer dan dua
wakil kamar dagang negara masing-masing. Delegasi W beranggotakan A, B, C, D, dan E.
Delegasi R beranggotakan F, G, H, I, dan J. Masing-masing delegasi berada pada sisi-sisi
memanjang berlainan (satu negara pada sisi yang sama dan ketua duduk di tengah
delegasinya). Batasan dalam mengatur urutan duduk mereka:
(1) Delegasi W menempatkan A dan B di kedua ujung barisannya.
(2) Kuping kanan G tuli shg ia harus paling kanan dari delegasi R.
(3) Baik D maupun F bukan ketua.
(4) Para atase militer W, salah seorangnya B, didudukkan berdampingan, dan
tidak ada satupun yang berseberangan dengan atase militer R
(5) G bukan atase militer.
(6) C wakil dari kamar dagang, duduk berseberangan dengan H.
Manakah yang paling mungkin mengenai F berikut?
(A) Wakil kamar dagang yang duduk di sebelah I
(B) Wakil kamar dagang yang duduk di sebelah H
(C) Wakil kamar dagang yang duduk berseberangan dengan B
(D) Atase militer yang duduk di sebelah I
(E) Atase militer yang duduk di sebelah J
Seperti pada contoh sebelumnya, dibuat diagram sbb
x1–x2–x3–x4–x5 negara W
y1–y2–y3–y4–y5 negara R
Dari (1) kemungkinan {x1,x5} adalah {A,B} atau {B,A}
Dari (2) maka y5=G yang karena pernyataan (4) dan (5) (G bukan a.m dan B
adalah a.m) menyebabkan x5=B, sehingga (atase militer dengan bold)
A –x2–x3–x4 –B
y1–y2–y3–y4–G
Dari pernyataan (6) dan (4) diperoleh C = x2 dan y2 = H, sehingga
A –C–x3–x4 –B
y1–H–y3–y4–G
Dari pernyataan (3) dan diagram di atas D = x4 dan F = y1 atau y4
A –C –E –D –B
y1–H –y3–y4–G
Jadi tinggal 2 kemungkinan F=y1 (atase militer), atau F=y4 (wakil kamar dagang). Jika atase
militer maka (D) dan (E) salah karena sebelah y1 adalah H. Jika wakil kamar dagang maka (B)
salah karena H atase militerdan (C) salah karena B ada di depan G. Jadi tinggal pilihan (A)
yang paling mungkin.
(Note: ini bukan satu-satunya kemungkinan. Kemungkinan lainnya masih adatapi tidak ada
di kelima pilihan itu).
(Sumber : TOKI, Buku Panduan Olimpiade Sains Bidang Komputer)
Latihan :
1. Fredy, Cindy, dan Sandy masing-masing memiliki dua ekor hewan peliharaan. Salah satu
diantara mereka tidak memelihara anjing. Cindy satu-satunya yang memiliki kucing.
Sandy memelihara anjing. Fredy dan cindy masing-masing memelihara kelinci. Siapa
yang memlihara kura-kura ?
2. Terdapat 7 bilangan bulat A-G, yang jika diurutkan membentuk deret bilangan cacah
berurutan dengan pernyataan-pernyataan berikut ini:
a. D berharga 3 kurangnya dari A
b. B adalah angka di tengah bila semua diurutkan
c. Kurangnya F dari B = kurangnya D dari C
d. G lebih besar dari F
Bila diurutkan, urutannya adalah ?
Di sebuah daerah, ada tepat 5 buah sungai, bernama A, B, C, D, E dan tepat 5 buah kota, bernama F, G, H, I, J. Kota F, H, dan J masing-masing dialiri oleh 3 buah sungai. Sungai B, C, dan D masing-masing mengaliri 2 buah kota. Kota I hanya dialiri oleh sungai B dan E, dan kota G hanya dialiri oleh sungai D dan A. Jika sebuah sungai yang mengaliri sebuah kota meluap, maka kota tersebut akan kebanjiran. 3. Jika ada tepat 4 kota yang kebanjiran, berapa jumlah minimal sungai yang meluap? 4. Jika semua sungai-sungai yang mengaliri kota F meluap, berapa banyak minimal kota
yang kebanjiran? 5. Jika kota H dialiri oleh sungai A, C, dan E, sungai manakah yang tidak mugkin mengaliri F
dan J sekaligus? 6. Jika sungai A mengaliri tepat 4 kota di daerah tersebut, berapa kota yang dialiri oleh
sungai E?
Sebuah alat musik baru sedang dibuat.Musik hanya akan membunyikan 5 nada saja; do,
re,mi, fa dan sol. Terdapat dua tombol untuk membunyikan nada-nadanya: tombol
merah dan tombol putih.Nada yang akan dibunyikan saat penekanan suatu tombol
tergantung pada nada sebelumnya dan tombola apa yang ditekan. Pada saat dihidupkan
alat musik dalam keadaan reset. Seperti tabel berikut (sementara, pada saar dihidupkan
maka mesin akan langsung membunyikan nada do).
Nada
Sebelumnya
Setelah menekan tombol merah Setelah menekan tombol
putih
Do Mi Re
Re Fa Mi
Mi Fa Mi
Fa Sol Fa
Sol mi Do
7. Jika ditekan 7 kali tombol putih setelah dihidupkan maka nada apa yang terakhir
terdengar?
8. Sejak nada do terakhir terdengar sedikitnya berapa kali penekanan yang harus dilakukan agar nada do kembali muncul?
BAB III
ARITMATIKA
Sekali lagi, walaupun mengambil topik mengenai aritmatika, aspek terpenting dari
materi ini bukan pada hitung menghitungnya tetapi pada uji kemampuan analitisnya. Aspek-
aspek analitis dalam persoalan aritmatika dijelaskan pada bagian berikut ini (Sumber : TOKI,
Buku Panduan Olimpiade Sains Bidang Komputer).
1. Mampu Membentuk Model Aritmatika/Matematika serta melakukan
deduksi/induksi Model
Dalam problem solving, seringkali diperlukan tahapan pemodelan masalah yang
sebagian menggunakan model matematika/aritmatika dan menyederhana-kannya sehingga
menjadi model yang lebih sederhana dan siap dikomputasikan dalam bentuk algoritma.
Model yang tidak tepat berakibat pada kegagalan dalam pemecahan masalah.
Contoh:
Uang Amir lebih banyak dari uang Ali. Jika dijumlahkan uang keduanya lebih dari 50 ribu
rupiah, sementara selisih uang Amir dengan uang Ali lebih dari 30 ribu rupiah. Berapakah
kemungkinan uang Amir yang paling tepat?
Model permasalahan: Uang Amir = x, Uang Ali = y, dan dari deskripsi di atas
• Pers-I: x > y
• Pers-II: x+y > 50000
• Pers-III: |x-y| > 30000
Dari Pers-I dan Pers-III: menghasilkan Pers-IV: x-y > 30000
Dari Pers-II dan Pers-IV: jika dijumlahkan menghasilkan 2x>80000.
Maka, x > 40000
2. Memahami Sifat-sifat Bilangan
Untuk sejumlah masalah, sifat-sifat dari bilangan harus dipahami secara logis
Contoh:
Jika n dan p adalah dua bilangan bulat, dan n + p berharga ganjil, manakah dari berikut ini bil
ganjil?
(A) n – p + 1
(B) np
(C) n2 + p2 – 1
(D) 3p + 5n
(E) (p – n)(n – p)
A bukan, karena (n+p) adalah ganjil maka dari n dan p salah satu ganjil dan yang lain genap.
Selisih antara n dan p pasti ganjil sehingga jika ditambah 1 menjadi genap.
B bulan karena perkalian antara suatu bilangan genap dengan bilangan apapun akan
menjadi genap.
C bukan karena pangkat bulat positif berapapun dari bilangan genap, tetap genap, dan ganjil
tetap ganjil, kemudian ganjil ditambah genap dan dikurang ganjil menjadi genap.
D bukan karena pangkat bulat positif berapapun dari bilangan ganjil tetap bilangan ganjil,
dan jumlah dua bilangan ganjil menjadi genap.
E benar, karena perkalian antara dua bilangan ganjil menghasilkan bilangan ganjil.
3. Mengkaitkan dengan Konteks Masalah
Konteks dari soal perlu diperhatikan dan konteks tersebut kadang-kadang hanya
tersirat saja. Yang dimaksud dengan konteks di sini adalah pemahaman umum akan sesuatu
yang sewajarnya diketahui pula.
Contoh:
jika lonceng berdentang setiap 1 detik, dalam jumlah dentang yang sesuai waktu yang
ditunjukkan, maka tepat pada pukul berapa dentang terakhir yang menunjukkan jam 6?
Apakah pukul 6:00:06?
Salah, seharusnya pukul 6:00:05 karena dentang-dentang tsb pada pukul 6:00:00, pukul
6:00:01, pukul 6:00:02, pukul 6:00:03, pukul 6:00:04 dan pukul 6:00:05!! Konteks disini
adalah dentang pertama terjadi pada tepat pukul 6, dan penomoran detik/menit dimulai
dari 0, 1, ... dst.
4. Memahami Formula Rekursif
Banyak masalah pemodelan dengan tingkat kesulitan yang tinggi atau
pemrogramannya sendiri memerlukan pemecahan dengan algoritma rekursif. Pemahaman
fungsi rekursif membantu dalam pemahaman memahami bagaimana bekerjanya algoritma
rekursif.
Contoh:
Jika didefinisikan f(n) = n f(n–1) untuk setiap n > 0 dan f(0) = 1, maka berapakah f(10)/(f (7) x
f(6))?
Pahami perilaku fungsi rekursif tsb, sbb,
f(n) = n.f(n–1) = n.(n–1).f(n–2) = n.(n–1).(n–2).f(n–3) = ... = n(n–1)(n–2)(n–
3)....2.1 = n!
Sehingga, f(10) = 10! dan f(7) = 7! serta f(6) = 6!.
10!/7! = (10.9.8.7.6.5.4.3.2.1)/(7.6.5.4.3.2.1) = 10.9.8
Dan (10.9.8) /(6.5.4.3.2.1) = 1
5. Eksplorasi dalam Masalah Kombinatorik
Dalam problem solving seringkali masalah yang diberikan bersifat kombinatorik
(mendapatkan setiap kemungkinan kombinasi/permutasi jawaban). Untuk memecahkannya
terkadang seluruh kemungkinan tersebut harus diperiksa untuk mendapatkan pemecahan
yang umum.
A. Kaidah Menghitung
Misalkan ada n percobaan, masing-masing dg pi hasil (Rinaldi Munir, 2005)
Kaidah perkalian (rule of product)
o p1 ´ p2 ´ … ´ pn hasil
Kaidah penjumlahan (rule of sum)
o p1 + p2 + … + pn hasil
Contoh :
Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri)
yang
(a) semua angkanya berbeda
(b) boleh ada angka yang berulang.
Penyelesaian:
(a) posisi satuan: 5 kemungkinan angka (1, 3, 5, 7, 9) posisi ribuan: 8 kemungkinan angka
posisi ratusan: 8 kemungkinan angka posisi puluhan: 7 kemungkinan angka
Banyak bilangan ganjil seluruhnya = (5)(8)(8)(7) = 2240 buah.
(b) posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9); posisi ribuan: 9
kemungkinan angka (1 sampai 9)
posisi ratusan: 10 kemungkinan angka (0 sampai 9)
posisi puluhan: 10 kemungkinan angka (0 sampai 9)
Banyak bilangan ganjil seluruhnya = (5)(9)(10)(10) = 4500
B. Permutasi
Definisi. Permutasi r dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang
dipilih dari n buah elemen, dengan r ≤n, yang dalam hal ini pada setiap kemungkinan urutan
tidak ada elemen yang sama.
P (n , r )=n (n−1 ) (n−2 )… (n−(r−1 ))= n !(n−r )!
Contoh 1:
Tulislah semua permutasi 3 objek {a, b, c} !
Penyelesaian :
Permutasi yang mungkin dari 3 objek {a, b, c} ada 3! = 6 kemungkinan yaitu : abc, acb,
bac, bca, cba, cab.
Contoh 2:
Suatu undian dilakukan s\dengan menggunakan angka yang terdiri dari 7 digit. Jika
digit-digit dalam suatu angka diharuskan berbeda satu dengan yang lain, ada beberapa
kemungkinan nomor undian ?
Penyelesaian :
Dalam undian tersebut, jelas urutan kemunculan angka-angka diperhatikan. Undian dengan
nomor 1234567 akan berbeda dengan nomor 7654321. Karena digit-digitnya diharuskan
selalu berbeda, maka banyaknya kemungkinan nomor undian adalah
P(10 ,7)=10 !3 !
=10 x 9 x 8 x 7 x 6 x 5 x 4 = 604800 macam kemungkinan.
C. Permutasi dengan Ada Elemen yang Sama
Secara umum, jika suatu himpunan terdiri dari n objek yang tersusun dari :
n1 buah objek sama jenis-1
n2 buah objek sama jenis-2
....
....
nk buah objek sama jenis-k.
dengan n1 + n2 + n3 +…+ nk = n
Maka banyaknya permutasi berbeda yang mungkin dari n objek tersebut adalah :
(n ¿ ) ¿¿
¿¿
Contoh 1 :
Ada berapa banyak cara yang mungkin dari kata MATEMATIKA ?
Penyelesaian :
Kata MATEMATIKA terdiri dari 10 karakter huruf, yang tersusun dari :
2 buah huruf M
3 buah huruf A
2 buah huruf T
1 buah huruf E
1 buah huruf I
1 buah huruf K
Sehingga banyaknya kemungkinan untuk membuat permutasi adalah :
10 !2 ! 3 ! 2 ! 1 ! 1 ! 1 1
=10 . 9 .8 . 7 .6 . 5 .41.2 .1 . 2.1.1 .1 .1
=6048004
=151200 banyaknya cara menyusun elemen-
elemen tersebut.
D. Kombinasi
Misalkan himpunan S mempunyai | S | = n elemen. Banyaknya himpunan bagian S yang
terdiri dari k (k≤n )disebut kombinasi n objek yang diambil sebanyak k objek sekaligus.
Simbolnya adalah
(n ¿ ) ¿¿
¿¿ atau C(n, k) atau nCk. Banyaknya kombinasi yang dimaksud dapat
dinyatakan dalam persamaan C (n, k )= Ck
n=n !(n-k )! k!
Contoh 1 :
Seorang pelatih bola basket akan memilih komposisi pemain yang akan diturunkan
dalam suatu pertandingan. Ada 12 orang pemain yang dapat dipilihnya. Berapa macam tim
yang dapat ia bentuk ?
Penyelesaian :
Dalam memilih pemain yang akan diturunkan, urutan pemilihan tidaklah diperhatikan.
Jadi, yang menjadi masalah hanyalah siapa yang dipilih. Tidak menjadi masalah apakah
seorang pemain (katakanlah A) terpilih pertama ataupun terakhir. Hal ini berbeda dengan
pemilihan ketua dan wakil ketua. Komposisi yang dibuat apabila seseorang (misalnya B)
yang terpilih pertama (menjadi ketua) akan berbeda apabila B terpilih kedua (menjadi wakil
ketua).
Jadi banyaknya tim yang dapat dibentuk oleh pelatih tersebut adalah kombinasi 12
objek yang diambil 5 sekaligus adalah sebagai berikut:
(12 ¿ )¿¿
¿¿tim.
E. Kombinasi dengan Pengulangan
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak .
Masing-masing kotak hanya boleh diisi paling banyak satu buah bola. Maka Jumlah
cara memasukkan bola : C(n,r)
Masing-masing kotak boleh diisi lebih dari satu buah bola. Maka Jumlah cara
memasukkan bola : C(n+r-1,r)= C(n+r-1,n-1)
Contoh :
Pada persamaan x1+ x2+x3+x4=12 , x iadalah bilanganbulat≥0. Berapa jumlah
kemungkinan solusinya ?
Penyelesaian :
Kombinasi dengan pengulangan, jadi C(4+12-1,12) = 455 kemungkinan solusi.
6. Berpikir secara “Cerdas”
Jika menghadapi suatu masalah komputasi yang kelihatannya tidak mungkin, pasti
ada sesuatu di balik itu!! Dapatkanlah dengan bantuan pemahaman akan sifat-sifat operasi
aritmatika untuk mendapatkan model matematis yang lebih sederhana.
Contoh 1:
Berapa digit terakhir dari 22003? Apakah anda ingin menghitungnya sendiri(secara manual)?
Tentu tidak, pasti ada penyederhanaannya. Dengan mengubah n=1, 2, 3, …, dst, perhitungan
2n menghasilkan deret 1, 2, 4, 8,
16, 32, 64, 128, 256, 512, 1024, 2048, 4096, dst. Amati angka terakhir dari setiap bilangan,
kita mendapatkan perulangan dari 6 – 2 – 4 – 8 pada n mod 4 = 0, 1, 2, 3. Jadi jika n=2003,
diperoleh 2003 mod 4 = 3, yaitu memiliki digit terakhir 8.
Contoh 2:
Ketiga digit awal dari hasil perkalian 22002 x 52005 jika dijumlahkan adalah? Ini juga tidak
mungkin dihitung manual. Perhatikan bilangan dasarnya 2 dan 5 yang jika dikalikan menjadi
10. Karena setiap pasang faktor 2 dan 5 menghasilkan 10 berarti hanya menambah 0 di digit
terkanan. Ada 2002 pasang faktor-faktor tsb sehingga 22002 x 52005 = 53 x 102002= 125 x 102002.
Penjumlahan tiga digit awal 1+2+5=8
Contoh 3:
Hitunglah (80! x 38!) /(77! x 40!).
Menggunakan sifat sbb untuk a dan b bulat positif, a > b, maka a!/b! = a.(a – 1).(a – 2)…(b +
1). Maka:
(80! x 38!) /(77! x 40!) = (80!/77!) / (40!/38!)
= (80x79x78) / (40x39)
= (80/40) x (78/39) x 79
= 2 x 2 x 79 = 316
yang dapat dihitung tanpa kalkulator.
Latihan
1. Digit terakhir dari 27001 adalah?
2. Jika 22 x 5 = 4x5 = 20 memiliki digit 2 dan 0 sehingga jumlahnya adalah 2+0=2. Maka
berapakah jumlah semua digit untuk nilai 22005x52007?
3. Jika 4!=4x3x2x1=24. Maka nilai digit terakhir dari (1!+2!+3!+4!+….+999!) dikalikan
dengan 7 adalah?
4. Nilai dari 20022007 x 30052008 dibagi 100 menghasilkan sisa pembagian?
5. Suatu seri angka terdiri dari 4 10 8 14 12 18 angka selanjutnya adalah…
6. Hasil dari 2 – 3 + 4 – 5 + 6 – ... + 1000 adalah?
7. Sebanyak 3/5 dari peserta kompetisi Pemrograman dan Logika adalah pria. Sebanyak
¼ peserta adalah wanita yang belum memiliki pacar. Bila ada 42 orang peserta wanita yang
sudah memiliki pacar, maka jumlah seluruh peserta kompetisi tersebut adalah … orang.
8. Usia seorang ayah sekarang adalah tiga kali usia anaknya. Dua belas tahun yang lalu
usia ayah enam kali usia anaknya. Tentukan usia mereka saat ini.
9. Wagimin menghabiskan
16 masa hidupnya sebagai anak,
112 hidupnya sebagai
pemuda, kemudian menikah setelah umurnya bertambah
17 hidupnya. 5 tahun kemudian,
anaknya lahir. Namun sayangnya, anaknya mati muda. Umur anak Wagimin hanya setengah
dari umur bapaknya. Karena depresi yang berat setelah kematian anaknya, 4 tahun
kemudian Wagimin pun meninggal. Berapa umur Wagimin sebenarnya ? (OSN 2010)
10. Berapa banyak bilangan yang bisa dibagi 8 atau enam diantara satu hingga 2010?
11. Berapa banyaknya bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999
itu sendiri) yang semuanya angka berbeda?
12. Seorang tukang cat dapat mengerjakan pengecatan suatu ruangan dalam x jam.
Tepat pada jam ke 2, catnya habis sehingga terpaksa menunggu kaleng cat berikutnya yang
sedang dipesan. Berapa bagiankah pekerjaan yang belum ia selesaikan?
13. Sebuah lembaga sepak bola mengadakan survey kepada para pelajar di sebuah
sekolah, untuk mengetahui seberapa populer olahraga sepak bola di antara remaja putra
dan putri. Dari 100 pelajar yang disurvey, ternyata banyaknya remaja putra yang menyukai
sepak bola sama banyak dengan banyaknya remaja putri yang tidak menyukai sepak bola,
dan perbandingan antara banyaknya remaja putra yang menyukai sepak bola dan tidak
menyukai sepak bola adalah 3 : 1.Jika 52% pelajar yang disurvey adalah putri, ada berapa
pelajar putri yang menyukai sepak bola?
14. Sebuah truk pengangkut kelapa mengangkut sejumlah kelapa dan mengantarkannya
ke beberapa pos. Setiap kali truk berhenti di sebuah pos, truk wajib menurunkan separuh
muatannya (dibulatkan ke bawah). Sebagai imbalannya, pos tersebut akan menambahkan
satu butir kelapa ke dalam muatan truk. Jika pada awalnya sebuah truk mengangkut 10000
butir kelapa, berapakah jumlah kelapa yang tersisa di muatan truk ketika truk tersebut tiba
di pos ke 60?
15. Sebuah kereta bergerak meninggalkan sebuah stasiun dengan kecepatan 40 mil/jam.
Dua jam kemudian sebuah kereta yang lainnya berangkat dari stasiun yang sama dengan
kecepatan 60 mil/jam. Ketika kereta kedua dapat menyusul kereta yang pertama, berapakah
jaraknya dari stasiun ?
16. Dari 100.000 bilangan bulat positif pertama, berapa banyak bilangan yang
mengandung tepat 1 buah angka 3, 1 buah angka 4, dan 1 buah angka 5 ?
17. Berapa banyak string yang dapat dibentuk dari huruf-huruf kata “CONGRESS”
sedemikian hingga dua buah huruf “S” tidak terletak berdampingan ?
18. Pada persamaan x1+ x2+x3=10 , jika0≤ x1≤2 , x2>1dan x3≥0, maka banyaknya solusi
adalah…
19. Berapa banyak cara memasang 10 pesawat telepon di 10 ruang kantor, jika pesawat
telepon terdiri dari 4 berwarna merah, 3 warna putih, dan 3 warna biru ?
20. Sebuah data disimpan dalam 8 bit (0 dan 1), misal : 11110101. Ada berapa banyak
data 8 bit yang dimulai dengan 11 atau berakhir dengan 11 ?
BAB IV
STRUKTUR DASAR ALGORITMA
1. Struktur Runtunan
Sebuah runtunan (sequence) terdiri dari satu atau lebih instruksi. Tiap instruksi
dikerjakan sesuai dengan urutan penulisannya, yakni sebuah instruksi dilaksanakan setelah
instruksi sebelumnya selesai dilaksanakan. Urutan instruksi menentukan keadaan akhir
program. Bila urutannya diubah, maka hasil akhirnya mungkin juga berubah.
Contoh berikut adalah program menukar dua buah nilai integer A dan B. Misal
sebelum penukaran nilai A = 5, nilai B=3. Setelah penukaran, nilai A=3, nilai B=5.
Jika urutan instruksi di atas diubah, maka hasilnya juga berubah. Misal :
temp:=A;
A:=B;
B:= temp;
diubah menjadi :
temp:=A;
B:= temp;
A:=B;
2. Struktur Pemilihan
Program Tukar;
VAR A,B, temp : integer;
Begin
write(’Masukkan nilai A :’); readln(A);
write(’Masukkan nilai B :’); readln(B);
temp:=A; A:=B; B:= temp;
writeln(’Nilai A sekarang = ’, A);
writeln(’Nilai B sekarang = ’, B);
End.
Pada umumnya, masalah yang akan diselesaikan memiliki beberapa alternatif
pelaksanaan aksi. Suatu aksi akan dilaksanakan jika persyaratan atau kondisi dipenuhi.
Kondisi adalah sesuatu yang bernilai true atau false, disebut kondisi boolean. Contoh kondisi
:
x > y
m = n
k mod 4 = 0
not(ketemu)
Penentuan kondisi bolean dan aksi yang dilakukan bergantung pada jumlah kasus
yang terdapat pada masalah tersebut : satu kasus, dua kasus, atau lebih dari dua kasus.
Bentuk umum untuk kasus satu kasus :
if kondisi then aksi ;
Contoh program dengan satu kasus :
Program BilanganGenap;
Var Bil : integer;
Begin
write (‘Masukkan bilangan :’); readln(Bil);
if bil mod 2 = 0 then write (Bil,’ adalah bilangan genap’);
end.
Bentuk umum untuk kasus dua kasus :
if kondisi then aksi1
else aksi 2;
Contoh program dengan dua kasus :
Program BilanganGenapGanjil;
Var Bil : integer;
Begin
write (‘Masukkan bilangan :’); readln(Bil);
if bil mod 2 = 0 then write (Bil,’ adalah bilangan genap’)
else write (Bil,’ adalah bilangan ganjil’);
end.
Bentuk umum untuk kasus tiga kasus atau lebih :
if kondisi1 then aksi1
else if kondisi2 then aksi2
if kondisi3 then aksi3
....
else aksiN;
Contoh program dengan tiga kasus atau lebih:
Program KonversiNilai;
{Program untuk merubah nilai angka menjadi nilai huruf}
Var Nilai : integer;
Begin
write (‘Masukkan bilangan :’); readln(Nilai);
if Nilai>= 80 then write (‘Nilai =A’)
else if Nilai>= 65 then write (‘Nilai = B’)
else if Nilai>= 50 then write (‘Nilai = C’)
else if Nilai>= 35 then write (‘Nilai = D’)
else write (‘Nilai = E’);
end.
Untuk masalah dengan tiga kasus atau lebih, struktur Case dapat menyederhanakan
penulisan If-Then-Else yang bertingkat-tingkat seperti contoh di atas.
Struktur Case sebagai berikut :
Case (nama_variabel) of
nilai1 : aksi1;
nilai2 : aksi2;
...
nilaiN : aksiN;
else aksiN1;
Contoh program KonversiNilai menggunakan struktur Case :
Program KonversiNilai;
{Program untuk merubah nilai angka menjadi nilai huruf}
Var NilaiAngka : integer;
Begin
write (‘Masukkan bilangan :’); readln(NilaiAngka);
Case NilaiAngka of
80..100 : write(‘Nilai = A’);
65..79 : write(‘Nilai = A’);
50..64 : write(‘Nilai = A’);
35..49 : write(‘Nilai = A’);
0..34 : write(‘Nilai = A’);
else write(‘ Masukkan nilai salah’);
end.
Nilai bisa berupa nilai tunggal atau beberapa nilai yang disebutkan satu per satu, atau bisa
juga berupa jangkauan nilai.
3. Struktur Pengulangan
Struktur pengulangan secara umum :
<inisialisasi>
awal pengulangan
badan pengulangan
akhir pengulangan
<terminasi>
Awal dan akhir pengulangan tergantung pada struktur pengulangan yang digunakan.
Terdapat tiga macam struktur pengulangan, yaitu :
1. Struktur FOR
2. Struktur WHILE
3. Struktur REPEAT
Struktur FOR
Bentuk umum struktur FOR ada dua macam, yaitu : menaik atau menurun.
FOR menaik :
for pencacah := awal to akhir do
aksi;
Keterangan :
a. Pencacah haruslah dari tipe data yang memilik predecessor dan successor, yaitu integer,
karakter, subrange, dan enumerasi.
b. Aksi adalah satu atau lebih instruksi yang diulang. Jika ada lebih dari satu aksi, maka
dimulai dengan pernyataan BEGIN dan diakhiri dengan END; .
c. Nilai awal lebih kecil atau sama dengan nilai akhir.
d. Pada mulanya, pencacah diinisialisasi dengan nilai awal, kemudian secara otomatis
bertambah satu, sampai akhirnya nilai pencaca sama dengan nilai akhir.
e. Jumlah pengulangan adalah nilai akhir-nilai awal + 1.
Contoh program menghitung nilai faktorial.
Program HitungFaktorial;
Var i,n : integer;
Faktorial : longint;
Begin
write(‘Nilai faktorial berapa ?’); readln(n);
Faktorial :=1;
For i:= 1 to n do
Faktorial :=Faktorial * i;
write(‘Nilai faktorial ‘,N,’ adalah =’,Faktorial);
end.
FOR menurun :
Bentuk umum :
for pencacah := akhir downto awal do
aksi;
Keterangan :
a. Pencacah haruslah dari tipe data yang memilik predecessor dan successor, yaitu integer,
karakter, subrange, dan enumerasi.
b. Aksi adalah satu atau lebih instruksi yang diulang. Jika ada lebih dari satu aksi, maka
dimulai dengan pernyataan BEGIN dan diakhiri dengan END; .
c. Nilai awal lebih kecil atau sama dengan nilai akhir.
d. Pada mulanya, pencacah diinisialisasi dengan nilai akhir, kemudian secara otomatis
berkurang satu, sampai akhirnya nilai pencaca sama dengan nilai awal..
e. Jumlah pengulangan adalah nilai akhir - nilai awal + 1.
Struktur WHILE
Bentuk umum struktur WHILE :
while kondisi do
aksi;
Aksi akan dilaksanakan berulangkali selama kondisi bernilai true.
Contoh program menghitung nilai faktorial :
Program HitungFaktorial;
Var i,n : integer;
Faktorial : longint;
Begin
write(‘Nilai faktorial berapa ?’); readln(n);
Faktorial :=1; i:=1;
While i<=n do
begin
Faktorial :=Faktorial * i;
i:=i + 1;
end;
write(‘Nilai faktorial ‘,N,’ adalah =’,Faktorial);
end.
Struktur REPEAT
Bentuk umum struktur REPEAT :
Repeat
aksi;
Until kondisi;
Aksi akan dilaksanakan berulangkali sampai kondisi bernilai true.
Contoh program menghitung nilai faktorial :
Program HitungFaktorial;
Var i,n : integer;
Faktorial : longint;
Begin
write(‘Nilai faktorial berapa ?’); readln(n);
Faktorial :=1; i:=1;
Repeat
Faktorial :=Faktorial * i;
i:=i + 1;
Until i > n;
write(‘Nilai faktorial ‘,N,’ adalah =’,Faktorial);
end.
Latihan
1. Perhatikan algoritma di bawah ini:
Jika diberikan a, b, c ketiganya adalah 1, maka jika nilai n adalah 20, nilai satuan dari d pada
akhir algoritma adalah ...
2. Diberikan algoritma berikut:
Banyaknya karakter '*' yang dicetak ke layar adalah ...
3. Perhatikan potongan program berikut berikut ini :
for i := 1 to n do begin case x of
1 : x:= (x+22) mod 6; 2 : x := x*2; 3 : dec(x); 4 : x:= 5-x; 5 : x:= x shr 1 + 1; else x := (x*4) mod 5 + 1; end; writeln(x);
end;a. Berapa nilai x yang dicetak terakhir, jika harga mula-mula x = 31 dan n = 1000 ?b. Berapa kali angka 5 muncul pada pencetakan yang dilakukan jika harga mula-mula x = 103
dan n = 100 ?
Perhatikan algoritma berikut ini:
Jika nilai x, y, dan z diberikan masing-masing 2, 6, 21; nilai yang dicetak ke layar adalah…
BAB V
SUB PROGRAM
1. Sub Program
Dalam bahasa pemrograman prosedural, program bisa terdiri dari beberapa sub program.
Dengan membuat sub program, penulisan kode program yang sama berulangkali bisa
dihindarkan, juga memudahkan menulis dan menemukan kesalahan program.
Dalam Bahasa Pascal terdapat dua subprogram, yaitu Prosedur dan Fungsi. Sub
program ini hanya perlu ditulis sekali, tetapi dapat dipanggil berkali-kali oleh program utama
atau sub program lain.
2. Pendeklarasian Prosedur
Bentuk deklarasi prosedur (tanpa parameter) adalah :
Procedure NamaProsedur;
Bagian deklarasi;
Begin
Bagian pernyataan;
End;
Contoh :
Procedure HitungLuasSegitiga;
Var alas, tinggi, Luas : real;
Begin
write(‘Masukkan panjang alas segi tiga :’); readln(alas);
write(‘Masukkan tinggi segi tiga :’); readln(tinggi);
Luas:=(1/2)*alas*tinggi;
write(‘Luas segi tiga = ‘,Luas);
End;
A. Pemanggilan Prosedur
Prosedur bukan program yang berdiri sendiri, jadi tidak bisa dieksekusi secara
langsung. Prosedur baru dilaksanakan dengan cara memanggil namanya dari program
utama atau sub program lain.
Ketika nama prosedur dipangil, kendali program secara otomatis akan berpindah ke
prosedur tersebut. Instruksi di dalam prosedur dilaksanakan. Setelah semua selesai, kendali
program berpindah secara otomatis ke instruksi sesudah pemanggilan tersebut.
Contoh program utama untuk memanggil prosedur HitungLuasSegitiga di atas :
Begin
HitungLuasSegitiga;
End.
B. Variabel Global dan Lokal
Variabel yang dideklarasikan dalam prosedur hanya dikenal di badan prosedur
tersebut, sehingga disebut variabel Lokal.
Sedangkan variabel yang dideklarasikan di dalam program utama bersifat Global,
karena dikenali di semua bagian program.
Program TukarNilai;
Var A, B : integer; {A,B variabel global}
Procedure Tukar;
Var temp : integer;{temp variabel lokal}
begin
temp:= A;
A:= B;
B:=temp;
end;
Begin
write(‘Masukkan nilai A = ‘);readln(A);
write(‘Masukkan nilai B = ‘);readln(B);
Tukar;
writeln(‘Nilai A sesudah ditukar = ‘,A);
writeln(‘Nilai B sesudah ditukar = ‘,B);
End.
C. Parameter
Kebanyakan program memerlukan pertukaran informasi antara prosedur (atau
fungsi) dengan pemanggilnya.Tiap item data ditransfer antara parameter aktual dan
parameter formal yang bersesuaian.
Parameter aktual adalah parameter yang disertakan waktu pemanggilan, sedangkan
parameter formal adalah parameter yang dideklarasikan di dalam bagian Nama Prosedur.
Berdasarkan maksud penggunaannya, terdapat tiga jenis parameter formal yang
disertakan di dalam prosedur :
1. parameter masukan
2. parameter keluaran
3. parameter masukan/keluaran
Parameter masukan adalah parameter yang nilainya berlaku sebagai masukan untuk
prosedur. Pada bahasa pemrograman seperti Pascal, parameter masukan dinamakan
parameter by value.
Parameter keluaran adalah parameter yang menampung keluaran yang dihasilkan
oleh prosedur. Pada bahasa pemrograman seperti Pascal, parameter keluaran dinamakan
parameter by reference.
Parameter masukan/keluaran adalah parameter yang berlaku sebagai masukan
sekaligus keluaran bagi prosedur tersebut. Pada bahasa pemrograman seperti Pascal,
parameter masukan/keluaran termask dalam parameter by reference.
Pada bahasa Pascal, parameter formal by value tidak menggunakan kata VAR dalam
deklarasinya, sedangkan parameter by reference menggunakan kata VAR.
Parameter Masukan (By value)
Contoh program menggunakan parameter masukan dalam deklarasi prosedurnya:
Program SegitigaKarakter;
var M : integer;
K : char;
Proedure CetakSegitiga(C : char; N : integer);
var i,j : integer;
Begin
for i:=1 to N do
Begin
for j :=1 to i do
write(C);
writeln;
End;
End;
Begin
write(‘Masukkan karakter yang akan dicetak :’); readln(K);
write(‘Masukkan tinggi segi tiga :’); readln(M);
CetakSegitiga(K,M);
End.
Parameter Keluaran (By reference)
Bila prosedur menghasilkan satu atau lebih nilai yang digunakan oleh program
pemanggil, maka nilai keluaran ditampung di dalam parameter keluaran. Bila prosedur yang
mengandung parameter keluaran dipanggil, nama parameter aktual akan menggantikan
nama parameter formal yang bersesuaian (berlawanan dengan parameter masukan, yang
dalam hal ini, nilai parameter aktual yang di assign ke dalam parameter formal).
Berikut contoh perbedaan parameter masukan dan keluran :
Program ABC;
Var A, B, C : integer;
Procedure XYZ(X,Y : integer; var Z : integer);
{X dan Y parameter masukan, Z parameter keluaran}
Begin
X:= X + 1;
Y:= Y + 1;
Z := X + Y;
End;
Begin
A:= 2;
B:= 5;
XYZ(A,B,C); {Pemanggilan prosedur XYZ}
writeln(A,’ ‘, B,’ ‘,C); {Menampilkan nilai A, B, dan C setelah pemanggilan prosedur}
End.
Pada Program ABC di atas, X dan Y adalah parameter masukan, sedangkan Z adalah
parameter keluaran. Ketika Prosedur XYZ dipanggil dengan parameter aktual A=2 dan B=5,
maka nilai itu mengisi nilai parameter formal X dan Y. Sedangkan nama parameter aktual C
secara semu menggantikan nama parameter formal C (bukan nilainya yang diisikan).
Sehingga setelah pemanggilan, nilai variabel A dan B tetap, yaitu A=2 dan B =5. Sedangkan
nilai variabel C berubah menjadi 9.
Parameter Masukan/Keluaran (By reference)
Parameter masukan/keluaran berfungsi sebagai masukan untuk prosedur sekaligus
menampung nilai keluaran prosedur. Sehingga bila keluarannya berbeda dengan
masukannya, maka hasilnya mengikuti nilai keluarannya.
Contoh Program TukarNilai berikut : 2 nilai integer A dan B merupakan parameter
formal Prosedur Tukar. Setelah instruksi di dalam prosedur dilaksanakan, maka nilai
keluaran A dan B berubah. Karena A dan B adalah parameter masukan/keluaran, maka nilai
parameter aktual pemanggilnya juga berubah sesuai nilai keluaran yang dihasilkan prosedur.
Program TukarNilai;
Var X, Y : integer;
Procedure Tukar (var A,B : integer);
Var temp : integer;
Begin
temp := A;
A := B;
B:=temp;
End.
Begin
X:= 2; Y:= 5;
Tukar (X,Y);
writeln(‘Nilai X setelah ditukar = ‘,X);
writeln(‘Nilai Y setelah ditukar = ‘,Y);
End.
3. Definisi Fungsi
Fungsi adalah sub program yang memberikan/mengembalikan sebuah nilai dari tipe
tertentu. Sebagaimana halnya prosedur, fungsi diakses dengan memanggil namanya. Selain
itu, fungsi juga dapat mengandung daftar parameter formal. Parameter formal pada fungsi
selalu berupa parameter masukan, karena parameter pada fungsi merupakan masukan yang
digunakan oleh fungsi tersebut untuk menghasilkan nilai.
A. Pendeklarasian Fungsi
Deklarasi fungsi adalah :
function NamaFungsi(daftar parameter masukan):tipe data;
bagian deklarasi
Begin
Bagian Pernyataan;
End;
B. Pemanggilan Fungsi
Fungsi diakses dengan cara memanggil namanya dari program utama atau sub
program lain, diikuti dengan daftar parameter aktual (jika ada). Karena fungsi menghasilkan
nilai, maka nilai tersebut dapat ditampung dalam suatu variabel (peubah) yang bertipe sama
dengan tipe fungsi.
(i). peubah := NamaFungsi(daftar parameter aktual);
atau dimanipulasi langsung seperti :
(ii) write(NamaFungsi(daftar parameter aktual));
(iii) if NamaFungsi(daftar parameter aktual) > 0 then....
(iv) y := 2* NamaFungsi(daftar parameter aktual) +3;
Contoh :
Program Terbesar
Var A,B,C,D,Z : integer;
Function Maks(X,Y : integer) : integer;
Begin
if X > Y then Maks:= X
else Maks := Y;
End;
Begin
A := 3; B := 6; C:= 10; D := 8;
writeln(‘Bilangan terbesar antara ‘,A, ‘ dan ‘, B,’ adalah ‘,Maks(A,B));
Z:= Maks(C,D); writeln(‘Bilangan terbesar antara ‘,C, ‘ dan ‘,D,’ adalah ‘, Z);
If Maks(A,B) > Maks(C,D) then writeln(‘Yang terbesar antara ‘, A,’ ‘,B,’ ‘,C,’ dan
‘,D,’ adalah = ‘, Maks(A,B))
else writeln(‘Yang terbesar antara ‘, A,’ ‘,B,’ ‘,C,’ dan ‘,D,’ adalah = ‘,
Maks(C,D));
End.
4. Rekursi
Suatu subprogram tidak hanya bisa memanggil sub program lain, tetapi juga bisa memanggil
dirinya sendiri. Cara ini dikenal dengan sebutan rekursi.
Rekursi banyak dipakai pada persoalan yang dapat dipecahkan secara induktif.
Misalnya untuk menghitung faktorial.
m!=¿¿
Pemecahan secara rekursif :
0 ! = 1 (penghentian rekursi)
jika m > 0, m ! = m x (m-1) ! (langkah induksi)
A. Fungsi Rekursif
Fungsi yang memanggil dirinya sendiri disebut fungsi rekursif. Contoh fungsi rekursif
untuk menghitung faktorial.
Function FaktorialR(m:byte) : longint;
Begin
If m = 0 then FaktrialR:= 1
else FaktorialR:= m * FaktorialR(m-1);
End;
B. Prosedur Rekursif
Rekursi juga bisa diterapkan pada prosedur. Berikut contoh prosedur Balik :
Procedure Balik (X : integer);
Var Sisa : integer;
Begin;
write (X mod 10);
Sisa := X div 10;
If Sisa <> 0 Then Balik(Sisa);
End;
Jika prosedur di atas dipanggil dengan Balik(1024) apa hasilnya ?
Latihan
1. Perhatikan algoritma rekursif berikut: function f(m,n: integer): integer; begin if (m = 0) or (n = 0) then f := 1else f := f(m-1, n-1) + f(m-1, n);end;
Hasil pemanggilan f(6,6) adalah…
2. Diberikan sebuah fungsi dalam Pseudopascal berikut:function P(x, y: integer):integer;beginif (x = 0) thenP := yelsebeginP := P(x-1, y+1);end;end;
Berapakah nilai writeln(P(5,10), ‘ dan ‘,P(2010,2011)); ?3. Dimiliki suatu prosedur berikut :
procedure coba2(a:integer);
begin
c:=c+1;
if (a>0) then
begin
coba2(a div 2);
write(a mod 2);
end;
end;
Jika dipanggil dengan coba2(10) akan menampilkan hasil…4. Dimiliki prosedur berikut :
procedure coba6(a,b : integer);
begin
if (a<>0) then
begin
coba6(a div b,b);
write(a mod b);
end;
end;
Jika dipanggil coba6(8,2) akan menghasilkan keluaran…
BAB VI
TIPE DATA ARRAY
Array atau larik terdiri atas bagian-bagian komponen yang memiliki tipe data sama. Dalam
penyimpanannya array selalu mempunyai jumlah komponen yang tetap yang ditunjukkan
oleh indeksnya.
A. Deklarasi Array
Variabel array dideklarasikan dengan mencantumkan tipe data dan nama variabel
yang diikuti dengan nomor indeks yang menyatakan banyaknya lokasi memori yang ingin
dibuat.
var nama_variabel : array [indeks] of tipe data;
contoh var N : array[1..100]of integer;
B. Mengakses Data larik :
Cara mengakses data larik adalah dengan menunjukkan :
Nama_Larik[no.indeks] ;
Misal : x[1] berarti kita mengakses data larik x pada no.indeks ke-1.
Keuntungan :
Menggunakan data larik, kita tidak akan kehilangan nilai dari suatu data.
Kelemahan :
Saat ditentukan suatu variabel bertipe data array maka ia akan langsung mengambil
tempat pada memory penyimpanannya sesuai dengan tipe data yang digunakan pada array,
baik nantinya semua komponen pada array itu digunakan ataupun tidak.
C. Array Dimensi Banyak
Dalam pemrograman kadang kita menghadapi masalah saat kita akan
mendeklarasikan suatu matriks. Dengan adanya tipe data array maka masalah itu dapat
diselesaikan, yaitu dengan menggunakan array dengan dimensi dua atau lebih yang
kemudian dikenal dengan array dimensi banyak.
Pendeklarasian :
var nama_variabel : array [indeks,indeks] of tipe data;
contoh var M : array[1..10,1..10]of integer;
Berarti matriks itu akan mempunyai dimensi (10x10), namun itu hanya batas atas
dari indeks yang dipesan dalam memori penyimpanan (di atas itu tidak akan disimpan),
sedangkan apabila nantinya kita hanya memasukkan jumlah baris misal 2 dan jumlah kolom
2 itu boleh saja selama tidak lebih dari 10.
Entry-entry dari matriks tersebut dapat kita panggil dengan mengetikkan
Nama_Array[indeks] ;
dari contoh diatas berarti M[2,3] yaitu entry dari matriks pada baris kedua kolom ketiga.
Contoh Kasus menggunakan tipe data array
Program menghitung nilai maksimum, minimum, rata-rata dari sejumlah data integer.
Var i,n,maks,min,jum,h : integer;
Nilai : array[1..10] of integer;
Rerata : real;
Begin
Write(‘Banyaknya data :’); readln(n);
Jum :=0;
for i:= 1 to n do begin
write(‘Data ke – ‘,i,’ = ‘);
readln(nilai[i]);
jum :=jum + nilai[i];
end;
rerata := jum/n;
maks=nilai[1];
min=nilai[1];
for i:= 1 to n do begin
if (nilai[i]>maks) then
maks :=nilai[i];
if (nilai[i]<min) then
min :=nilai[i];
end;
writeln(‘Nilai Terbesar = ‘ ,maks);
writeln(‘Nilai Terkecil = ‘ ,min);
writeln(‘Nilai Terbesar = ‘ ,maks);
writeln(‘Nilai Rata-rata = ‘ ,rerata);
readln;
end.
Latihan
1. Diberikan array berikut:
dan diberikan algoritma berikut:
Nilai elemen ke 9 dari array tersebut (atau a[9]) adalah...2. Perhatikan kode program di bawah ini “cek” adalah sebuah array dengan indeks mulai dari 1 s/d 1000 yang setiap elemennya bernilai true atau false. Pada awal program semua elemen array “cek” diberi nilai “false”.
for i:=1 to n dobeginj:=i;repeat
cek[j]:=not cek[j];j:=j+i;
until j>n;end;
for i:=1 to n doif cek[i] thenwrite(i,'*');
Jika n berharga 100, maka output yang akan dihasilkan adalah .....
3. Jika pada program didefinisikan sebuah array berikut ini:
dan diberikan sebuah fungsi hitung berikut ini:
Nilai hitung(4) adalah…
4. Dimiliki suatu larik a sebagai berikut :
var a : array [1..10] of integer = (1,3,5,9,8,7,6,6,4,2);dan potongan algoritma berikut :c:=0;for i := 1 to 9 dobegind:=i;m:=a[i];for j:= (i+1) to 10 do if ( m>a[j]) then begin d:=j; m:=a[j]; end;if (d<>i) thenbegin
temp:=a[i];a[i]:=a[d];a[d]:=temp;c:=c+1;
end;end;
Pada saat i = 3 dan iterasi j selesai dilakukan, nilai a[4] adalah…
5. Dimiliki larik x : array [1..7] of integer= (2,4,5,9,11,12,14);
Dan potongan program berikut :
procedure coba1(c,a,b : integer);
var t : integer;
k : boolean;
begin
i:=i+1;
k:= false;
if (a<=b) then
begin
t:= (a+b) div 2;
if c = x[t] then
begin
d:=t;
k:=true;
end
else if (c> x[t]) then coba1(c,t+1,b)
else coba1(c,a,t-1);
end
else d:=-1;
end;
Jika dipanggil dengan coba1(9,1,7), berapa nilai d ?
BAB VII
KOMPLEKSITAS ALGORITMA
Sebuah masalah dapat mempunyai banyak algoritma penyelesaian. Contoh: masalah
pengurutan (sort), ada puluhan algoritma pengurutan. Sebuah algoritma tidak saja harus
benar, tetapi juga harus mangkus (efisien). Algoritma yang bagus adalah algoritma yang
mangkus (efficient).
Kemangkusan algoritma diukur dari waktu (time) eksekusi algoritma dan kebutuhan
ruang (space) memori. (Munir, 2005) Algoritma yang mangkus ialah algoritma yang
meminimumkan kebutuhan waktu dan ruang. Kebutuhan waktu dan ruang suatu algoritma
bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses.
Kemangkusan algoritma dapat digunakan untuk menilai algoritma yang bagus dari
sejumlah algoritma penyelesaian masalah.
Model Penghitungan Kebutuhan Waktu
Menghitung kebutuhan waktu algoritma dengan mengukur waktu sesungguhnya (dalam
satuan detik) ketika algoritma dieksekusi oleh komputer bukan cara yang tepat.
Alasan:
1. Setiap komputer dengan arsitektur berbeda mempunyai bahasa mesin
yang berbeda à waktu setiap operasi antara satu komputer dengan
komputer lain tidak sama.
2. Compiler bahasa pemrograman yang berbeda menghasilkan kode mesin
yang berbeda à waktu setiap operasi antara compiler dengan compiler lain
tidak sama.
Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin
dan compiler apapun.
Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang
ini adalah kompleksitas algoritma.
Ada dua macam kompleksitas algoritma, yaitu: kompleksitas waktu dan
kompleksitas ruang.
Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk
menjalankan algoritma sebagai fungsi dari ukuran masukan n.
Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang
terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat
menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan
meningkatnya ukuran masukan n.
Ukuran masukan (n): jumlah data yang diproses oleh sebuah algoritma.
Contoh: algoritma pengurutan 1000 elemen larik, maka n = 1000.
Contoh: algoritma TSP pada sebuah graf lengkap dengan 100 simpul, maka n = 100.
Contoh: algoritma perkalian 2 buah matriks berukuran 50 x 50, maka n = 50.
Dalam praktek perhitungan kompleksitas, ukuran masukan dinyatakan sebagai
variabel n saja.
Kompleksitas Waktu
Jumlah tahapan komputasi dihitung dari berapa kali suatu operasi dilaksanakan di dalam
sebuah algoritma sebagai fungsi ukuran masukan (n).
Di dalam sebuah algoritma terdapat bermacam jenis operasi:
o Operasi baca/tulis
o Operasi aritmetika (+, -, *, /)
o Operasi pengisian nilai (assignment)
o Operasi pengakasesan elemen larik
o Operasi pemanggilan fungsi/prosedur
o dll
Dalam praktek, kita hanya menghitung jumlah operasi khas (tipikal) yang mendasari
suatu algoritma.
Contoh Operasi Khas dalam Algoritma
Algoritma pencarian di dalam larik
Operasi khas: perbandingan elemen larik
Algoritma pengurutan
Operasi khas: perbandingan elemen, pertukaran elemen
Algoritma penjumlahan 2 buah matriks
Operasi khas: penjumlahan
Algoritma perkalian 2 buah matriks
Operasi khas: perkalian dan penjumlahan
Contoh 1. Tinjau algoritma menghitung rerata sebuah larik (array).
sum ¬0
for i ¬ 1 to n do
sum ¬ sum + a[i]
endfor
rata_rata ¬ sum/n
Operasi yang mendasar pada algoritma tersebut adalah operasi penjumlahan
elemen-elemen ai (yaitu sum¬sum+a[i]) yang dilakukan sebanyak n kali.
Kompleksitas waktu: T(n) = n.
Latihan
1. Dimiliki potongan program berikut :
for i :=1 to p do
writeln('*');
for j:= 1 to p-1 do
writeln('*');
for k:= 1 to p-2 do
writeln('*');
Berapa kali ‘*’ dicetak, jika p = 10 …
2. Diberikan potongan algoritma berikut :
for i :=1 to p do
c:=c+1;
for j:= 1 to p-1 do
begin
for k:= 1 to p-2 do
c:=c+1;
end;
Jika nilai c mula-mula adalah 0 dan nilai p = 10, maka nilai akhir c adalah…
3. Dimiliki prosedur sebagai berikut :procedure hitungsaja(n : integer; m : integer);var k : integer;begin
if (n < m) then begin
writeln(‘hello’);k := (m + n) div 2;hitungsaja(n,k);hitungsaja(k+1,m);
endelse writeln(‘hello’);
end;
Pada pemanggilan hitungsaja(5,24), berapa kali dicetak ‘hello’ ?
DAFTAR PUSTAKA
Gilles Brassard, Paul Bratley, Fundamentals of Algorithmics, Prentice Hall, New Jersy, 1996
Rinaldi Munir, Algoritma dan Pemrograman, Informatika, Bandung, 2005
Rinaldi Munir, Matematika Diskrit, Informatika, Bandung, 2005
TOKI, Buku Panduan Olimpiade Sains Komputer, 2007