MatematikaPemulaFase C–FE1E5

Algoritma Euclid (FPB)

Algoritma Euclid mencari FPB (Faktor Persekutuan terBesar) dua bilangan lewat sisa pembagian berulang: FPB(a, b) = FPB(b, a mod b). Diulang sampai sisa nol; bilangan terakhir yang bukan nol itulah FPB-nya. Jauh lebih cepat daripada mencoba semua faktor.

Contoh kasus

Menyederhanakan pecahan ke bentuk paling sederhana (mis. 272/153 dibagi FPB 17 menjadi 16/9) — dipakai kalkulator dan pustaka bilangan rasional.

Silabus

Mencari FPB dua bilangan lewat sisa pembagian berulang: FPB(a, b) = FPB(b, a mod b) sampai sisanya nol.

Tujuan Belajar

·Memahami hubungan FPB(a, b) dengan sisa pembagian a mod b
·Menjelaskan mengapa proses berhenti saat sisa nol
·Menerapkan Euclid untuk menyederhanakan pecahan

Cara Kerja

·Ambil dua bilangan a dan b
·Hitung sisa pembagian a dibagi b
·Ganti a dengan b, dan b dengan sisa tadi
·Ulangi sampai sisanya menjadi nol
·Bilangan terakhir yang bukan nol itulah FPB-nya

Prasyarat

·Operasi modulo (sisa bagi)

Contoh Nyata

·Menyederhanakan pecahan, misalnya 272/153 menjadi 16/9
·Membagi rata benda ke beberapa orang tanpa sisa berlebih

Kompleksitas O(log(min(a, b)))