Showing posts with label Strategi Algoritma. Show all posts
Showing posts with label Strategi Algoritma. Show all posts

Thursday, 14 June 2012

Praktikum 5 SA :

#include <cstdlib>
#include <iostream>

using namespace std;
class knapsack{
      public:
             void hitung();
             void inisialisasi();
             void output();
      private:
              int w;
              int P[20];
              int X[20];
              int W[20];
              int TotalUntung;
              int n;
              double kapasitas;
              bool MasihMuatUtuh;
              };
             
             
void knapsack::inisialisasi(){
      cout<<"masukkan angka :";
                  cin>>n;
      cout<<"batas =";
      cin>>w;
              for (int i=0; i<n; i++){
                 cout<<"weight ke - "<<i<<":";
                 cin>>W[i];
                 }
                
                 for (int i=0; i<n; i++){
                 cout<<"profit ke - "<<i<<":";
                 cin>>P[i];
                 }
 
                
     }
    
    
void knapsack::hitung(){
    
    
     for (int i=1; i<n; i++){
        X[i]=0;
        }
       
        kapasitas=w;
        TotalUntung=0;
        int i=1;
        MasihMuatUtuh=true;
       
       
     while (i<=n && MasihMuatUtuh==true) {
           if (W[i]<=kapasitas){
              X[i]=1;
              TotalUntung=TotalUntung + P[i];
              kapasitas=kapasitas - W[i];
              i=i+1;
              }
           else{
           MasihMuatUtuh=false;
           }
          
           }
           if (i<=n){
                     X[i]=kapasitas/W[i];
                     TotalUntung=TotalUntung + X[i]*P[i];
                     }
                     }
void knapsack::output(){
     cout<<"untung ="<<TotalUntung;
     }
       
int main(int argc, char *argv[])
{
    knapsack z;
    z.inisialisasi();
    z.hitung();
    z.output();
    system("PAUSE");
    return EXIT_SUCCESS;
}

Posted on 19:30 by yusufruli

No comments

Monday, 11 June 2012


#include<iostream.h>
#include <cstdlib>
#include<conio.h>
using namespace std;
class prims{
private:
int n; //no of nodes
int graph_edge[250][4]; //edges in the graph
int g; //no of edges in the graph
int tree_edge[250][4]; //edges in the tree
int t; //no of edges in the tree
int s; //source node
//Partition the graph in to two sets
int T1[50],t1; // Set 1
int T2[50],t2; // Set 2
public:
void input();
int findset(int);
void algorithm();
void output();
};
void prims::input()
{
cout<<"*************************************************\n"
<<"This program implements the prims algorithm\n"
<<"*************************************************\n";
cout<<"Enter the no. of nodes in the undirected weighted graph :";
cin>>n;
g=0;
cout<<"Enter the weights for the following edges :\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";
int w;
cin>>w;
if(w!=0)
{
g++;
graph_edge[g][1]=i;
graph_edge[g][2]=j;
graph_edge[g][3]=w;
}}}
//print the graph edges
cout<<"\n\nThe edges in the given graph are:\n";
for(int i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}
int prims::findset(int x)
{
for(int i=1;i<=t1;i++)
if(x==T1[i])
return 1;
for(int i=1;i<=t2;i++)
if(x==T2[i])
return 2;
return -1;}
void prims::algorithm()
{
t=0;
t1=1;
T1[1]=1; //The source node
t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //The reamining nodes
cout<<"\n*****The algorithm starts*****\n\n";
while(g!=0 && t!=n-1)
{
// Find the least cost edge
int min=9999;
int p;
int u,v,w;
for(i=1;i<=g;i++)
{
bool flag1=false,flag2=false;
//if u and v are in different sets
if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))
{
if(min>graph_edge[i][3])
{
min=graph_edge[i][3];
u=graph_edge[i][1];
v=graph_edge[i][2];
w=graph_edge[i][3];
p=i;
}}}
//break if there is no such edge
cout<<"The edge included in the tree is:";
cout<<" < "<<u<<" , "<<v<<" > "<<endl;
//delete the edge from graph edges
for(int l=p;l<g;l++)
{
graph_edge[l][1]=graph_edge[l+1][1];
graph_edge[l][2]=graph_edge[l+1][2];
graph_edge[l][3]=graph_edge[l+1][3];
}
g--;
//add the edge to the tree
t++;
tree_edge[t][1]=u;
tree_edge[t][2]=v;
tree_edge[t][3]=w;
//Alter the set partitions
t1++;
int m;
if(findset(v)==2)
{
T1[t1]=v;
m=v;
}
else if(findset(u)==2)
{
T1[t1]=u;
m=u;
}
int x;
for(x=1;T2[x]!=m;x++);
for(;x<t2;x++)
T2[x]=T2[x+1];
t2--;

// Print the sets
int k;
cout<<"NOW\nT1: ";
for(k=1;k<=t1;k++)
cout<<T1[k]<<' ';
cout<<endl;
cout<<"T2 :: ";
for(k=1;k<=t2;k++)
cout<<T2[k]<<' ';
cout<<endl;
cout<<"The graph edges are ::\n";
for(i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
cout<<endl<<endl;
}}
void prims::output()
{
cout<<"\nThe selected edges are ::\n";
for(int i=1;i<=t;i++)
cout<<" < "<<tree_edge[i][1]
<<" , "<<tree_edge[i][2]
<<" > ::"<<tree_edge[i][3]<<endl;
}
int main(int argc, char *argv[])
{
prims obj;
obj.input();
obj.algorithm();
obj.output();
getch();
 system("PAUSE");
    return EXIT_SUCCESS;
}

Posted on 19:01 by yusufruli

No comments



#include <cstdlib>
#include <iostream>
#define max 20
#define infinity 9999

using namespace std;
class dijkstra{
      private:
              int n,graph[max][max],colour[max],start,distance[max],predecessor[max];
              enum {green,yellow,red};
      public:
             void read_graph();
             void initialize();
             int select_min_distance_lable();
             void update(int);
             void output();
             void function();

      };
void dijkstra::read_graph(){
     cout<<"masukkan jumlah node = ";
     cin>>n;
     cout<<"masukkan nilai matrik untuk graf ::\n";
     int i,j;
     for(i=1;i<=n;i++){
                       for(j=1;j<=n;j++){
                                         cout<<"["<<i<<"],["<<j<<"]=";
                                         cin>>graph[i][j];}}
     for(i=1;i<=n;i++){
                       colour[i]=green;}
     cout<<"masukkan vertex mulai :: ";
     cin>>start;
     }
void dijkstra::initialize(){
     for(int i=1;i<=n;i++){
             if(i==start){
                          distance[i]=0;}
             else{distance[i]=infinity;}
     }
     for(int j=1;j<=n;j++){
             if(graph[start][j]!=0){
                                    predecessor[j]=start;}
             else{predecessor[j]=0;}
     }
}
int dijkstra::select_min_distance_lable(){
    int min=infinity;
    int p=0;
    for(int i=1;i<=n;i++){
            if(colour[i]==green){
                                 if(min>=distance[i]){
                                                   min=distance[i];
                                                   p=i;
                                                   }
                                 }
            }
    return p;
    }
void dijkstra::update(int p){
     cout<<"\nupdate jarak = \n";
     for(int i=1;i<=n;i++){
             if(colour[i]==green){
                                  if(graph[p][i]!=0){
                                                     if(distance[i]>graph[p][i]+distance[p]){
                                                                                             distance[i]=graph[p][i]+distance[p];
                                                                                             predecessor[i]=p;
                                                                                             }
                                                     }
                                  }
             cout<<distance[i]<<'\t';
             }
     }
void dijkstra::output()
{
 cout<<"****** The final paths and the distacnes are ******\n\n";

 for(int i=1;i<=n;i++)
 {
  if(predecessor[i]==0 && i!=start)
  {
   cout<<"path does not exists between "<<i<<" and the start vertex "
    <<start<<endl;
   exit(1);
  }
  cout<<"path for node "<<i<<" is ::\n";
  int j=i;
  int array[max];
  int l=0;
  while(predecessor[j]!=0)
  {
   array[++l]=predecessor[j];
   j=predecessor[j];
  }
  for(int k=l;k>=1;k--)
   cout<<array[k]<<"->";

  cout<<i<<endl;
  cout<<"distance is "<<distance[i]<<endl<<endl<<endl;
 }
}

void dijkstra::function()
{
 cout<<"\n**********************************************************************\n";
 cout<<"*This program is to implement dijkstra’s algorithm using colour codes* \n";
 cout<<"**********************************************************************\n\n";
 read_graph();
 initialize();  //repeate until all nodes become red
 int flag=0;
 int i;

 cout<<"\n\n******** The working of the algorithm is **********\n\n";

 for(i=1;i<=n;i++)
  if(colour[i]!=red)
   flag=1;

 cout<<"The initial distances are ::\n";
 for(i=1;i<=n;i++)
  cout<<distance[i]<<'\t';
 cout<<endl;

 while(flag)
 {
  int p=select_min_distance_lable();
  cout<<"\nThe min distance lable that is coloured yellow is "<<p;
  colour[p]=yellow;

  update(p);
  cout<<"\nnode ="<<p<<" is coloured red "<<endl;
  colour[p]=red;

  flag=0;
  for(i=1;i<=n;i++)
   if(colour[i]!=red)
    flag=1;

  cout<<endl<<endl<<endl;
 }
 output();
}

int main(int argc, char *argv[])
{
    dijkstra d;
 d.function();
    system("PAUSE");
    return EXIT_SUCCESS;
}

Posted on 18:45 by yusufruli

No comments


#include <cstdlib>
#include <iostream>

using namespace std;
int floor(double x){
                int a;
                a=x;
                return a;}

int ceil(double x){
                int a;
                a=x;
                if (a!=x)   {
                                return a+1;              }
                else         {
                                return a;  }}
int round(double x){
                int a;
                double c;
                a=x;
                c=(x-a);
                if (c>=0.5){
                                return a+1;}
                else         {
                                return a;  }}

int main(){
                double a;
cout<<"Program Pembulatan \n"<<endl;
cout<<"Masukan angka yang akan dibulatkan : ";
 cin>>a;
cout<<"FLOOR : " << floor(a) << " (dibulatkan kebawah)\n";
cout<<"CEIL  : " << ceil(a) <<  " (dibulatkan keatas)\n";
cout<<"ROUND : " << round(a) << " (dibulatkan keatas jika lebih besar dari 0,5)\n\n";
    system("PAUSE");
    return EXIT_SUCCESS;
}

Posted on 18:42 by yusufruli

No comments


#include <cstdlib>
#include <iostream>
using namespace std;
typedef int larik [10];//tipe data untuk merge
void baca_data(int A[], int n){
//proses input dan baca data
for (int i = 0; i < n; i++){
cout <<"Data ke - " << i + 1 <<" : ";
cin >> A[i];
}
}
void cetak_data(int A[], int n){
//cetak data
for (int i = 0; i < n; i++){
cout << A[i] <<" ";
}
}
void tukar_data(int *a, int *b){
//tukar data
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void minimum(int A[], int dari, int n, int *tempat){
int i, min;
min = A[dari];
*tempat = dari;
for (i = dari + 1; i < n; i++)
if (A[i] < min){
min = A[i];
*tempat = i;
}
}
void merge(larik a, int kiri, int tengah, int kanan){
int bagkir, postemp, bykel, i;
larik temp;
bagkir = tengah -1;
postemp = kiri;
bykel = kanan - kiri + 1;
while ((kiri <= bagkir) &&
(tengah <= kanan))
if ((a[kiri] <= a[tengah])){
temp[postemp] = a[kiri];
postemp = postemp + 1;
kiri = kiri + 1;
}
else {
temp[postemp] = a[tengah];
postemp = postemp + 1;
tengah = tengah + 1;
}
//kopi bagian kiri
while ((kiri <= bagkir)){
temp[postemp] = a[kiri];
postemp = postemp + 1;
kiri = kiri + 1;
}
//kopi bagian kanan
while ((tengah <= kanan)){
temp[postemp] = a[tengah];
postemp = postemp + 1;
tengah = tengah + 1;
}
//kopi ke aaray asal
for (i = 1; i <= bykel; i++){
a[kanan] = temp[kanan];
kanan = kanan -1;
}
}
void merge_sort(larik A, int kiri, int kanan){
int tengah;
if (kiri < kanan){
tengah = (kiri + kanan) / 2;
merge_sort(A, kiri, tengah);
merge_sort(A, tengah + 1, kanan);
merge(A, kiri, tengah + 1, kanan);
}
}
int main(int argc, char *argv[])
{
int data[10], n;
cout <<"MERGE SORT";
cout <<"\n\nMasukan data : ";
cin >> n;
baca_data(data, n);
cout <<"Data yang anda masukan : ";
cetak_data(data, n);
cout<<endl;
merge_sort(data, 0, n - 1);
cout <<"Setelah ditukar (Merge Sort): ";
cetak_data(data, n);
cout <<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

Posted on 18:41 by yusufruli

No comments