Penjelasan Algoritma Euclidean untuk GCD

Motivasi

Setiap orang yang pernah belajar untuk OSK/OSP komputer kemungkinan besar mengenal fungsi berikut:

?

1 2 3 4 5 6 7

int gcd(int a, int b){   if (b == 0){     return a;   }else{     return gcd(b, a % b);   } }

Fungsi yang pendek ini adalah Algoritma Euclidean untuk mencari GCD. Entah mengapa cukup dengan operasi modulo, tiba-tiba didapatkan GCD dari dua bilangan. Padahal jika kita mencari GCD menurut cara anak SD, diperlukan faktorisasi bilangan terlebih dahulu. Bagaimana sebenarnya fungsi ini bekerja?

Ada pembuktian matematis mengapa algoritma ini benar. Sayangnya pembuktian ini bisa jadi sulit dicerna bagi beberapa orang. Ada pendekatan lain untuk memahami bagaimana fungsi ini bekerja, dan akan saya jelaskan pada tulisan ini.

GCD = Memotong Kue

Kita ganti persoalan GCD(a, b) sebagai berikut:
Diberikan kue berbentuk persegi panjang, dengan panjang a dan lebar b. Kue ini hendak dipotong menjadi sejumlah persegi. Tidak boleh ada potongan yang tidak persegi. Tentukan sisi persegi terbesar yang mungkin digunakan!

Sebagai contoh, jika a=30 dan b=21, maka jawabannya adalah 3. Gambar berikut menunjukkan cara pemotongannya:

Jawaban dari masalah ini sama saja dengan GCD(a, b). Sebab kita berusaha mencari nilai terbesar yang habis membagi a dan b.

ACM ICPC World Final 2015 - Morocco (Bagian 1)

Tim BerinGAS mendapat peringkat 4 pada ICPC Regional Jakarta 2014 yang lalu. Saya sudah putus harapan untuk bisa lolos ke World Final (WF), mengingat biasanya hanya 3 besar yang mendapat tiket ke WF. Namun pada awal tahun 2015, saya sedikit penasaran juga apakah tim kita mendapat slot WF. Saya sering-sering cek blog CJ Hwang, berharap infonya segera muncul.

Suatu hari, saya sangat mengantuk dan sudah tidur sekitar 21.30. Pagi-pagi jam 05.00 saya bangun dan dikagetkan dengan notifikasi di HP. Setelah saya cek, banyak yang memberi selamat karena tim BerinGAS BERHASIL MASUK KE WF 2015! Saya yang tadinya sudah siap-siap pensiun jadi kembali harus latihan. Saya juga harus mengatur ulang rencana hidup selama 6 bulan ke depan yang sebelumnya sudah dirancang dengan asumsi tanpa WF. Saya langsung mundur dari kerja paruh waktu, memilih topik skripsi yang ringan, dan mengalokasikan waktu untuk latihan.

Keadaan

Setelah 15 tahun berjuang di ACM ICPC, tim UI akhirnya masuk ke WF pada tahun 2014. Tahun ini, UI masuk lagi untuk kedua kalinya. Tim UI yang berangkat untuk ke WF adalah Pak Denny (coach), Ammar, Soko, dan saya.

Lokasi WF tahun ini adalah di kota Marrakesh, Maroko. Lokasinya di Afrika utara, dekat dengan Eropa barat.

Sumber: http://www.freeworldmaps.net/africa/morocco/location.gif

ACM ICPC World Final 2015 - Morocco (Bagian 2)

Daftar bagian tulisan:

• Bagian 1
• Bagian 2 (tulisan ini)
• Bagian 3

Hari 3

Akhirnya tidur pulas dan saya bangun pukul 07.30. Ternyata nama hotelnya adalah Hotel Palmerie yang sempat salah saya baca sebagai "Palmerah". Kami pergi sarapan ke restoran, dan saya makan banyak roti dan buah. Roti di sini sangat enak, terutama yang teksturnya lembut atau renyah. Kalau dari Pak Denny, mungkin rotinya bisa enak karena Maroko mendapat banyak pengaruh dari Prancis. Yang saya suka adalah croissant dan pain au chocolat. Namun saya kurang suka dengan roti varian lain yang teksturnya keras.

Musik yang seperti di acara TV buka puasa ternyata alat musik senar

ACM ICPC World Final 2015 - Morocco (Bagian 3)

Daftar bagian tulisan:

• Bagian 1
• Bagian 2
• Bagian 3 (tulisan ini)

Hari 7

Hari ini sudah tidak ada agenda resmi dari ICPC. Karena kita sudah jauh-jauh ke Afrika, Pak Denny sudah booking tur ke gurun Zagora. Kami akan naik mobil bersama seorang supir dari Marrakesh ke Zagora (~260 km), kemudian naik unta ke lokasi kemah (di padang pasir), melihat matahari terbenam, berkemah, tidur, melihat matahari terbit, naik unta lagi ke jalan raya, lalu pulang ke Marrakesh.

Kami bangun 06.00, siap-siap sarapan. Sambil siap-siap, saya membaca soal OSN hari 2. Rasanya senang karena 2 soal buatan saya keluar pada hari ke-2 ini :)
Soal saya yang tidak keluar merupakan soal tersulit. Jadi ternyata tim juri OSN tahun ini masih punya belas kasihan >:)

Untuk sarapan, saya makan sebanyak yang saya bisa dan menikmati croissant terakhir. Berikutnya kami checkout, dan naik mobil tur. Pengemudi kita bernama Mohammed, dan Bahasa Inggrisnya bagus. Sepanjang perjalanan kami berbincang-bincang dengan Mohammed seputar Maroko dan Indonesia.

Croissant dan pain au chocolat :"

Merencanakan strategi perang