Translate

Kamis, 06 Desember 2012

Listing Menghitung Jenis Koin atau Uang

listing ini saya buat ketika praktikum perancangan analisis dan algoritma di lab. teknik informatika. listing dibawah ini merupakan program untuk menghitung uang atau jenis koin.

#include
#include
#define size 99
void sort(int[], int);
main()
{
int x[size],i,n,uang,hasil[size];
printf("\n Banyak Koin : ");
scanf("%d", &n);
printf("\n \nMasukkan Jenis Koin : \n");
for(i=1;i<=n;i++)
{
scanf("%d", &x[i]);
}
sort(x,n);
printf("\n Koin yang Tersedia :");
for(i=1;i<=n;i++)
{
printf("%d", x[i]);
printf("\n");
}
printf("\n");
printf("\n Masukkan Nilai yang Dipecah :");
scanf("%d", &uang);
printf("\n");
for(i=1;i<=n;i++)
{hasil[i]=uang/x[i];
uang=uang%x[i];
}
for(i=1;i<=n;i++)
{
printf("Keping %d", x[i]);
printf("-an sebanyak : %d", hasil[i]);
printf("\n \n");
}
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;
}
}
}
}

semoga listing ini bermanfaaat. :D

Selasa, 04 Desember 2012

Macam-Macam Algoritma dalam bahasa C++


TUGAS UNTUK PRAKTIKUM
PERANCANGAN ALGORITMA DAN ANALISIS PROGRAM
Description: E:\logo_gunadarma.jpg


MOH.ACENG HASIRI
54410460
3IA02



LABORATORIUM TEKNIK INFORMATIKA
UNIVERSITAS GUNADARMA
2012/2013

DAFTAR ISI

A.      ALGORITMA GREEDY
A.1  Definisi Algoritma Greedy
A.2  Contoh Program C++ Menggunakan Algoritma Greedy
B.      ALGORITMA BRUTE FORCE
B.1   Defisi Algoritma Brute Force
B.2   Contoh Program C++ menggunakan Algoritma Brute Force
C.      ALGORITMA DYNAMIC PROGRAMING
C.1   Defini Algoritma Dynamic Programing
C.2   Contoh Program C++ Menggunakan Algoritma Dynamic Programing
D.      ALGORITMA KRUSKAL
D.1  Definisi Algoritma Kruskal
D.2  Contoh Program C++ Menggunakan Algoritma Kruskal
E.       ALGORITMA DJIKSTRA
E.1   Definisi Algoritma Djikstra
E.2   Contoh Program C++ Menggunakan Algoritma Djikstra


A.    ALGORITMA GREEDY


A.1 Definisi Algoritma Greedy


Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah dengan memakai kemungkinan yang ada.  Algoritma Greedy membentuk solusi langkah per langkah, terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. keputusan yang telah di ambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.dan merupakan salah satu metode dalam optimasi.

 Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya  mengarah ke solusi optimum global (global optimum).
Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah, pada setiap langkah:
1.      mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2.      berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

A.2 Contoh Program C++ Menggunakan Algoritma Greedy


Program Penukaran Koin
#include
#include
#define size 99

void sort(int[], int);
main(){
clrscr ();
int x[size],i,n,uang,hasil[size];
printf("Banyak Koin : ");
scanf("%d", &n);

printf("\nMasukkan Jenis Koin : ");
printf("\n");
for(i=1;i<=n;i++){
scanf("%d", &x[i]);
}

sort(x,n);
printf("\nKoin yang tersedia :");
printf("\n");
for(i=1;i<=n;i++){
printf("%d",x[i]);
printf("\n");
}
printf("\n");
printf("\nMasukkan nilai yang dipecah :");
scanf("%d", &uang);
printf("\n");
for(i=1;i<=n;i++){
hasil[i]=uang/x[i];
uang=uang%x[i];
}
for(i=1;i<=n;i++){
printf("keping %d",x[i]);
printf("-an sebanyak : %d",hasil[i]);
printf("\n \n");
}
getch();
return 0;
}
void sort (int a[],int siz){
int pass, hold, j;
for (pass=1; pass
if(a[j+1]
hold=a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;}}}




B.    ALGORITMA BRUTE FORCE


B.1 Definisi Algoritma Brute Force


Algoritma Brute Force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.
Cara kerja algoritma Brute Force
1.       Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2.       Evaluasi setiap kemungkinan solusi “satu per satu” dan simpan solusi terbaik yang ditemukan sampai sejauh ini.
3.       Bila pencarian solusi berakhir, umumkan solusi terbaik
Karakteristik  Algoritma Brute Force
1.      Algoritma brute force sebenarnya bukanlah algoritma yang “cerdas” dan mangkus(efisien), karena ia membutuhkan jumlah langkah yang besar/banyak dalam penyelesaiannya dan tentu saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (na├»ve algorithm).
2.      Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tapi kalau mencari pola2 dasar, keteraturan, atau trik-trik khusus, biasanya dapat membantu membantu untuk menemukan algoritma yang lebih cerdas dan lebih mangkus lagi.
3.      Untuk persoalan2 yang kecil, kesederhanaan brute force lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus.
4.       Meskipun brute force bukan merupakan teknik pemecahan masalah yang mangkus, namun teknik brute force dapat diterapkan pada sebagian besar persoalan. Bayangkan..,sangat sulit menemukan masalah yang tidak dapat dipecahkan dengan teknik brute force, tapi ada masalah yang hanya dapat dipecahkan secara brute force

B.2 Contoh Program C++ Menggunakan Algoritma Brute Force


Program mencari Bilangan Prima, Sorting Bilangan, dan Perkalian Matriks
#include
#include
#include


void prima (),bsort(),kalimatriks();


main()
{
 start :
 int x;
 clrscr();
 printf ("\n \t Algoritma Brute Force \n");
 printf ("\n ==========================================");
 printf ("\n \t 1. Pencarian Bilangan Prima");
 printf ("\n \t 2. Sorting Bilangan");

 printf ("\n \t 3. Perkalian Matriks");
 printf ("\n \t 4. Exit ");
 printf ("\n ========================================= \n");
 printf ("\n Masukkan Pilihan (1-4) : ");
 scanf ("%d",&x);
 switch(x)
  {
 case 1  : prima ();
   goto start;
 case 2  : bsort();
   goto start;
 case 3  : kalimatriks();
   goto start;
 case 4  : return 0;
 default : clrscr();
   printf("\n \n \n \n \n \n \t \t \t Anda Salah memasukkan Input");
   printf("\n \t \t Program Akan Direstart Setelah Anda Menekan Tombol Enter");
   getch();
   goto start;
  }
}


void prima ()
{
  int bil,j;
  clrscr();
  printf ("\t \t \t Pencarian Bilangan Prima \n \n \n");
  printf ("Masukkan Data Yang Ingin Diinput: ");
  scanf("%d",&bil);
  for(j=2;j<=bil;j++)
  {
 if ((j%2>0)&&(j%3>0)&&(j%5>0)&&(j%7>0) || (j==2)||(j==3)||(j==5)||(j==7))
 printf ("%i ",j);
  }
  getch();
}


void bsort()
{
  int i,j,temp,n,bil[100];
  clrscr();
  printf ("\t \t \t Sorting Bilangan \n \n \n" );
  printf ("Masukkan jumlah bilangan: " );
  scanf ("%d",&n);
for(i=0;i
 {
  printf ("Bilangan ke-%d \t: ",i+1);
  scanf ("%d",&bil[i]);
 }
 printf ("\n");
 for(i=0;i
 {
  for(j=n-1;j>i;j--)
  {
 if (bil[i] > bil[j])
   {
 temp = bil[i];
    bil[i] = bil[j];
 bil[j] = temp;
   }
  }
 }
 printf ("Sorting:");
 for(i=0;i
 {
  printf ("%d",bil[i]);
  if (i!= n-1)
  {
 printf (",");
  }
 }
 getch();
}


void kalimatriks()
{
 int i,j,k,temp,ordo,ma[10][10],mb[10][10],mc[10][10];
 clrscr();
 printf ("\t \t \t Perkalian Matriks \n \n \n");
 printf ("Masukkan Ordo Matriks: ");
 scanf ("%d", &ordo);
 printf ("Matriks A: ");
 for(i=0;i
 {
  for(j=0;j
  {
 gotoxy((j+1)*5,i+6);
 scanf ("%d", &ma[i][j]);
  }
 }
 printf ("\n");
 printf ("Matriks B: ");
 for(i=0;i
 {
  for(j=0;j
  {
 gotoxy((j+1)*5,i+8+ordo);
 scanf ("%d", &mb[i][j]);
  }
 }
 for(i=0;i
 {
  for(j=0;j
  {
 temp = 0;
 for(k=0;k
 {
 temp += ma[i][k] * mb[k][j];
 }
 mc[i][j] = temp;
  }
 }
 printf ("\n \n");
 printf ("Hasil Matriks A * Matriks B: ");
 for(i=0;i
 {
  for(j=0;j
  {
 gotoxy((j+1)*5,i+11+ordo*2);
 printf ("%d",mc[i][j]);
  }
 }
 getch();
}



C.     ALGORITMA DYNAMIC PROGRAMING


C.1 Definisi Algoritma Dynamic Programing

Program dinamis (Dynamic programing) merupakan metode pemecahan maslah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian hingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.
Algoritma pemrograman dinamik dapat dibagi kedalam 4 langkah:
1.       Menentukan struktur dari suatu penyelesaian optimal.
2.       Mendefinisikan secara rekursif nilai dari penyelesaian optimal.
3.       Menghitung nilai dari penyelesaian optimal dengan cara bottom-up. Langkah1-3 ini merupakan basis dari penyelesaian pemrograman dinamik. Langkah 4 dapat diabaikan apabila hanya diperlukan sebuah solusi optimal.
4.       Membentuk suatu penyelesaian optimal dari informasi yang didapat.

C.2 Contoh Program C++ Menggunakan Algoritma Dynamic programing


Program mencari jalan terpendek  pada Graph
#include
#include
using namespace std;
int min(int a,int b);
int cost[10][10],a[10][10],i,j,k,c;

main()
{
  int n,m;
  cout <<"enter no of vertices";
  cin >> n;
  cout <<"enter no od edges";
  cin >> m;
  cout<<"enter the\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
a[i][j]=cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]== 0 && i !=j)
a[i][j]=31999;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
cout <<"Resultant adj matrix\n";
for(i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
  {
  if(a[i][j] !=31999)
  cout << a[i][j] <<" ";
  }
cout <<"\n";
}
getch();
}
int min(int a,int b)
{
if(a
return a;
else
return b;
}


D.    ALGORITMA KRUSKAL


D.1 Definisi Algoritma Kruskal


Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.

D.2 Contoh Program C++ Menggunakan Algoritma Kruskal

Mencari minimal spaning tree
Description: E:\1.png

#include  
#include
#include

using namespace std;

class kruskal
{
    private:
    int n; //no of nodes
    int noe; //no edges in the graph
    int graph_edge[100][4];

    int tree[10][10];

    int sets[100][10];
    int top[100];
    public:
    int read_graph();
    void initialize_span_t();
    void sort_edges();
    void algorithm();
    int find_node(int );
    void print_min_span_t();
};

int kruskal::read_graph()
{
//cout<<"Program ini Mengimplementasikan Algoritma Kruskal\n";
cout<<"Banyak titik graph : ";
cin>>n;
noe=0;

cout<<"\nJarak antar tiap titik:\n";

for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
        cout<<"("<
        int w;
        cin>>w;
            if(w!=0)
            {
            noe++;

            graph_edge[noe][1]=i;
            graph_edge[noe][2]=j;
            graph_edge[noe][3]=w;
            }
        }
    }

}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
    for(int j=1;j<=noe-i;j++)
    {
        if(graph_edge[j][3]>graph_edge[j+1][3])
        {
        int t=graph_edge[j][1];
        graph_edge[j][1]=graph_edge[j+1][1];
        graph_edge[j+1][1]=t;

        t=graph_edge[j][2];
        graph_edge[j][2]=graph_edge[j+1][2];
        graph_edge[j+1][2]=t;

        t=graph_edge[j][3];
        graph_edge[j][3]=graph_edge[j+1][3];
        graph_edge[j+1][3]=t;
        }
    }
}



cout<<"\n\nSetelah Jarak diurutkan adalah ::\n";
for(int i=1;i<=noe;i++)
cout<<"("<< graph_edge[i][1]
<<" , "<
<<" ) = "<
}

void kruskal::algorithm()
{
    
    for(int i=1;i<=n;i++)
    {
    sets[i][1]=i;
    top[i]=1;
    }

cout<<"\nRentang Yang di Pakai\n\n";

    for(int i=1;i<=noe;i++)
    {
    int p1=find_node(graph_edge[i][1]);
    int p2=find_node(graph_edge[i][2]);

        if(p1!=p2)
        {
            cout<<"Rentang yg masuk ke pohon ::"
            <<" < "<
            < "<

            tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
            tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

            // Mix the two sets

            for(int j=1;j<=top[p2];j++)
            {
                top[p1]++;
                sets[p1][top[p1]]=sets[p2][j];
            }

            top[p2]=0;
        }
        else
        {
            cout<<"Jika "
            <<" < "<
            < "<<"di masukkan, maka terbentuk siklus. jadi di hapus\n\n";
        }
    }
}

int kruskal::find_node(int n)
{
    for(int i=1;i<=noe;i++)
    {
        for(int j=1;j<=top[i];j++)
        {
        if(n==sets[i][j])
            return i;
        }
    }

    return -1;
}


int main(int argc, char *argv[])
{
    kruskal obj;
    obj.read_graph();
    obj.sort_edges();
    obj.algorithm();
       
    system("PAUSE");
    return EXIT_SUCCESS;
}





E.     ALGORITMA DJIKSTRA


E.1 Definisi Algoritma Djikstra


Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah dengan bobot-bobot sisi yang bernilai tak-negatif. Algoritma Djikstra melakukan komputasi pencarian rute terpendek antara simpul sumber dan simpul tujuan berdasarkan bobot pada sisi yang menghubungkan simpul-simpul dalam graph.
Bobot pada sisi bisa berarti jarak.waktu ataupun bobot lainnya. Jalur terpendek dalam graph adalah jumlah total minimum bobot dari sisi-sisi yang menghubungkan simpul sumber dengan simpul tujuan. Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah graf berarah yang berbobot G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.
Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.
Bobot dari semua sisi dihitung dengan fungsi
w: E → [0, ∞)
jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.
Ongkos dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.

E.2 Contoh Program C++ Menggunakan Algoritma Djikstra

Program mencari biaya perjalanan pada graph
#include
#include
#define MAXNODES 50
#define MAX1 150
#define INFINITY 5000

using namespace std;

int weight[MAXNODES][MAXNODES],i,j,distance[MAXNODES],visit[MAXNODES];
int precede[MAXNODES],final=0;
int path[MAX1];
int smalldist,newdist,k,s,d,current,n,distcurr;

void Display_Result()
{
i=d;
path[final]=d;
final++;
while(precede[i]!=s)
{
  j=precede[i];
  i=j;
  path[final]=i;
  final++;
}
path[final]=s;
printf("\nThe shortest path followed is :\n\n");
for(i=final;i>0;i--)
 printf("\t\t(%d -> %d) with cost = %d\n\n",path[i],path[i-1],weight[path[i]][path[i-1]]);
printf("\nFor total cost = %d",distance[d]);
}

main()
{
printf("\nEnter the number of nodes(Less than 50)in the matrix : ");
scanf("%d",&n);
printf("\nEnter the cost matrix :\n\n");
for(i=0;i   for(j=0;j     scanf("%d",&weight[i][j]);
printf("\nEnter the source node (0 to %d) : ",n-1);
scanf("%d",&s);
printf("\nEnter the destination node (0 to %d) : ",n-1);
scanf("%d",&d);
for(i=0;i {
  distance[i]=INFINITY;
  precede[i]=INFINITY;
}
distance[s]=0;
current=s;
visit[current]=1;
while(current!=d)
{
  distcurr=distance[current];
  smalldist=INFINITY;
  for(i=0;i     if(visit[i]==0)
    {
      newdist=distcurr+weight[current][i];
      if(newdist       {
    distance[i]=newdist;
    precede[i]=current;
      }
      if(distance[i]       {
    smalldist=distance[i];
    k=i;
      }
    }
  current=k;
  visit[current]=1;
}
Display_Result();
getch();
}




DAFTAR PUSTAKA

1.       A Hypercube Algorithm for the 0/1
KnapsackProblem.
http://www.cise.ufl.edu/~sahni/paper
s/knap.pdf.
2.       Dynamic Programming Examples:
Integer Knapsack.
http://cgm.cs.mcgill.ca/~msuder/courses/
360/lectures/integer-knapsack.html.
4.       http:// repository.upnyk.ac.id