Newzbiez

misalkan:
m = 80 dan n = 12
fakor pembagi 80 = 1,2,4,5,8,10,16,20,40,80
faktor pembagi 12 =1,2,3,4,6,12

GCD (80,12) = 4

Langkah-langkah mencari gcd (80,12) dengan algoritma eulidean sebagai berikut :
80/12 =6. sisa 8
12/8 = 1. sisa 4
8/4 = 2. sisa 0
karena pembagian terakhir menghasilkan 0, maka sisa pembagian terakhir sebelum 0 adalah 4
menjadi GCD (80,12) = GCD (12,8) = GCD (8,4) = GCD (4/0)

ada beberapa versi algoritma eulidean salah satu versinya di tuliskan dibawah ini
program eulidean

diberikan 2 buah bilangan bulat tak negatif (m>n )algoritma eulidean mencari pembagi bersama
terbesar, gcd, dari kedua bilangan tersebut, yaitu bilangan bulat positif terbesar habis membagi m dan n


algoritma

1. jika n = 0 maka
m adalah jawabanya;
stop
tetapi jika n bukan 0
lanjutkanlah langkah ke 2

2. Bagilah m Dengan n dan miaslkan r adalah sisanya

3. Gantilah M dengan N dan N nilai R , lalu kembali ke langkah 1

Dengan mengunakan m =80 dan N =12 maka eksekusi algoritma eulidean mencari GCD (80,12) sebagai berikut:

1. (i) karena n =12 bukan 0 maka lanjutkan ke langkah 2(i)
2. (i) hitung m/n = 80/12 = 6 sisanya r = 8
3. (i) nilai m baru = n lama = 12 dan n baru = r = 8 lanjutkan ke langkah 1(2)

1. (ii) karena n = 8 bukan 0 maka lanjutkan ke langkah 1(2)
2. (ii) hitung m/n =12/8=1 sisanya r= 4
3. (ii) nilai m baru = n lama = 8 dan n baru = r= 4 lanjutkan ke langkah 1(3)

1. (iii) karena n =4 bukan 0 maka lanjutkan ke langkah 2(3)
2. (iii) hitung m/n =8/12 =4 sisanya r =0
3. (iii) nilai m baru = n lam=4 dan n baru = r= 0 lanjut ke langkah 1(4)

1.(iv) karena r = 0 maka n = 4 adalah jawabananya stop. jadi PBT (80,12)=4

keterangan angka romawi si dalam kurung (i),(ii),(iii),(iv) masing-masing menyatakan per ulangan yang ke 1,ke 2 , ke 3, ke 3, ke 4 dari instruksi yang dijalankan
satu hal yang perlu dicatat langkah langkah penyelesaian masalah didalam algoritma haruslah menyatakan urutan yang logis berarti bahwa hasil dari urutan langkah-langkah yang tidak logis dapat memberikan hasil yang salah

contoh 1.1 dan contoh 1.2 berikut ini memerhatikan bahwa urutan langkah -langkah yang logis menentukan kebenaran algoritma

contoh 1.1 (mempertukarkan isi 2 buah ember)

tinjau sebuah persoalan yaitu persoalan pertukaran isi dari 2 buah ember, sebut saja ember A berwarna biru dan ember B berwarna merah . kita akan mempertukarkan isi ke dua ember tersebut menjadi A jadi warna merah dan B jadi warna biru

ember a dan ember b

perogram tukar isi

diberikan 2 buah ember a dan b ;ember a berisi air yang berwarna biru dan ember b yang berisi air yang berwarna merah

algoritma:

1. tuangkan air dari ember a kedalam ember b

2. tuangkanair dari ember ember b kedalam ember a

perhatikan bahwa algoritma tukar_isi diatas tidak akan berhasil p0ertukarannya. yang terjadi adalah pencampuran keduanya.dengan kata lain algoritma tersebut adalah salah!!

agar mendapatkan pertukaran yang benar kita memerlukan sebuah ember tambahan yang diperlukan sebagai temapat penampungan sementara, namakan ember tambahan tersebut yaitu ember c. dengan menggunakan ember c ini algoritma pertukaran isi 2 buah yang sebagai berikut: