Tuesday, February 23, 2016
Pada tutorial
kali ini akan menggunakan algoritma greedy. Algoritma greedy merupakan
algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai
maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal
dengan istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak
akan menghasilkan solusi paling optimal, bagitupun algoritma greedy biasanya
memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.
Tutorial ini
akan membahas kasus penukaran koin dengan menggunakan C++. Untuk memulainya,
lakukan langkah-langkah berikut :
1. Jika belum
memiliki compiler c++ nya, maka harus mendownload terlebih dahulu ( disini saya
menggunakan dev c++ ).
2. Jika sudah
ketikkan listing program berikut :
Pada setiap langkah, pilihlah
koin dengan nilai terbesar dari himpunan koin yang tersisa.
|
Jenis koin yang dimasukkan :
100, 200, 500, 1000
Koin yang tersedia :
(diurutkan dari yang terbesar ke kecil) 1000,500, 200, 100
Masukkan nilai yang di pecah :
5500
Langkah 1 : pilih
koin 1000 sebanyak 5 (Total 5000)
Langkah 2 : pilih koin 500 sebanyak 1(total 5500), sudah selesai
tetapi masih mengecek sisa koin
Langkah 3 : pilih koin
200 sebanyak 0 (total 5500)
Langkah 4 : pilih koin 100 sebanyak 0 (total 5500)
|
LISTING PROGRAM
|
#include<stdio.h>
#include<conio.h>
#define size 99
void sort(int[], int);
main()
{
int x[size],i,uang,n,k,hasil[size];
printf("\n Banyak Koin : ");
scanf("%d", &n);
printf("\n \n Masukan Jenis Koin :
\n");
for (i=1;i<=n;i++)
{
scanf("\n %d", &x[i]);
}
sort(x,n);
printf("\n Koin yang tersedia :
\n");
for (i=1;i<=n;i++)
{
printf("%d",x[i]);
printf("\n");
}
printf("\n");
printf("\n Masukan Nilai yang dipecah
: ");
scanf("%d", &uang);
printf("\n");
for (i=1;i<=n;i++)
{
hasil[i]=uang/x[i];
uang=uang%x[i];
k=uang%x[i];
}
for (i=1;i<=n;i++)
{
printf("Keping %d", x[i]);
printf("-an sebanyak : %d",
hasil[i]);
printf("\n \n");
}
printf("sisanya adalah %d",k);
getch();
return 0;
}
void sort (int a[], int siz)
{
int pass, hold,j;
for (pass=1;pass<=siz-1;pass++){
for (j=0;j<=siz-2;j++){
if (a[j+1]<a[j+2]){
hold = a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;
}}}}
|
LOGIKA
PROGRAM
Apabila sudah mengetikkan listing programnya,
disimpan koin.cpp
§ #include
<stdio.h> merupakan Library untuk input/output pada program,tanpa menyertakan
code ini kita tidak bisa melakukan pengoperasian
input dan output.
§ #include<conio.h> merupakan fungsi library console
i/o untuk memanggil fungsi input output untuk menggunakan perintah getch.
§ #define
size 99 merupakan fungsi untuk
menentukan batasan ukuran data yang ingin diinput. Apabila lebih dari 99 maka
data yang sudah diinput tidak dapat di eksekusi.
§ void
sort(int[],int); Merupakan Main procedure atau bisa dibilang sebagai program utama berbentuk prosedur untuk mengurutkan data yang akan kita masukan
(input).
§ main()
merupakan
badan utama dari suatu progam.
|
int x[size],i,uang,n,k,hasil[size]; A
printf("\n Banyak Koin : "); B
scanf("%d", &n); C
printf("\n \n Masukan Jenis Koin :
\n");
for (i=1;i<=n;i++) D
{
scanf("\n %d", &x[i]);
}
|
§ A, Merupakan peendeklarasian variabel x dalam bentuk array, i ,
uang , n dan k bertipe data integer dan variabel hasil dalam bentuk array.
§ B, printf adalah untuk menampilkan output dengan type data string
yang dideklarasikan yaitu “Banyak koin : “ pada saat program dijalankan.
§ C , scanf adalah membaca input-an dari dari variabel yang diinput
yaitu variabel n dengan &n. %d berfungsi untuk menentukan variabel n yg diinput bertipe data
integer atau decimal.
§ D,
Merupakan
perulangan for yang mendeklarasikan nilai awal variabel i=1, nilai i lebih kecil
sama dengan n dan increment i (i++) nilai I bertambah 1
|
sort(x,n); E
printf("\n
Koin yang tersedia : \n");
for
(i=1;i<=n;i++)
{
printf("%d",x[i]);
printf("\n");
}
for
(i=1;i<=n;i++)
{
scanf("\n
%d", &x[i]);
}
for
(i=1;i<=n;i++)
|
§ sort(x,n), Merupakan fungsi untuk memanggil
fungsi sort yang mengurutkan dari nilai terbesar sampai terkecil, dalam hal ini
adalah variabel x dan n yanfg bertipe integer.
 for (i=1;i<=n;i++)
{
hasil[i]=uang/x[i];F
F
uang=uang%x[i];
k=uang%x[i];
|
§ Merupakan
fungsi perulangan for dimana nilai awal i adalah 1 sampai kondisi akhir nilai i
kurang dari sama dengan n. Selama kondisi masih terpenuhi, maka akan dilakukan
iterasi dengan menjalankan program hasil array sebagai hasil dari uang dibagi
array x, dan uang sebagai hasil uang mod array x. Kemudian setelah iterasi
berhasil, k merupakan hasil dari uang mod array x.
getch();
return 0;
}
§ Getch, Merupakan syntax untuk membaca hasil langsung dari console.
Sedangkan return 0 merupakan pengembalian statement yang sudah diolah, dengan
tanpa nilai.
|
void sort
(int a[], int siz)
{
int pass,
hold,j;
for
(pass=1;pass<=siz-1;pass++){
for
(j=0;j<=siz-2;j++){
if
(a[j+1]<a[j+2]){
hold =
a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;
}}}}
|
§ void sort, Merupakan method dimana algoritma dimulai, disini dilakukan
proses pengurutannya, sebelum menjadi output yang ditampilkan di layar fungsi
ini harus di olah terlebih dahulu, setelah diolah kemudian ditampilkan dilayar.
OUTPUT
