Friday, March 4, 2011

Tips Menghitung FPB dengan Algoritma Euclidean

Categories: ,

Algoritma Euclidean adalah salah satu algoritma tercepat untuk menghitung FPB (Faktor Persekutuan terBesar) / GCD (Greatest Common Divisor). FPB dari 2 angka adalah angka terbesar yang habis membagi 2 angka tersebut. Prinsip dari algoritma Euclidean ini adalah dari kenyataan bahwa FPB dari 2 angka tidak akan berubah jika angka terbesar dikurangi angka terkecil. Sebagai contoh, 22 adalah FPB dari 198 dan 110 (198 = 22 x 9; 110 = 22 x 5), 198 – 110 = 88 dan 110 tetap mempunyai FPB 22. Proses ini bisa terus di-ulang sampai salah satu dari angka tersebut adalah 0, sehingga angka yang lainnya adalah FPB dari 2 angka paling awal. Jika dilihat langkah – langkahnya sampai selesai :
(198, 110) -> (110, 88) -> (88, 22) -> (22, 0)
Dapat juga dituliskan secara prosedural :
198 = 110 x 1 + 88
110 = 88 x 1 + 22
88 = 22 x 4 + 0
Berdasarkan prosedur di atas, sekarang akan dibuat implementasinya di 4 bahasa pemrograman (C/C++, Assembly, Pascal, dan BASIC). Implementasinya akan berbentuk fungsi FPB dengan input 2 bilangan bulat (integer) 32-bit, dan output juga integer. Berikut ini adalah kode-kode fungsi FPB algoritma Euclidean di 4 bahasa tersebut :

C/C++

01int FPB(int a, int b)
02{
03    if (a < b)
04       {int t = a; a = b; b = t;} // Tukar a dan b jika a < b
05
06    int r = 0;
07
08    do
09    {
10        r = a % b;
11        a = b;
12        b = r;
13    } while (r); // Teruskan loop hanya jika r tidak 0
14
15    return a;
16}

Assembly

01FPB PROC
02; Fungsi : FPB(a,b)
03; Input  : (a,b) -> (eax, ebx)
04; Output : FPB -> eax
05
06    pushad             ; Simpan semua register
07    cmp eax, ebx   ; Bandingkan eax dan ebx
08    ja  startloop  ; Jika  a > b, langsung ke startloop
09    xchg    eax, ebx   ; Jika tidak, tukar isi eax dan ebx
10startloop:
11    xor edx, edx   ; edx = 0
12    div ebx        ; eax / edx, sisanya akan disimpan di edx
13    cmp edx, 0     ; Bandingkan edx dan 0
14    je  endloop    ; Jika edx = 0, hentikan loop ke endloop
15    mov eax, ebx   ; eax = ebx
16    mov ebx, edx   ; ebx = edx
17    jmp startloop  ; Mulai lagi loop
18endloop:
19    popad              ; Kembalikan semua register ke asal
20    mov eax, ebx       ; Simpan nilai FPB di eax
21    ret                ; Kembali ke pemanggil
22
23FPB ENDP

Pascal

01Function FPB(a, b : Integer) : Integer;
02
03Var t, r : Integer;
04
05Begin
06 If (a < b) Then
07    Begin
08      t := a; a := b; b := t
09    End;
10
11 Repeat
12    r := a Mod b;
13    a := b;
14    b := r
15 Until r = 0;
16
17 FPB := a;
18End;

BASIC

01Function FPB(ByVal a As Long, ByVal b As Long) As Long
02
03    Dim t As Long, r As Long
04
05    If a < b Then t = a: a = b: b = t
06
07    Do
08        r = a Mod b
09        a = b
10        b = r
11    Loop Until r = 0
12
13    FPB = a
14
15End Function

Spread The Love, Share Our Article

Related Posts

No Response to "Tips Menghitung FPB dengan Algoritma Euclidean"

Post a Comment

Link dead , link invalid , suggestions or criticism ?
Please explain or tell to us by leaving a comment bellow.

By RANDYSHARE