Uređivanje niza

Složeniji proces od  pretraživanja niza je uređivanje. Da bi se niz uredio neophodno je da se svaki element uporedi sa ostalim elementima, po potrbi, izvršiti njihovu međusobnu zamenu. Niz može biti sortiran u rastućem i opadajućem redosledu. Postoje nekoliko algoritama za sortiranje nizova.

Metod izbora (selection sort)

Zasniva se na veoma jednostavnoj ideji, izabrati najmanji element niza i dovesti ga na prvo mesto, zatim drugi najmanji, na drugo mesto, itd. do kraja niza.

Primer koji sortira niz u rastućem redosledu

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje*/
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
pom=a[i];
a[i]=a[j];
a[j]=pom;
}
}
}
/*Ispis niza*/
cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;

}
system(„PAUSE“);
return EXIT_SUCCESS;
}

selekt sort

Pr1.

Napravite program koji niz a čiji elementi su celi brojevi uređuje u rastućem redosledu koristeći funkcije?

Rešenje:

#include
#include
using namespace std;
void ucitajniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza“<<endl; cin>>a[i];
}
}
void razmeni(int *a, int *b)
{
int pom=*a;
*a=*b;
*b=pom;
}
void sortiraj(int a[], int n)
{
int i, j;
for (i=0;i<n-1;i++)
{
for (j=i+1;j<n;j++) { if (a[i]>a[j])
razmeni(&a[i], &a[j]);
}
}
}
void ispisiniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<“ a[„<<i+1<<„] je „<<a[i]<<endl;

}

int main(int argc, char *argv[])
{
int a[10],n;
cout<<„Unesi broj elemenata niza“<<endl; cin>>n;
ucitajniz(a,n);
sortiraj (a,n);
cout<<“ Sortirani niz:“<<endl;
ispisiniz(a,n);
system(„PAUSE“);
return EXIT_SUCCESS;
}

Metod mehuriće (babl sort)

Algoritam sortiranja bubble sort poredi dva susedna elementa niza i ako su pogrešno rasporežđeni zamenjuje im mesta. Posle porežđnja svih susednih parova najmanji od njih će isplivati na kraj niza. Zbog toga se ovaj metod naziva metod mehurića. Da bi se najmanji broj nesortiranog dela niza doveo na svoje mesto treba ponoviti postupak

Primer sortira niz metodom babl sort u rasući redosled

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{

/* deklaracija niza i promenljive koje se koriste*/
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje- babl sort*/
for(i=n-1; i>0; i–)
{
for(j=0; j<i; j++)
{
if(a[j]>a[j+1])
{
pom=a[j];
a[j]=a[j+1];
a[j+1]=pom;
}
}
}
/*Ispis niza*/
cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
system(„PAUSE“);
return EXIT_SUCCESS;
}

bublesort.JPG

Metod isort

Insert sort, u svakom trenutku je početak niza sortiran a sortiranje se vrši tako što se jedan po jedan element niza sa kraja ubacuje na odgovarajuće mesto.

Primer prikazuje uređivanje niz u opadajućem redosledu metodom isort

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje*/

for(i=1; i<n; i++)
{
for(j=i; (j>0) && (a[j]>a[j-1]); j–)
{

pom=a[j];
a[j]=a[j-1];
a[j-1]=pom;
}
}
/* Ispis niz*/

cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;

}
system(„PAUSE“);
return EXIT_SUCCESS;
}

isort.JPG

Pretraživanje nizova

Veoma često javlja se potreba ispitivanja da li određeni element pripada određenom skupu, da li je moguće elemente skupa urediti po nekom kriterijumu? Znamo da skup istih elemenata po tip daju niz, kada je reč o programiranju, pa tehnika pretraživnja i uređivanja nizova čini jednu od najznačajniih grupa obrade podataka.

Za pretraživanje nizova postoje dva algoritma koji se načešće koriste u praksi

Sekcencionalno pretraživanje

Uzastopno upoređivanje elemenata niza sa traženom vrednošću (provera da li se vrednost nalazi  u nizu), sve dok se vrednost ne pronađe ili kada se dođe do kraj niza (tražena vrednost nije u nizu) su karakteristike sekvencionalnog pretraživana. 

Sekvencionalno pretraživanje          Funkcija za sekvencionalno pretraživanje

Da je tražena vrednost pronađena zna se po tome što je ciklus pretraživanja završen pre kraja niza (i<n). Vrednost funkcije je 1 u slučaju uspeha, 0 u slučaju neuspeha.

Jednostavnost je dobra strana pretraživanja, mana je relativno veliki broj proba da bi se došlo do rezultata.

Pr1.

U jednom razredu ima n učenika. Prosečna standardna visina je b. da li u razredu ima učenika sa standardnom visinom?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;

/*Funkcija za pretrazivanje*/
int sektra1 (int a[],int n,int b)
{
int i;
for (i=0;i<n && a[i]==b;i++)
return i<n;
}

/*glavni program*/
int main(int argc, char *argv[])
{
int a[30];
int b, n, i;
cout<<„Unesi standardnu visinu?“<<endl;
cin>>b;
cout<<„Unesi broj ucenika u razredu?“<<endl;
cin>>n;
cout<<„Unesi visine svakog ucenika?“<<endl;
for (i=0;i<n;i++)
{
cout<<„Unesi visinu ucenika sa rednim brojem „<<i+1<<endl;
cin>>a[i];

}
cout <<sektra1(a,n,b);

if (sektra1 (a,n,b)==1)
{
cout <<„Postoje ucenici cija visina je „<< b<< „, prosecna visina „<<endl;
}
else
{
cout <<“ Ne postoje ucenici cija visina je „<< b<< „(prosecna visina) „<<endl;
}
system(„PAUSE“);
return EXIT_SUCCESS;
}

 

Pokazivači

Svaki podatak u računarskom sistemu ima svoju memorijsku lokaciju. C++ omogučava preko promenljivih određenog tipa pristup podacima, pri čemu nije neophodno da se vodi računa o memorijskoj lokaciji gdegde se podatak nalazi.

Pokazivači su specijalni tipovi podataka koji omogućavaju rad sa memorijskim lokacijama. C++ definiše pokazivače tako što posle tipa pokazivača, ispred naziva stavlja * ( int *pokazivač). Ako želimo da saznamo koja je adresa definisanog pokazivača ispred naziva pokazivača se stavlja & (pr. &pokazivac).

Pr:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a = 5;
/* pokayivac ka podatku koji je po tip intedjer*/
int *b;
//b je adresa promenljive a („b pokayuje ka a“)
b = &a;
/*
double *k;
k = &a; //GRESKA: pogresen tip na pokazhuvac (double)
*/
cout << a << endl; //stampa ‘5’ (vrednosta promenljive a)
cout << b << endl; //stampa ‘0x27ff44’ (adresa memorijske lokacije a)
system(„PAUSE“);
return EXIT_SUCCESS;
}

pokazivac

Veoma često, kada se kreiraju pokazivači, potrebno je znati koja je vrednost promenljive ka kojoj pokazuje pokazivač. Sa znakom * pristupamo podatku koji se nalazi na odredjenoj memorijskoj lokaciji. Važno je da se zna da pristupom sa znakom * može vrednost memorijske lokacije da se promeni.

Pr.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a = 5; //promenliva ‘a’ ima vrednost 5
int *p; //pokazhuvac ka podatkom od tipa int

p = &a; //p ja adresa a („p pokazuje ka a“)

cout << a << endl; //stampa ‘5’
cout << *p << endl; //stampa ‘5’

*p = 3; //promena vrednosti

cout << p << endl; //stampa adresu
cout << *p << endl; //stampa ‘3’ (vrednost)
cout << a << endl; //stampa ‘3’
system(„PAUSE“);
return EXIT_SUCCESS;
}

pok2

Jedan pokazivač može se koristiti više puta pri čemu može  da pokazuje i ka različitim promenljivima i memorijskim lokacijama.

Veličina pokazivača zavisi od arhitekturu računarskog sistema, i operativnog sistema, 32 bitni računarski sistem koristi 32 bitne memorijske adrese, veličina pokazivača je 4 bajta.

Pr.

#include <iostream>
using namespace std;

struct typeX
{
int t1, t2, t3, t4;
double t5, t6, t7, t8;
};

int main()
{
int a = 5, b = 2;
double c = 3.8;
char d = ‘Z’;
typeX e;

int *pa = &a, *pb = &b;
double *pc = &c;
char *pd = &d;
typeX *pe = &e;

cout << sizeof(pa) << endl; //stampa ‘4’
cout << sizeof(pb) << endl; //stampa ‘4’
cout << sizeof(pc) << endl; //stampa ‘4’
cout << sizeof(pd) << endl; //stampa ‘4’
cout << sizeof(pe) << endl; //stampa ‘4’

system(„PAUSE“);
return EXIT_SUCCESS;
}

pok3

Niz i pokazivači

 

Dropbox

Рачунари и програмирање

Дропбокс – мој фаворит.
Дропбокс је мрежни сервис за синхронизацију датотека (фајлова) између више уређаја (истог корисника!): кућни рачунар, рачунар на послу, таблет, паметни телефон…
То је складиште на мрежи у које се пакују фајлови којима корисник може приступити са било ког места: или преко претраживача (фајерфокс, хром…) или преко инсталираног програма, који сам обавља синхронизацију! Подршка је одлична за све системе: линукс, виндовс, андроид…  Бесплатан је и нуди 2GB простора. Тај простор се може повећати до 5GB, позивањем пријатеља да користе дропбокс. Уз доплату од 9,99$ месечно добија се 1ТB!

View original post 680 more words

Primeri zadataka koji koriste cin i cout

Računari i programiranje

Pr1.

Napravi program koji unosi i izdaje brojeve?

Rešenje:
#include <iostream>
usingnamespacestd;
intmain()
{
inta, b;
cout << "Unesi dva broja: ";
cin >> a;
cin >> b;
cout << "a = "<< a << endl;
cout << "b = "<< b << endl;
intc, d;
cout << "unesi jos dva broja: ";
cin >> c >> d;
cout << "c = "<< c << endl;
cout << "d = "<< d << endl;
doublereal;
cout << "Unesi jedan decimalni broj: ";
cin >> real;
cout << "real = "<< real;
return0;
}
Pr2.
Napravi program koji izračunava srednju vrednost četiri broja i ispiši rezultat u sledećem obliku:
Unesi cetiri realna broja:
Srednja vrijednost brojeva …., …., …. i …. je ……?

 Rešenje:

#include<iostream>

using namespace std;

int main()

{

    float a,b,c,d,srvr;

    cout<<„Unesi…

View original post 84 more words

Učeniški projekti

Projekat 1. SRTONOGA

slika

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r=30;
// crtam oko
for (x=75;x<80;x=x+1)
{
circle(x,210,10);
}
for (x=60;x<65;x=x+1)
{
circle(x,220,10);
}
line(60,240,80,240);
//crtam glava

circle(75, 220, 40);

// crtam trup
for (x=150;x<600;x=x+2*r)
{
for (r=5;r<40;r=r+5)
{

circle(x, 240,r+5);
}
}
// crtam antene
line (70, 180,40,120);
line (85, 180,120,120);
// crtam nozice
for (x=160; x<600;x=x+2*r)
{
line(x, 280,x+r, 280+5);
line(x, 280, x-r,280+15);
}
getch();
return EXIT_SUCCESS;
}

Projekat 2.  KAMIONČE

Kamionceslika

 

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;
int main()
{
//Pode[avanja grafi;kih parametara
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,“ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
rectangle(50,240,150,300);
rectangle(150,300,380,150);
rectangle(380,240,480,300);
moveto(150,240);
lineto(400,240);
circle(100,330,30);
circle(430,330,30);
moveto(50,240);
lineto(150,150);
line(150,195,100,195);
system(„PAUSE“);
return EXIT_SUCCESS;
}

Animacija

Animacija se može napraviti veoma jednostavno. Dovoljno je objekat koji je postavljen, pre ponovnog pozicioniranja obrisati.

Pr1. Napravite program koji crta pravougaonik od jedne do druge pozicije, pri čemu se y koordinata objekta ne menja?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;
for (x=50;x<600;x=x+1)
{
cleardevice();
rectangle(x, y,x+60,y+60);
}
getch();
return EXIT_SUCCESS;
}

Pr2. Napravite program koji omogućava kretanje kruga po različitim putanjama?

Rešenje:

a)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (y=10;y<400;y=y+30)
{
for (x=10;x<600;x=x+1)
{
cleardevice();
circle(x, y,20);
}
}
getch();
return EXIT_SUCCESS;
}

slika

Krug se kreće sleva prema desno kroz celog grahičkog ekrana.

b)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (x=10;x<600;x=x+30)
{
for (y=10;y<400;y=y+1)
{
cleardevice();
circle(x, y,x+10);
}
}
getch();
return EXIT_SUCCESS;
}

c)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (x=10;x<600;x=x+30)
cleardevice();
{

for (y=10;y<400;y=y+1)
{

circle(x, y,x);
}
}
getch();
return EXIT_SUCCESS;

d)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r;

for (x=30;x<610;x=x+60)
{
for (r=5;r<31;r=r+5)
{

delay(100);
// cleardevice();
circle(x, 24,r);
}

}
getch();
return EXIT_SUCCESS;
}

Krug koji menja poluprečnik,  kreće se sleva prema desno, pri čemu y koordinata je fiksna, menja se samo x; Evo kako izgleda slika kada ne bi brisali objekte

slika

Pr3.

a)  Animacija koja od donje pozicije ekrana kreće krug koji nakon dolaska do određenu poziciju menja poluprečnik?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r;

for (x=465;x>100;x=x-1)
{
cleardevice();
circle(320, x,10);
}
for (r=10;r<91;r=r+1)
{

delay(100);
cleardevice();
circle(320, x,r);
}

getch();
return EXIT_SUCCESS;
}

Kada ne bi brisali predhodno nacrtani objekat dobili bi sliku slika

Pr4.   Napravite animaciju koja se dešava korišćenjem tastera a-levo, f -desno, c-gore, v-dole

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x=290;
int y=220;
char odgovor=’d’;

while (odgovor!=’k’)
{
rectangle(x,y,x+60,y+5);
odgovor=getch();
if (odgovor==’a’)
{
x=x-5;
}
if (odgovor==’f’)
{
x=x+5;
}

if (odgovor==’v’)
{
y=y-5;
}
if (odgovor==’c’)
{
y=y+5;
}
//cleardevice();
}
closegraph();
return EXIT_SUCCESS;
}

Ukoliko se izbriše komanda za brisanje predhodnog objekta dobija se slika slika

ili ako početni objekat je krug, dobija se slika slika

 Pr5. Napravite program koji pomoću miša pomera objekat na grafičkom ekrenu?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
while (!kbhit())
{
rectangle(mousex(), mousey(), mousex()+50, mousey()+50);
}
closegraph();
return EXIT_SUCCESS;
}

slika

Napomena: Naredba kbhit() ispituje dali je neki taster tastature pritisnut. Znaši naredbom while(!kbhit()) objekat se pomera sve dok se ne pritisne bilo koji taster na tastaturi.