My first Magazine pemrograman-kompetitif-dasar | Page 21

2
Matematika Diskret Dasar
Matematika diskret merupakan cabang matematika yang mempelajari tentang sifat bilangan
bulat, logika, kombinatorika, dan graf. Ilmu pada jenis matematika ini digunakan sebagai dasar
ilmu komputer secara umum. Pada bagian ini, kita akan mencakup dasar ilmu matematika diskret
yang umum digunakan dalam pemrograman kompetitif.
2.1
Arimetika Modular
Modulo merupakan suatu operator matematika untuk mendapatkan sisa bagi suatu bilangan
terhadap suatu bilangan lainnya. Operasi modulo bisa dilambangkan dengan mod pada bahasa
Pascal atau % pada bahasa C/C++ atau Java. Operasi a mod m biasa dibaca "a modulo m", dan
memberikan sisa hasil bagi a oleh m. Sebagai contoh:
• 5 mod 3 = 2
• 10 mod 2 = 0
• 21 mod 6 = 3
Sifat-sifat dasar dari operasi modulo adalah:
•
•
•
•
•
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a − b) mod m = ((a mod m) − (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
a b mod m = (a mod m) b mod m
(−a) mod m = (−(a mod m) + m) mod m
Sifat-sifat tersebut dapat dimanfaatkan untuk mempermudah perhitungan modulo. Sebagai
contoh, Anda diberikan bilangan n dan k, lalu diminta menghitung hasil n! mod k. Pada contoh
ini, n! = n × (n − 1) × (n − 2) × ... × 1. Seandainya kita menghitung n! terlebih dahulu, kemudian
baru dimodulo k, kemungkinan besar kita akan mendapatkan integer overflow. Ingat bahwa n!
dapat bernilai sangat besar dan tidak dapat direpresentasikan dengan tipe data primitif integer.
Solusinya adalah melakukan modulo pada setiap fase perkalian. Contoh implementasi dapat
dilihat pada Algoritma 2. Perhatikan pada baris ke-4, hasil perkalian selalu dimodulo untuk
mencegah integer overflow.
Algoritma 2 Fungsi faktorial dengan memanfaatkan modulo.
1:
2:
3:
4:
5:
6:
7:
function MODULAR F ACTORIAL (n, k)
result ← 1
for i ← 1, n do
result ← (result × i) mod k
end for
return result
end function
11