Pernahkah anda mendengar tentang Algoritma Euclid? Istilah Algoritma Euclid mungkin kelihatan pelik bagi pelajar yang masih dalam pendidikan menengah. Walau bagaimanapun, bagi mereka yang terlibat dalam olimpiade matematik atau bagi mereka yang belajar matematik di universiti, algoritma ini akan menjadi biasa.
Berbeza dengan algoritma Eculid, istilah GCF atau Greatest Common Factor sememangnya biasa didengari oleh telinga kita. Sebab kita dah kenal FPB sejak sekolah rendah. Jadi apakah kaitan antara algoritma Euclid dan FPB? Semak ulasan di bawah.
Apakah algoritma Euclid?
Sebelum mengetahui lebih lanjut tentang algoritma Euclid, kita terlebih dahulu memahami apa itu algoritma. Algoritma boleh ditafsirkan sebagai satu set laluan atau prosedur untuk menyelesaikan masalah tertentu.
Manakala algoritma Euclid sendiri adalah prosedur yang digunakan untuk menentukan nilai GCF bagi dua nombor.
Algoritma ini dipanggil algoritma Euclid sempena nama penciptanya, Euclid. Euclid adalah seorang ahli matematik Yunani yang terkenal. Euclid menulis Algoritma Euclid sepenuhnya dalam bukunya Elements.
Pembelajaran tentang algoritma Euclid biasanya berlaku di peringkat kuliah, terutamanya untuk pelajar matematik. Dan dia belajar secara mendalam dalam kursus teori nombor.
Menggunakan algoritma Euclid untuk menentukan GCF
Kaedah biasa untuk menentukan GCF adalah untuk menentukan bilangan terbesar semua faktor sepunya nombor tertentu. Apabila ia datang kepada faktor sepunya, sudah tentu, ia merujuk kepada nombor perdana.
Proses menentukan faktor sepunya yang merupakan nombor perdana juga dikenali sebagai pemfaktoran perdana. Pelajar sekolah rendah kemudiannya diajar tentang pokok faktor untuk memudahkan proses pemfaktoran awal.
Tidak ada yang salah dengan proses pemfaktoran pertama untuk menentukan GCF, tetapi kaedah ini terhad kepada nombor yang kecil. Apabila perlu untuk menentukan GCF bilangan yang besar, kaedah pemfaktoran pertama tidak akan berkesan.
Dan masalah ini dijawab oleh algoritma Euclid. Algoritma Euclid menggunakan konsep modulus (pembahagian baki) dalam proses.
Prosedur algoritma Euclid
Prosedur dalam algoritma Euclid ditulis sepenuhnya seperti berikut.
GCF (a,b) di mana a > b dan a, b ialah integer positif boleh ditentukan dengan mengulangi algoritma pembahagian berikut:
a = q1.b + r1 0 < r1 < b
b = q2.r1 + r2 0 < r2 < r1
r1 = q3.r2 + r3 0 < r3 < r2
⁞ ⁞
rn-2 = qn.rn-1 + rn 0 < rn < rn-1
rn-1 = qn+1.rn + rn+1 rn+1 = 0 Proses pembahagian diulang sehingga baki pekali menjadi sifar, dan GCF(a,b) ditentukan daripada baki bukan sifar terakhir pembahagian di atas.
Sebagai contoh, untuk menentukan GCF 720 dan 246 menggunakan algoritma Euclid, maka algoritma pembahagian untuk menentukan GCF adalah seperti berikut:
720 = 2 x 246 + 228 Ulang 1
246 = 1 x 228 + 18 ulangan 2
228 = 12 x 18 + 12 ulangan 3
18 = 1 x 12 + 6 ulangan 4
12 = 2 x 6 + 0 Ulang 5
Algoritma bahagian berakhir dengan lelaran kelima kerana baki bahagian mencapai 0, maka GCF(720, 246) ialah baki bahagian terakhir sebelum 0, iaitu 6 (dalam lelaran keempat).
Kaedah di atas ialah aliran penentuan GCF(720, 246) menggunakan algoritma Euclid. Berikut akan dibandingkan dengan cara menentukan penyebut.
Pembahagi 720 = 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80 90 , 120, 144, 180, 240, 360, 720
Pembahagi 246 = 1, 2, 3, 41
Pembahagi 720 dan 246 = 1, 2, 3
Maka GCF bagi 720 dan 246 ialah 1 x 2 x 3 = 6.
Membandingkan dua kaedah di atas, algoritma Euclid adalah lebih berkesan dalam menentukan GCF nombor besar.
Contoh soalan dan perbincangan Algoritma Euclid
Untuk lebih memahami proses penentuan GCF menggunakan algoritma Euclid, lawati semula perbincangan soalan berikut.
Contoh soalan 1
Tentukan GCF bagi 615 dan 3579 menggunakan algoritma Euclid
Bincangkan:
Di bawah ialah aliran algoritma pembahagian untuk menentukan GCF (615, 3579).
3579 = 3 x 988 + 615 ulangan 1
988 = 1 x 615 + 373 Ulang 2
615 = 1 x 373 + 242 Ulang 3
373 = 1 x 242 + 131 ulangan 4
242 = 1 x 131 + 111 Ulang 5
131 = 1 x 111 + 20 ulangan 6
111 = 5 x 20 + 11 ulangan 7
20 = 1 x 11 + 9 ulangan 8
11 = 1 x 9 + 2 ulangan 9
9 = 4 x 2 + 1 Ulang 10
2 = 2 x 1 + 0 Ulang 11
Dalam lelaran ke-11, baki bahagian ialah 0, kemudian GCF 615 dan 3579 ditentukan daripada baki hasil bagi lelaran sebelumnya, iaitu, lelaran ke-10. Baki bahagian dalam lelaran kesepuluh ialah 1. Jadi GCF(615, 3579) ialah 1.
Contoh soalan 2
Tentukan GCF 534 dan 10587 menggunakan algoritma Euclid!
Bincangkan:
Di bawah ialah aliran algoritma pembahagian untuk menentukan GCF (534, 10587)
10587 = 19 x 534 + 441 ulangan 1
534 = 1 x 441 + 93 ulangan 2
441 = 4 x 93 + 69 ulangan 3
93 = 1 x 69 + 24 ulangan 4
69 = 2 x 24 + 21 ulangan 5
24 = 1 x 21 + 3 ulangan 6
21 = 7 x 3 + 0 ulang 7
Lelaran algoritma bahagian berhenti pada lelaran ketujuh kerana baki bahagian ialah 0. Maka GCF ialah 534 dan 10587 ialah baki pembahagian dalam lelaran keenam, iaitu bersamaan dengan 3. Oleh itu, GCF(534, 10587) ialah 3.
Contoh soalan 3
Tentukan GCF bagi 1677, 1157 dan 897 menggunakan algoritma Euclid!
Bincangkan:
Menentukan GCF menggunakan algoritma Euclid hanya boleh digunakan untuk dua nombor. Tetapi ini tidak bermakna kita tidak boleh menggunakan algoritma Euclid untuk menentukan GCF. Kaedah untuk menentukan GCF bagi 3 nombor adalah dengan memilih 2 daripada 3 nombor dahulu.
Sebagai contoh, nombor 1677 dan 1157 dipilih dahulu, kemudian algoritma bahagi diulang seperti berikut.
1677 = 1 x 1157 + 520 ulangan 1
1157 = 2 x 520 + 117 Ulang 2
520 = 4 x 117 + 52 ulangan 3
117 = 2 x 52 + 13 ulangan 4
52 = 4 x 13 + 0 Ulang 5
Dalam lelaran kelima, baki bahagian ialah 0, maka GCF(1677, 1157) ialah baki bahagian dalam lelaran keempat, iaitu 13. Kemudian, GCF 897 dan 13 ditentukan (GCF 1677 dan 1157). Algoritma pembahagian adalah seperti berikut.
897 = 69 x 13 + 0 Ulang 1
Dalam lelaran pertama baki bahagian ialah 0, maka GCF ialah 897 dan 13 ialah 13. Oleh itu, boleh disimpulkan bahawa GCF bagi 1677, 1157 dan 897 adalah bersamaan dengan 0. Atau kita boleh menulis GCF (1677), 1157, 897) = 13.
