Mengenal Algoritma Euclid


Algoritma Euclid merupakan algoritma yang dibuat oleh Euclid untuk memperoleh nilai FPB dari dua bilangan. Dan akhirnya, nilai FPB tersebut dapat kita gunakan untuk membantu memperoleh bentuk paling sederhana dari suatu bilangan pecahan .

mengenal-algoritma-euclid-sobat-kreatif-indonesia-president-university

Tentu ini bukan masalah yang sulit bagi Kita, kan? Kita sudah terbiasa melakukan penghitungan seperti ini sejak bangku sekolah dasar. Nah, yang perlu kita pikirkan sekarang adalah bagaimana menuangkan algoritma Euclid ini dalam bentuk program komputer sehingga komputer dapat menyelesaikan masalah serupa. OK, untuk mempermudah, marilah Kita definisikan problem Kita dengan pengelompokan sebagai berikut.

Problem:

Menentukan bentuk pecahan paling sederhana dari suatu pecahan yang pembilang dan penyebutnya sudah diketahui nilainya dengan nilai nonnegatif.

Input

Output

5 0

0 5

17 3

12 15

178468 267702

(tidak ada output)

0/5

17/3

12/15 = 4/5

178468/267702 = 2/3

Solusi:

Metode yang digunakan dalam algoritma Euclid adalah berdasarkan fakta bahwa jika a > b, maka FPB dari a dan b sama dengan FPB dari b dan a – b. Untuk memudahkan pemahaman, mari Kita coba kode dengan bahasa C berikut.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#include <stdio.h>

int main ()

{

int pembilang, penyebut, nilai_fpb;

int fpb ( int a, int b );

while ( scanf ( “%d %d”, &pembilang, &penyebut ) > 0 )

if ( pembilang > -1 && penyebut > 0 ) {

nilai_fpb = ( pembilang > 0 ) ? fpb ( pembilang, penyebut ) : 1;

printf ( “%d/%d = %d/%d\n”,

pembilang, penyebut, pembilang/nilai_fpb, penyebut/fpbval );

}

return 0;

}

int fpb ( int a, int b )

{

int c;

while ( a > 0 ) {

if ( a < b ) {

c = a; a = b; b = c;

}

a = a – b;

}

return b;

}

Baris 8 – 13: Meminta user untuk menginputkan 2 angka. Dalam bahasa pemrograman C, apabila proses pembacaan input dengan fungsi scanf() berjalan baik (data yang diinputkan betul-betul merupakan angka yang valid), maka fungsi tersebut akan memberikan nilai balik > 0. Apabila sebaliknya, misalnya diinputkan karakter ‘d’ (bukan angka), maka akan menghasilkan nilai balik < 1. Sehingga baris 8 ini menginstruksikan bahwa apabila nilai balik dari fungsi scanf() > 0, maka instruksi pada baris 9 – 13 akan dikerjakan hingga berulang lagi pada pembacaan input dengan fungsi scanf() di baris 8. Akan begitu terus hingga kondisi nilai balik dari fungsi scanf() > 0 tidak terpenuhi.

Baris 18 – 29: Nah, di sinilah Kita menerapkan teori algoritma Euclid yang telah sedikit Kita tengok sebelumnya. Instruksi pada baris 23 melakukan pengecekan nilai argumen a dan b yang diinputkan untuk memastikan bahwa nilai a > b. Namun jika ternyata nilai a < b, maka nilai dari kedua variable tersebut harus ditukar terlebih dahulu, sehingga nilai a = nilai b dan nilai b = nilai a sebelum ditukar, seperti terinstruksikan di baris 24. Jika kondisinya sudah dipastikan nilai a > nilai b, maka nilai a – b disimpan ke a. Proses ini akan terus berulang hingga kondisi pada baris 22, yaitu nilai a > 0 tidak terpenuhi. Pada akhirnya fungsi ini akan memberikan nilai balik dari nilai b pada pengulangan terakhir atau sama dengan nilai a sebelum menjadi 0.

Demikian ilmu yang sedikit ini telah kami bagikan. Semoga bermanfaat dan Salam Kreatif!

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s