PEMROGRAMAN

ALGORITMA PEMROGRAMAN

KELOMPOK 2

Velta Boenika Yuwono	112144368
Wahy Daniah	112144371
Wahyu Puji Riyanto	112144372

A.   Dasar teori

Ada suatu konsep yang paralel dengan konsep faktor persekutuan terbesar (FPB), yang dikenal faktor persekutuan terkecil (KPK). Suatu bilangan bulat c disebut kelipatan persekutuan dari bilangan-bilangan bulat tak nol a dan b jika a c dan b c. Hal ini berarti pula nol adalah kelipatan persekutuan dari a dan b. Perlu diingat pula bahwa ab dan –(ab) adalah kelipatan persekutuan dari a dan b, dan salah satunya positif. Dengan menggunakan prinsip terurut sempurna (well ordering principle), himpunan kelipatan persekutuan dari a dan b harus sebuah bilangan bulat terkecil; kita menyebutnya kelipatan persekutuan terkecil dari a dan b, dan ditulis KPK(a, b).

Definisi

Kelipatan persekutuan terkecil dari dua bilangan bulat tak nol a dan b, dilambangkan KPK(a, b), adalah bilangan positif m yang memenuhi:

(i) a m dan b m.

(ii) Jika a c dan b c dengan c 0 maka m c.

Sifat 1

Untuk bilangan-bilangan bulat positif a dan b, berlaku

FPB(a, b). KPK(a, b) = ab

Sifat 2

Untuk suatu bilangan-bilangan bulat positif a an b, KPK(a, b) = ab jika dan hanya jika FPB(a, b) = 1.

Seperti pada FPB, ada beberapa metode untuk menentukan KPK dari dua buah bilangan yang diberikan, yaitu:

1. Metode Irisan Himpunan.

Di dalam metode irisan himpunan, pertama kita tentukan himpunan kelipatan-kelipatan positif dari bilangan pertama dan bilangan kedua, kemudian kita tentukan himpunan persekutuan kelipatan dari bilangan-bilangan itu, dan akhirnya kita pilih bilangan terkecil dari himpunan itu.

2. Metode Faktorisasi Prima.

Metode irisan himpunan untuk menentukan KPK sering kali terlalu panjang, khususnya ketika digunakan untuk menentukan KPK dari tiga atau lebih bilangan-bilangan asli. Metode lain, yang mungkin lebih efisien, untuk menentukan KPK dari beberapa bilangan adalah metode faktorisasi prima.

3. Algoritma Euclide

Untuk menentukan KPK(a, b) dengan cara ini, kita memanfaatkan pengetahuan kita tentang algoritma Euclide untuk menentukan FPB(a, b) dan hubungan antara KPK dan FPB, yaitu FPB(a, b). KPK(a, b) = ab untuk bilangan-bilangan bulat positif a dan b.

Cara ini sangat berguna untuk mencari KPK dari dua buah bilangan a dan b jika dengan faktorisasi prima tidak mudah untuk ditentukan. FPB (a, b)-nya.

4. Metode Pembagian dengan Bilangan Prima

Metode lain untuk menentukan kelipatan persekutuan terkecil (KPK) dari beberapa bilangan asli adalah menggunakan pembagian dengan bilangan prima. Metode ini mulai dengan bilangan prima terkecil yang dapat membagi paling sedikit satu dari bilangan yang diberikan, kemudian proses pembagian ini dilanjutkan sampai baris di mana jawabannya berisi bilangan–bilangan 1.

B. Algoritma KPK

1.      Permasalahan

2.      Program mencari KPK dari 2 buah bilangan

3.      Solusi

4.      Mulai (start)

5.      Masukan dua buah bilangan, x, y

6.      Carilah P dengan P=KPK dari x,y

7.      Jika x<y, bila benar kerjakan untuk n=1, w!=0, n++ maka P=y*n , w=P mod x

8.      Bila benar maka tampilkan P

9.      Jika x<y, bila salah kerjakan dengan n=1, w!=1, n++ maka P=x*n , w=P mod y

10.  Bila salah lakukan perulangan

11.  Bila benar, tampilkan P

12.  Selesai

13.  Di bawah ini flow chartnya;

C.   Source KPK

#include <stdio.h>

main()

{

int x, y, P;

printf("KELOMPOK 2\n\n");

printf("KPK dari 2 buah bilangan\n\n");

printf("====================================\n\n");

printf("Velta Boenika Yuwono  [112144368]\n");

printf("Wahy Daniah           [112144371]\n");

printf("Wahyu Puji Riyanto    [112144372]\n");

printf("....................................\n\n");

printf("Masukan 2 buah bilangan\n");

printf("\nBilangan pertama:");

scanf("%d",&x);

printf("\nBilangan kedua:");

scanf("%d",&y);

P=kpk(x,y);

printf("\nKPK dari kedua bilangan adalah:%d\n",P);

system("pause");

}

int kpk(int x,int y)

{

int w=1, P, n;

if(x<y)

{

for(n=1;w!=0;n++)

{

P=y*n;

w=P%x;

}

}

else

{

for(n=1;w!=0;n++)

{

P=x*n;

w=P%y;

}

}

system("pause");

return(P);

}

D.   Tampilan Program Akhir