Korisni algoritmi

Teme vezane za console/GUI programiranje u C/C++ jeziku
3 post(ov)a • Stranica: 1/1.

Korisni algoritmi

PostPostao/la gagiD » 05 tra 2014, 13:23

1. Algoritmi sortiranja
2. Matrica - klasa



Druge teme:

Re: Korisni algoritmi

PostPostao/la gagiD » 05 tra 2014, 14:01

Algoritmi sortiranja

1. Bubble sort

cpp code
//funkcija
void bubble(int niz[] , int n) {
for ( int i=0 ; i < n ; i++) {
for ( int j = 0 ; j < n ; j++) {
if ( niz[i] < niz[j]) {
int tmp = niz[i];
niz[i] = niz[j];
niz[j] = tmp;
}
}
}
}
//primjer poziva funkcije
bubble( niz , velicina_niza);

Sporija metoda , ne koristi se ako je niz veliki.

2. Selection sort

cpp code
//funkcija
void selection(int niz[] , int n) {
for ( int i=0 ; i < n ; i++) {
int mini = niz[i];
for ( int j=i ; j < n ; j++) {
if ( niz[j] < mini ) {
mini = niz[j];
niz[j] = niz[i];
niz[i] = mini;
}
}
}
}
//primjer poziva funkcija
selection( niz , velicina_niza);


3. Insertion sort

cpp code
//funkcija
void insertion(int niz[] , int n) {
for (int i = 1 ; i <= n - 1; i++) {

int d = i;

while ( d > 0 && niz[d] < niz[d-1]) {
int tmp = niz[d];
niz[d] = niz[d-1];
niz[d-1] = tmp;

d--;
}
}
}
//primjer poziva funkcije
insertion( niz , velicina_niza);


4. Shell sort

cpp code
void shell(int niz[] , int n) {
int k;
for (int i = n/2; i > 0; i /= 2) {
for (int j = i; j<n; j++) {
int temp = niz[j];
for (k = j; k >= i ;k-=i) {
if (temp < niz[k-i]) niz[k] = niz[k-i];
else break;
}
niz[k] = temp;
}
}
}
//primjer poziva funkcije
shell( niz , velicina_niza);


5. Quick sort

cpp code
int deal(int niz[], int p, int r) {
int pivot = niz[r];

while ( p < r ) {
while ( niz[p] < pivot )
p++;
while ( niz[r] > pivot )
r--;
if ( niz[p] == niz[r] )
p++;
else if ( p < r ) {
int tmp = niz[p];
niz[p] = niz[r];
niz[r] = tmp;
}
}
return r;
}
void quick(int niz[], int p, int r) {
if ( p < r ) {
int j = deal(niz, p, r);
quick(niz, p, j-1);
quick(niz, j+1, r);
}
}
//primjer poziva funkcije
quick( niz , 0 , velicina_niza-1 );

//dodat ce se i ostali


Graficki prikaz:

slika

Koristenje biblioteka vector i algorithm:

cpp code
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
int n;
cout<<"unesite velicinu niza"<<endl;
cin>>n;

vector<int> niz(n);

for (int i=0 ; i<n ; i++) {
cin>>niz[i];
}

sort(niz.begin() , niz.end()); //sortiranje niza

//ispis niza koristenjem iteratora
for (vector<int>::iterator it=niz.begin(); it != niz.end() ; it++) {
cout<<*it<<endl;
}
return 0;
}


Vector:
Algorithm:

Re: Korisni algoritmi

PostPostao/la gagiD » 21 lis 2014, 19:14

Matrica

Podrzava osnovne operacije nad matricama kao sto su sabiranje, mnozenje, racunanje determinante, svodenje na trouglastu....
Zbog preglednosti mislim da je nabolje staviti kod u matrica.h && matrica.cpp.

*Neke operacije nisu matematici tacne, npr. sabiranje matrice s skalarom.

Funkcije napraviTrouglastu() && determinanta() ne rade ako su clanovi matrice cijeli brojevi! Bit ce update.

cpp code
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

template <typename T>
class Matrica {
int redovi;
int kolone;
vector<vector<T> > elementi;
public:
Matrica(): redovi(0) , kolone(0) , elementi(0, vector<T>(0)) {};
Matrica(int n): redovi(n) , kolone(n) , elementi(n , vector<T>(n,0)) {};
Matrica(int m, int n): redovi(m) , kolone(n) , elementi(m , vector<T>(n,0)) {};
Matrica(const Matrica<T> &m): redovi(m.redovi) , kolone(m.kolone) , elementi(m.elementi) {};
~Matrica() {};
Matrica<T> &operator=(const Matrica<T> &m);

inline Matrica<T> operator+=(const Matrica<T> &m);
inline Matrica<T> operator-=(const Matrica<T> &m);
inline Matrica<T> operator*=(const Matrica<T> &m);

inline Matrica<T> operator+=(const T x);
inline Matrica<T> operator-=(const T x);
inline Matrica<T> operator*=(const T x);

inline bool operator==(const Matrica<T> &m);
inline bool operator!=(const Matrica<T> &m);

inline T operator()(int i, int j) const;
inline T &operator()(int i, int j);

T proizvodGlavna();
T proizvodSporedna();
T sumaGlavna();
T sumaSporedna();
T determinanta();

void napraviTruglastu();
void napraviJedinicnu();

template <typename K>
friend Matrica<K> operator+(const Matrica<K> &m1, const Matrica<K> &m2);
template <typename K>
friend Matrica<K> operator-(const Matrica<K> &m1, const Matrica<K> &m2);
template <typename K>
friend Matrica<K> operator*(const Matrica<K> &m1, const Matrica<K> &m2);

template <typename K>
friend Matrica<K> operator+(const Matrica<K> &m1, const T x);
template <typename K>
friend Matrica<K> operator-(const Matrica<K> &m1, const T x);
template <typename K>
friend Matrica<K> operator*(const Matrica<K> &m1, const T x);

template <typename K>
friend Matrica<K> operator+(const T x, const Matrica<K> &m2);
template <typename K>
friend Matrica<K> operator-(const T x, const Matrica<K> &m2);
template <typename K>
friend Matrica<K> operator*(const T x, const Matrica<K> &m2);

template <typename K>
friend ostream &operator<<(ostream &, const Matrica<K> &);
template <typename K>
friend istream &operator>>(istream &, Matrica<K> &);
};

template <typename T>
Matrica<T> &Matrica<T>::operator=(const Matrica<T> &m) {
redovi = m.redovi;
kolone = m.kolone;
elementi = m.elementi;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator+=(const Matrica<T> &m) {
*this = *this + m;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator-=(const Matrica<T> &m) {
*this = *this - m;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator*=(const Matrica<T> &m) {
*this = *this * m;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator+=(const T x) {
*this = *this + x;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator-=(const T x) {
*this = *this - x;
return *this;
}

template <typename T>
Matrica<T> Matrica<T>::operator*=(const T x) {
*this = *this * x;
return *this;
}

template <typename T>
bool Matrica<T>::operator==(const Matrica<T> &m) {
if (redovi != m.redovi || kolone != m.kolone) throw "Neispravne dimenzije";
for(int i = 0; i < redovi; i++)
for(int j = 0; j < kolone; j++)
if ( elementi[i][j] != m.elementi[i][j] ) return false;
return true;
}

template <typename T>
bool Matrica<T>::operator!=(const Matrica<T> &m) {
return !( *this == m );
}

template <typename T>
T Matrica<T>::operator()(int i, int j) const {
if ( i < 0 || i > redovi-1 || j < 0 || j > kolone-1 ) throw "Ne valja index";
return elementi[i][j];
}

template <typename T>
T &Matrica<T>::operator()(int i, int j) {
if ( i < 0 || i > redovi-1 || j < 0 || j > kolone-1 ) throw "Ne valja index";
return elementi[i][j];
}

template <typename T>
T Matrica<T>::proizvodGlavna() {
if (redovi != kolone) throw "Matrica nije kvadratna";
T proizvod(1);
for (int i = 0; i < redovi; i++)
proizvod*=elementi[i][i];
return proizvod;
}

template <typename T>
T Matrica<T>::proizvodSporedna() {
if (redovi != kolone) throw "Matrica nije kvadratna";
T proizvod(1);
for (int i = 0; i < redovi; i++)
proizvod*=elementi[redovi-i-1][i];
return proizvod;
}

template <typename T>
T Matrica<T>::sumaGlavna() {
if (redovi != kolone) throw "Matrica nije kvadratna";
T suma(0);
for (int i = 0; i < redovi; i++)
suma+=elementi[i][i];
return suma;
}

template <typename T>
T Matrica<T>::sumaSporedna() {
if (redovi != kolone) throw "Matrica nije kvadratna";
T suma(0);
for (int i = 0; i < redovi; i++)
suma+=elementi[redovi-i-1][i];
return suma;
}

template <typename T>
T Matrica<T>::determinanta() {
if (redovi != kolone) throw "Matrica nije kvadratna";

Matrica<T> tmp(redovi);
tmp.elementi = elementi;

tmp.napraviTruglastu();

return tmp.proizvodGlavna();
}

template <typename T>
void Matrica<T>::napraviTruglastu() {
if (redovi != kolone) throw "Matrica nije kvadratna";

int brojac(1) , zamjena , m(kolone);

for( int i=0; i<m-1; i++ ) {
int kontrolna = 0;

if(!elementi[i][i]) {
for( int j = i; j<m-1; j++ )
if( elementi[j+1][i] != 0 && kontrolna == 0 ) {
for( int k=0; k<m; k++ ) {
zamjena = elementi[i][k];
elementi[i][k] = elementi[j+1][k];
elementi[j+1][k] = zamjena;
}
brojac *= (-1);
kontrolna++;
}
}
for(int j=i; j<m-1; j++) {
if(!elementi[j+1][i]) continue;
double koeficijent = elementi[j+1][i]/elementi[i][i];
for(int k=i; k<m; k++) {
elementi[j+1][k] += (-koeficijent) * elementi[i][k];
}
}
}
if ( brojac != 1 ) elementi[0][0] = -elementi[0][0];
}

template <typename T>
void Matrica<T>::napraviJedinicnu() {
if (redovi != kolone) throw "Matrica nije kvadratna";
for (int i = 0; i < redovi; i++)
for (int j = 0; j < redovi; j++) {
if (i == j) elementi[i][j] = 1;
else elementi[i][j] = 0;
}
}

template <typename K>
Matrica<K> operator+(const Matrica<K> &m1 , const Matrica<K> &m2) {
if (m1.redovi != m2.redovi || m1.kolone != m2.kolone) throw "Neispravne dimenzije";
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] + m2.elementi[i][j];
return pomocna;
}

template <typename K>
Matrica<K> operator-(const Matrica<K> &m1 , const Matrica<K> &m2) {
if (m1.redovi != m2.redovi || m1.kolone != m2.kolone) throw "Neispravne dimenzije";
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] - m2.elementi[i][j];
return pomocna;
}

template <typename K>
Matrica<K> operator*(const Matrica<K> &m1 , const Matrica<K> &m2) {
if (m1.kolone != m2.redovi) throw "Neispravne dimenzije";
Matrica<K> pomocna(m1.redovi, m2.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m2.kolone; j++)
for(int k = 0; k < m1.kolone; k++)
pomocna.elementi[i][j] += m1.elementi[i][k] * m2.elementi[k][j];
return pomocna;
}


template <typename K>
Matrica<K> operator+(const Matrica<K> &m1 , const K x) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] + x;
return pomocna;
}

template <typename K>
Matrica<K> operator-(const Matrica<K> &m1 , const K x) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] - x;
return pomocna;
}

template <typename K>
Matrica<K> operator*(const Matrica<K> &m1 , const K x) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] * x;
return pomocna;
}

template <typename K>
Matrica<K> operator+(const K x , const Matrica<K> &m1) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] + x;
return pomocna;
}

template <typename K>
Matrica<K> operator-(const K x , const Matrica<K> &m1) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] - x;
return pomocna;
}

template <typename K>
Matrica<K> operator*(const K x , const Matrica<K> &m1) {
Matrica<K> pomocna(m1.redovi,m1.kolone);
for(int i = 0; i < m1.redovi; i++)
for(int j = 0; j < m1.kolone; j++)
pomocna.elementi[i][j] = m1.elementi[i][j] * x;
return pomocna;
}

template <typename K>
ostream &operator<<(ostream &izlaz, const Matrica<K> &m) {
for(int i = 0; i < m.redovi; i++) {
for(int j = 0; j < m.kolone; j++)
cout<<m.elementi[i][j]<<" ";
cout<<endl;
}
return izlaz;
}

template <typename K>
istream &operator>>(istream &ulaz, Matrica<K> &m) {
for(int i = 0; i < m.redovi; i++)
for(int j = 0; j < m.kolone; j++) {
cout<<"["<<i<<"]["<<j<<"]=";
cin>>m.elementi[i][j];
}
return ulaz;
}

int main() {
Matrica<int> m1(3) , m2(3) , m3 , m4;

cout<<"Unesi prvu matricu"<<endl;
cin>>m1;
cout<<"Unesi drugu matricu"<<endl;
cin>>m2;

m3 = m1 + m2;

cout<<"Suma prve i druge matrice:"<<endl;
cout<<m3;

m4 = m1 * m2;

cout<<"Proizvod prve i druge matrice:"<<endl;
cout<<m4;

cout<<"Determinanta prve matrice: "<<m1.determinanta()<<endl;

cout<<"Suma elemenata glavne diagonale prve matrice: "<<m1.sumaGlavna()<<endl;

cout<<"Druga matrica svedena na trouglastu:"<<endl;
m2.napraviTruglastu();
cout<<m2;

return 0;
}


3 post(ov)a • Stranica: 1/1.

Na mreži

Trenutno korisnika/ca: / i 1 gost.