My first Magazine pemrograman-kompetitif-dasar | Page 27

2.5 Kombinatorika
Dengan menyelesaikan versi mudah, ternyata kita justru dapat menyelesaikan soal tersebut.
Suatu subbarisan dari A pasti juga merupakan subhimpunan dari A. Ternyata, selalu ada cara
untuk menjawab pertanyaan Pak Dengklek. Yakni, keluaran "tidak mungkin" tidak akan pernah
terjadi. Implementasinya cukup sederhana: lihat Algoritma 8.
Algoritma 8 Solusi persoalan Subhimpunan Terbagi.
1:
2:
3:
4:
5:
6:
function FIND D IVISIBLE S UBSEQUENCE (A, N)
sum ← new integer[N + 1]
sum[0] ← 0
for i ← 1, N do
sum[i] ← sum[i − 1] + A[i]
end for
seenInIndex ← new integer[N]
FILL A RRAY (seenInIndex, −1)
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
. Inisialisasi array sum[0..N]
. Inisialisasi array seenInIndex[0..N − 1]
. Isi seenInIndex dengan -1
for i ← 0, N do
if seenInIndex[sum[i] mod N] = −1 then
seenInIndex[sum[i] mod N] ← i
else
a ← seenInIndex[sum[i] mod N]
b ← i
return [a + 1, a + 2, ..., b]
end if
end for
end function
2.5
. Kembalikan indeks-indeks solusinya
Kombinatorika
Kombinatorika adalah ilmu yang mempelajari penyusunan dari objek-objek, 9 seperti menghi-
tung banyaknya kemungkinan dari susunan objek menurut aturan tertentu. Mampu memahami
sifat-sifat dari penyusunan objek dapat membantu pemecahan masalah dengan algoritma. Terda-
pat beberapa dasar teknik menghitung banyaknya penyusunan objek, yang akan dibahas pada
bagian ini.
2.5.1
Aturan Perkalian dan Aturan Penjumlahan
Contoh Soal 2.2: Kota 1
Terdapat 3 buah kota yaitu A, B, dan C. Kota A dan kota B terhubung oleh 3 jalur berbeda
yaitu e 1 , e 2 , dan e 3 . Sedangkan kota B dan kota C terhubung oleh 2 jalur berbeda yaitu e 4
dan e 5 . Berapa banyak cara berbeda untuk menuju kota C dari kota A?
e 4
e 1
A
e 2
e 3
B
e 5
C
17