dynamic view

click here to see this page in dynamic views.
kliknij tutaj aby zobaczyć tę stronę w widoku dynamicznym.

Heap C++ implementation / Kopiec C++

Implementacja kopca w C++ oraz metod dla tej stuktury, dostępny jest również słownik pozwalający na orientownie się w hierarchii pierwotnej kopca gdy zaburzona zostanie jego struktura np. poprzez dodanie nowych elementów etc.
Heap C++ implementation with dictionary.
English ver in comments...

/*****************************************************************************/
/* Heap C++ implementation, methods n algorithms + dictionary showing index  */
/* of an element. Polish n English menu's versions available                 */
/* compile: g++ -Wall -pedantic heap.cpp                                     */
/* how to use: ./a.out                     -> n do whatever u want           */

#include <iostream>

//#define PL
#define ENG

using namespace std;

/*****************************************************************************/
/*!
 * \brief Object
 * \param value - wartosc liczbowa
 * \param key - klucz
 */
class Object
{
public:
 int value;
 int key;

 Object()
 {
       //srand((int)time(0));
       //value=rand()%(10);
    value=0;
 }

 ~Object(){}

};
/**/
/*****************************************************************************/

/*****************************************************************************/
/*!
 * \brief Heap
 * \param Tab - tablica wartosci kopca
 * \param Dictionary - slownik
 * \param n - takie n
 */
class Heap
{
public:
 Object *Tab;
 int n;
 int *Dictionary;
/*!
 * \brief Tworzy tablice obiektow rozmiaru size
 *        oraz slownik pozwalajacy na lokaalizacje
 *        elementow kopca gdy jego porzadek zostanie
 *        zaburzony
 *
 */
 Heap(int size)
 {
  n=size;

  Tab=new Object[size+1];
  Dictionary=new int[size+1];

  for(int i=1;i<=size+1;i++)
  {
  Tab[i].key=i;
  }

  for(int i=1;i<size+1;i++)
  {
  Dictionary[i]=Tab[i].key;
  }
 }
~Heap(){cout<<"boom!!! free machines's brain"<<endl;
            delete[] Tab; delete Dictionary;}


/*!
 * \brief Ustawia wartosc tablicy o danym kluczu
 */
void ChangeKElement(int k,int v)
{
         Tab[Dictionary[k]].value=v;
}

/*!
 * \brief Wypisuje wartosci kopca
 */
void PrintHeap()
{
    cout<<"Heap:"<<endl<<endl;;
    for(int i=1;i<n+1;i++)
        {
   cout<<Tab[i].value<<endl;
        }
}

/*!
 * \brief Wypisuje wartosci kluczy
 */
void PrintKeys()
{
    cout<<"Keys:"<<endl<<endl;;
    for(int i=1;i<n+1;i++)
  {
   cout<<Tab[i].key<<endl;
  }
}

/*!
 * \brief Wypisuje slownik
 */
void PrintDictionary()
{
    cout<<"Dictionary:"<<endl<<endl;;
    for(int i=1;i<n+1;i++)
  {
   cout<<Dictionary[i]<<endl;
  }
}

/*!
 * \brief Naprawia kopiec iteracyjnie
 */
void FixHeapIt()
{
       int p,d,tmp_w,tmp_k;


       for(int i=2;i<=n;i++)
       {
        d=i;
        p=d/2;


        tmp_w=Tab[i].value;
        tmp_k=Tab[i].key;

         while((p>0)&&(Tab[p].value>tmp_w))
          {
           Tab[d].value=Tab[p].value;
           Tab[d].key=Tab[p].key;
           Dictionary[Tab[p].key]=d;
            d=p;
            p=d/2;

         Tab[d].value=tmp_w;
         Tab[d].key=tmp_k;
         Dictionary[tmp_k]=d;
       }
    }

}

/*!
 * \brief tzw swap - zamiana elementow
 */
void siup(int *ptr1, int *ptr2)
{
   int tmp=*ptr1;
   *ptr1=*ptr2;
   *ptr2=tmp;
}

/*!
 * \brief Naprawia kopiec rekurencyjnie
 */
void FixHeapRe(int i)
{
       int star_wars=i;
       if(((2*i)<n+1) && (Tab[2*i].value<Tab[star_wars].value))
                      star_wars=2*i;
       if(((2*i+1)<n+1) && (Tab[2*i+1].value<Tab[star_wars].value))
                      star_wars=2*i+1;
       if(star_wars!=i)
         {
           siup(&Tab[star_wars].value,&Tab[i].value);
           siup(&Tab[star_wars].key,&Tab[i].key);
           siup(&Dictionary[Tab[star_wars].key],&Dictionary[Tab[i].key]);
           FixHeapRe(star_wars);
         }
}

/*!
 * \brief Buduje kopiec
 */
void BuildHeap()
{
    for (int i=n+1;i>0;i--)
       {
         FixHeapRe(i);
        }
}

/*!
 * \brief Wypisuje proste menu
 */
    void PrintMenu()
    {
         char opt='?';
         #ifdef ENG
         while(opt!='q')
         {
                          cout<<" "<<endl;
          cout<<"p - print heap"<<endl;
          cout<<"& - print keys"<<endl;
          cout<<"# - print dictionary"<<endl;
          cout<<"z - change value of key's element"<<endl;
          cout<<"r - fix heap"<<endl;
          cout<<"q - quit"<<endl;
          cin>>opt;

          switch(opt)
          {
                       case 'p': cout<<"--------"<<endl;
                                  PrintHeap(); opt='?'; break;
                       case '&': cout<<"--------"<<endl;
                                  PrintKeys(); opt='?'; break;
                       case '#': cout<<"--------"<<endl;
                                  PrintDictionary(); opt='?'; break;
                       case 'z': cout<<"object's key: "<<endl;
                                  int k1,w1;
                                  cin>>k1;
                                  cout<<"object's value: "<<endl;
                                  cin>>w1;
                                  ChangeKElement(k1,w1);opt='?'; break;
                       case 'r': cout<<"fixed:"<<endl;
                                   BuildHeap(); PrintHeap(); opt='?'; break;
                       case 'q': cout<<"maskotky's toy says hasta la vista!"<<endl;break;
          }
          #endif
          #ifdef PL
         while(opt!='q')
         {
                          cout<<" "<<endl;
          cout<<"p - wypisz kopiec"<<endl;
          cout<<"& - wypisz klucze"<<endl;
          cout<<"# - wypisz slownik"<<endl;
          cout<<"z - zamien wartosc elementu o danym kluczu"<<endl;
          cout<<"r - napraw kopiec"<<endl;
          cout<<"q - zakoncz"<<endl;
          cin>>opt;

          switch(opt)
          {
                       case 'p': cout<<"--------"<<endl;
                                  PrintHeap(); opt='?'; break;
                       case '&': cout<<"--------"<<endl;
                                  PrintKeys(); opt='?'; break;
                       case '#': cout<<"--------"<<endl;
                                  PrintDictionary(); opt='?'; break;
                       case 'z': cout<<"klucz: "<<endl;
                                  int k1,w1;
                                  cin>>k1;
                                  cout<<"wartosc: "<<endl;
                                  cin>>w1;
                                  ChangeKElement(k1,w1);opt='?'; break;
                       case 'r': cout<<"naprawiony:"<<endl;
                                   BuildHeap(); PrintHeap(); opt='?'; break;
                       case 'q': cout<<"maskotky's toy says hasta la vista"<<endl; break;
          }
          #endif
     }
    }
};
/**/
/*****************************************************************************/

int main()
{
    cout<<"\nhello, this is heap toy!"<<endl;

    Heap My_Heap(8); //kopiec ma 8 elementow

    // ustawienie elementow kopca
    My_Heap.ChangeKElement(1,4);
    My_Heap.ChangeKElement(2,3);My_Heap.ChangeKElement(3,7);
    My_Heap.ChangeKElement(4,9);My_Heap.ChangeKElement(5,8);
    My_Heap.ChangeKElement(6,5);My_Heap.ChangeKElement(7,2);
    My_Heap.ChangeKElement(8,1);
    //

    //My_Heap.BuildHeap();
    //My_Heap.PrintHeap();
    //My_Heap.PrintKeys();
    //My_Heap.PrintDictionary();

    My_Heap.PrintMenu();

 return 0;
}

&chill_out

                                           
-slow down, cowboy!

NEH algorithm C++ implementation / implementacja algorytmu NEH

Implementacja algorytmu NEH z  akceleracją w C++.
NEH algorithm with acceleration,  C++ implementation.
The program has 3 functions: data reading, data writting and NEH algorithm solving problem function based on read data file. The program displays time. Compilation: Microsoft Visual C++ 2010 Express.

//////////////////////////////////////////////////////////////////////////
// program posiada 3 funkcje:
// wczytywania danych, zapisywania danych, rozwiazywania problemu
// przeplywowego algorytmem NEH z akceleracja
// posiada rowniez funkcje pomocnicze oraz odpowiednie struktury danych
// program wyswietla czas dzialania algorytmu, zmienna cmax nie wyswietlana
// dla kolejnych instancji przechowuje cmax
// kompilacja: Microsoft Visual Studio 2010 

#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#include<Windows.h>

#define INSTANCE_AMOUT 120
#pragma warning(disable: 4996)

using namespace std;

struct JobsData
{ 
 int no;
 int time;
};

struct AllData
{
 int **Tab_Job;
 int jobs; //liczba zadan
 int machines; //liczba maszyn
 list<JobsData> Jobs_List;  //lista zadan posiada nr zadania i calkowity czas potrzebny do spedzenia na maszynach
 vector<int>solution; // tablica uszeregowan czasow zadan
};

bool compare(const JobsData& _jd1, const JobsData& _jd2)
{ 
    return _jd1.time > _jd2.time; 
}

int clear_matrix(int **Tab,int x, int y);
void print_matrix(int **Tab, int x, int y);

/////////////////////////////////////////////////
// zamien vector'y
void swap_V(int &x,int &y);
//
/////////////////////////////////////////////////

/////////////////////////////////////////////////
//  funkcja wczytuje dane z odpowiedniego pliku
// bench_fs.txt
// PRE: AllData - wskaznik na strukture danych 
//      z elementami niezbednymido wykonania 
//  algorytmu,
//  pFile - wskaznik na otwarty plil
// POST: brak
//
void GetData(AllData *D, FILE *pFile);
//
/////////////////////////////////////////////////

/////////////////////////////////////////////////
//  funkcja wczytuje dane z odpowiedniego pliku
// bench_fs.txt
// PRE: AllData - wskaznik na strukture danych 
//      z tablica wynikowa solution
//  pFileOut - wskaznik na plik do zapisu
// POST: brak
//
void ToFile(AllData *W, FILE *pFileOut);
//
/////////////////////////////////////////////////

////////////////////////////////////////////////
// funkcja implementujaca algorytm NEH
// z akceleracja
// PRE: AllData - wskaznik na strukture danych
//      z elementami niezbednymi do wykonania
//  algorytmu NEH
// POST: brak
void DoNEH_acc(AllData *N);
//
////////////////////////////////////////////////



//////////////////////////////////////////////////////////////////////////
// main
int main()
{ 
 __int64 start, stop, freq;

 AllData *ins = new AllData[INSTANCE_AMOUT];
 FILE *pFile; 
 pFile=fopen("bench_fs.txt","r");
 
 for(int instance = 0; instance < INSTANCE_AMOUT; instance++) // for dla kolejnych instancji
  {
   GetData(ins,pFile); //wczytaj dane z pliku
   ins++;
     }
 fclose(pFile);
 ins=ins-INSTANCE_AMOUT;

 QueryPerformanceCounter((LARGE_INTEGER*)&start);

 for(int instance = 0; instance < INSTANCE_AMOUT; instance++)
 {
   DoNEH_acc(ins); //uszereguj je NEH'em
   ins++;
 }

 QueryPerformanceCounter((LARGE_INTEGER*)&stop);  
 QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
 cout<<" "<<endl;
 cout<<"time: " << ((double)(stop-start))/freq << "s" << endl; 

 ins=ins-INSTANCE_AMOUT;
 FILE *pFileOut;
 pFileOut=fopen("data_out.txt","w");



 for(int instance = 0; instance < INSTANCE_AMOUT; instance++)
 {
   ToFile(ins,pFileOut); //zapisz dane do pliku
   ins++;
 }
 fclose(pFileOut);
 
 getchar();
 return 0;
}
// koniec main
//////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////
//  GetData
void GetData(AllData *D, FILE *pFile)
{
 int E_time;//suma czasow jednego zadania na wszystkich maszynach
 int time; //czas zadania na maszynie
 int nvm;//pomijana
 char iname[6];//nazwa instancji w pliku 
 JobsData Job; //dane zadania

 if(pFile == NULL){fprintf(stderr,"Blad: Nie podano uchwytu do pliku\n");exit(-1);}

   fscanf(pFile,"%s",iname);
   fscanf(pFile,"%d",&D->jobs);
   fscanf(pFile,"%d",&D->machines);

   D->Tab_Job = new int * [D->machines]; // i-zadan na j-maszynach
    for (int j = 0; j < D->machines; j++){
     D->Tab_Job[j] = new int[D->jobs];
     }

   for(int i = 0; i < D->jobs; i++)
   {
     E_time = 0; 
    for(int j = 0; j < D->machines; j++)
    {
     fscanf(pFile,"%d",&nvm);
     fscanf(pFile,"%d",&time);
     E_time = E_time + time;
     D->Tab_Job[j][i] = time;

    }
    Job.no = i+1;
    Job.time = E_time;
    D->Jobs_List.push_back(Job);
   }

  


  
}
// koniec funkcji GetData
/////////////////////////////////////////////////

/////////////////////////////////////////////////
// ToFile
void ToFile(AllData *W, FILE *pFileOut)
{
 for(int i = 0; i < W->jobs; i++)
 {

  fprintf(pFileOut,"%d ", W->solution[i]);

 }
 fprintf(pFileOut,"\n");
}
// koniec ToFile
/////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////
// NEH z akceleracja
void DoNEH_acc(AllData *N)
{
 int max, min;
 int _dict = 0;
 int new_job;
 int cmax;
 int tmp_job;
 vector<int>max_vect; 
 N->solution.clear();
 N->Jobs_List.sort(compare); //mam uszeregowane zadania ze zgledu na czas
 N->solution.push_back(N->Jobs_List.front().no);// dodaje do tablicy 1 element posortowanej listy zadan 
 N->Jobs_List.pop_front(); // sciagam ten element z listy, na liscie o jedno zadanie mniej


 int **E = new int*[N->machines+1]; //tworze macierz E
  for (int i = 0; i < N->machines+1; i++)
  {
   E[i] = new int[N->jobs];
  }

 int **Q= new int*[N->machines+1]; //tworze macierz Q
  for (int i = 0; i < N->machines+1; i++)
  {
   Q[i] = new int[N->jobs];
  }
 int **F= new int*[N->machines+1]; //tworze macierz F
  for (int i = 0; i < N->machines+1; i++)
  {
   F[i] = new int[N->jobs];
  }

 int **F_Q= new int*[N->machines+1]; //tworze macierz F
  for (int i = 0; i < N->machines+1; i++)
  {
   F_Q[i] = new int[N->jobs];
  }
  clear_matrix(E,N->machines+1,N->jobs); //
  clear_matrix(Q,N->machines+1,N->jobs); // wypelniam je zerami
  clear_matrix(F,N->machines+1,N->jobs); //
  clear_matrix(F_Q,N->machines+1,N->jobs);
///////////////////////////////////////////////////////////////////////
// poczatek petli dla kazdego zadania
 while(N->Jobs_List.size() != 0)
 {
 max_vect.clear();
 for(int i=0; i < (int)N->solution.size(); i++) ////////////////////////////////////////////////////////////////////////////////// matrix E
  {
   for(int j=0; j < N->machines; j++)// w pierwszej kolumnie
   {
    
    E[j+1][i+1] = max(E[j][i+1],E[j+1][i]) + N->Tab_Job[j][N->solution[i]-1];
   }

  }
 for(int i = (int)N->solution.size()-1; i >= 0; i--) ////////////////////////////////////////////////////////////////////////////////// matrix Q
  {
   for(int j = N->machines-1; j >= 0; j--)// w pierwszej kolumnie
   {
    
    Q[j][i] = max(Q[j+1][i],Q[j][i+1]) + N->Tab_Job[j][N->solution[i]-1];
   }

  }
 
 new_job = N->Jobs_List.front().no; // sciagam nowe zadanie
 N->Jobs_List.pop_front();          //
 
 for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F
  {
   for(int j=0; j < N->machines; j++)// w pierwszej kolumnie
   {
    
    F[j+1][i] = max(E[j+1][i],F[j][i]) + N->Tab_Job[j][new_job-1];
   }

  }
 for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F_Q
  {
   for(int j=0; j < N->machines; j++)// w pierwszej kolumnie
   {
    
    F_Q[j][i] = Q[j][i]+F[j+1][i];
   }

  }

 for(int i=0; i < (int)N->solution.size()+1; i++) // znajduje maxa poszczegolnych kolumn w macierzy F+Q
  {
   max = 0;
   for(int j=0; j < N->machines; j++)
   {
    if(F_Q[j][i] > max) {max = F_Q[j][i];}
   }
   max_vect.push_back(max);
  }

 min=999999;
 for(int i=0; i < (int)max_vect.size(); i++)
 {
  if(max_vect[i]<min){ min = max_vect[i];
  _dict = i;} // _slownik_it zeby znac indeks na ktory mam wstawic to zadanie
 }
 cmax = min;
 
 N->solution.push_back(0);
 for(int i = _dict; i < (int)N->solution.size(); i++)
 {
  swap_V(N->solution[i],tmp_job);
 }
 N->solution[_dict] = new_job;


} //koniec while
} // koniec funkcji
//
/////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////
// funkcje dodatkowe
void swap_V(int &x,int &y) //swap4vector
{
 int temp;
 temp=x;
 x=y;
 y=temp;
}

int clear_matrix(int **Tab,int x, int y)
{
 for(int i = 0; i < x; i++)
  for(int j = 0; j < y; j++)
   Tab[i][j]=0;
 return 0;
}

void print_matrix(int **Tab, int x, int y)
{
 for(int i = 0; i < x; i++){ 
  for(int j = 0; j < y; j++)
  {cout<<Tab[i][j];}
  cout<<" "<<endl;}
}
//
/////////////////////////////////////////////////////////////////////

co?/what?

Posty będą zamieszczane w języku polskim i angielskim. Będą one dotyczyły zagadnień związanych z poniższymi tematami:
-algorytmy,
-sztuczna inteligencja,
-przetwarzanie obrazów, 
-robotyka,
-automatyka,
-hardcore lifestyle i inne.

 ========================================================================


Posts will be published in Polish and English (maybe;)) and will follow underground, mainstream, ready solutions in:
 -algorithms,
 -artificial intelligence,
 -image processing,
 -robotics,
 -automatition n control engeneering,
 -hardcore lifestyle and traveling.

hello world

hello world
this is maskotki