Un vector arata cam asa:
Acesta este un vector cu numarul maxim de spatii in memorie egal cu 10. In prima faza, aceste spatii sunt goale. Trebuie sa le atribuim numere. El se va numi vectorul v (putem sa-l numim si altfel, bineinteles), iar spatiile din acesta sunt numerotate de la 0 la 9. Deci, pentru un vector cu n spatii, ele vor fi numerotate de la 0 la n-1.
Iata vectorul cu 10 spatii, atribuite fiecarui numar, ales aleator.
Iata vectorul cu 10 spatii, atribuite fiecarui numar, ales aleator.
Acest vector are de exemplu: v [0]=5, v [1] = 11, s.a.m.d. De fapt, vectorii sunt asemanatori unei functii, cu legea de corespondenta definita de utilizator pentru fiecare valoare a lui f: f(0)=5, f(1)=11, etc. In C++, vectorii se declara astfel: tip <nume vector> [valoarea maxima de spatii in memorie]; Exemplu:
int vector [25]; - am declarat un vector cu maxim 25 de spatii in memorie, de tip intreg (int).
Pasul 2 dupa declarare este citirea fiecarei valori ale fiecarui spatiu, adica acei v [i]. Pentru asta, vom avea nevoie de o variabila i, care sa memoreze numarul spatiului, ce va porni evident de la 0. Si vom mai citi de la tastatura o variabila n, care reprezinta numarul actual de spatii dorite de utilizator. (Nota! Vectorul poate avea si max. 100 de spatii libere, dar utilizatorul nu poate introduce un n > 100, deoarece citirea se va opri!).
In acest program vom citi si afisa un vector. Pentru a citi, avem nevoie de instructiunea for, care sa ceara de la tastatura, pentru fiecare i de la 0 la n-1, cate un numar care ii va fi atribuit lui v[i]. Apoi, parcurgem vectorul asemanator, dar de aceasta data afisam fiecare v [i].
//Citirea unui vector
#include <iostream.h>
#include <math.h>
void main ()
{
int v [20], n, i;
cout<<”Introduceti numarul de spatii: “;
cin>>n;
for (i=0; i<n; i++) //de la fiecare i de la primul spatiu (0) la ultimul (n-1)
cin>>v [i]; //citim fiecare v [i]
for (i=0; i<n; i++) //parcurgem din nou vectorul
cout<<v [i]<<” “; //si de aceasta data afisam v [i]
int vector [25]; - am declarat un vector cu maxim 25 de spatii in memorie, de tip intreg (int).
Pasul 2 dupa declarare este citirea fiecarei valori ale fiecarui spatiu, adica acei v [i]. Pentru asta, vom avea nevoie de o variabila i, care sa memoreze numarul spatiului, ce va porni evident de la 0. Si vom mai citi de la tastatura o variabila n, care reprezinta numarul actual de spatii dorite de utilizator. (Nota! Vectorul poate avea si max. 100 de spatii libere, dar utilizatorul nu poate introduce un n > 100, deoarece citirea se va opri!).
In acest program vom citi si afisa un vector. Pentru a citi, avem nevoie de instructiunea for, care sa ceara de la tastatura, pentru fiecare i de la 0 la n-1, cate un numar care ii va fi atribuit lui v[i]. Apoi, parcurgem vectorul asemanator, dar de aceasta data afisam fiecare v [i].
//Citirea unui vector
#include <iostream.h>
#include <math.h>
void main ()
{
int v [20], n, i;
cout<<”Introduceti numarul de spatii: “;
cin>>n;
for (i=0; i<n; i++) //de la fiecare i de la primul spatiu (0) la ultimul (n-1)
cin>>v [i]; //citim fiecare v [i]
for (i=0; i<n; i++) //parcurgem din nou vectorul
cout<<v [i]<<” “; //si de aceasta data afisam v [i]
Tutorial - Citirea si afisarea unui vector
c_-_tutorial_8_-_citirea_si_afisarea_unui_vector_-_electrokits.ro.mp4 | |
File Size: | 3418 kb |
File Type: | mp4 |
Sau pe Youtube chiar aici: http://www.youtube.com/watch?v=nfG4OGkJp8Y
Sortarea prin inserare
Este cea mai eficienta metoda de a ordona elementele unui vector crescator sau descrescator. Acest lucru ne ajuta la o aplicatie care suna cam asa: Se citesc de la tastatura n numere reale. Sa se afiseze aceste numere, ordonate crescator sau descrescator, la cererea utilizatorului. Problema consta in memorarea numerelor citite de la tastatura intr-un vector v. Sa zicem ca am memorat aceste numere in vectorul v[10]:
Dupa cum se vede, aceste numere sunt introduse aleator, si anume nu sunt ordonate. Aceasta “strategie” a ordonarii prin interschimbare consta in parcurgerea acelui vector, si schimbarea pozitiei numarului cu cel precedent, in cazul in care este mai mare sau mai mic decat cel la care am ajuns (depinzand de tipul de ordonare). Procesul se va repeta “cat timp” numerele sunt in ordine perfecta. Pentru a intelege mai bine acest proces, va voi da un exemplu folosind vectorul de mai sus.
Deci, incepem sa parcurgem vectorul, in acest caz pentru o ordonare crescatoare.
- Mai intai citim v[0], iar apoi, v[0+1], adica v[1].
- Comparam cele doua valori, si observam ca v[0]>v[1], deci… interschimbam. Cum facem acest lucru? Schimb de variabile. Folosim o auxiliara, aux, care va retine valoarea lui v[0] si o va transmite lui v[1].
- Apoi, citim v[1+1]=v[2].v [1] va fi egal cu 10, pentru ca am schimbat . Observam ca v[2] este deja mai mare decat v[1], deci… il lasam in pace. Si tot asa, pana la v[n]=v[10] in cazul nostru, cand facem ultima schimbare.
- Procesul se repeta pana cand vectorul va fi complet ordonat. Cum scriem in C++? Pai, iata cum facem: Citim vectorul de la tastatura, prin metoda obisnuita. Apoi, il parcurgem, tot prin metoda uzuala. Folosim o variabila j, care va desemna de fapt urmatoarea valoare a lui v[i], deci v[j]=v[i+1].
- In cazul asta putem compara v[i] cu v[j]. Daca v[i]>v[j], schimbam, adica aux=v[i], v[i]=v[j], iar v[j]=aux. Codul arata cam asa:
//Ordonare
#include <iostream.h>
void main ()
{
double long n, i, j, a, aux, d; //am declarat variabilele folosite: n pentru nr actual de spatii in vector, i pentru pozitia fiecarei valori ale vectorului, j pentru a afla pozitia “urmatoare” a lui v[i], a este o variabila care cere utilizatorului tipul de ordonare, aux este auxiliara care ajuta la interschimbare, iar d pentru a repeta programul, la cererea utilizatorului.
int v [1000];
do {
cout<<”Ordonarea numerelor introduse “<<endl;
cout<<”Alegeti tipul de ordonare: “<<endl;
cout<<”1.ORDONARE CRESCĂTOARE”<<endl;
cout<<”2.ORDONARE DESCRESCĂTOARE”<<endl;
cin>>a; //cerem de la tastatura tipul de ordonare
if (a==1) //daca am ales ordonarea crescatoare, atunci …>>
{
cout<<”Ati ales ordonarea crescătoare.”<<endl;
cout<<”Câte numere introduceti? (MAX=1000) “;
cin>>n; //aici citim numarul de spatii disponibile in vector
if (n>1000) //acesta nu trebuie sa fie mai mare de 1000
cout<<”Reporniti programul si introduceti un număr corespunzător.”; //in acest caz cerem utilizatorului sa introduca un numar mai mic de 1000.
else
{
cout<<”Introduceti numerele: “; //in cazul in care a introdus un numar corect
for (i=0; i<n; i++)
cin>>v [i]; //citim vectorul
for (i=0; i<n; i++) //incepem sa-l parcurgem
{
for (j=i+1; j<n; j++) //iar pentru j=i+1, adica valoarea urmatoarei pozitii
if (v [i]>v [j]) //comparam pozitia initiala cu cea urmatoare. Daca este mai mare, atunci schimbam pozitiile valorilor
{
aux=v [i];
v [i]=v [j];
v [j]=aux;
}
}
cout<<”Ordinea crescătoare a numerelor introduse este: “;
for (i=0; i<n; i++)
cout<<v [i]<<”; “; //si in final afisam ordinea corecta, in acest caz crescatoare, a numerelor din vector, cu “;” intre ele
}
}
else if (a==2) //daca am ales ordonarea descrescatoare, atunci…>>
{
cout<<”Ati ales ordonarea descrescătoare.”<<endl;
cout<<”Câte numere introduceti? (MAX=1000) “;
cin>>n; //la fel, citim numarul actual de spatii in vector
if (n>1000)
cout<<”Reporniti programul si introduceti un număr corespunzător.”; //cerem repornirea in cazul unui numar >1000
else
{
cout<<”Introduceti numerele: “;
for (i=0; i<n; i++)
cin>>v [i]; //citim fiecare numar de la tastatura si le memoram in vector
for (i=0; i<n; i++) //apoi il parcurgem
{
for (j=i+1; j<n; j++) //si pentru urmatoarea valoare din urmatoarea pozitie,
if (v [i]<v [j]) //comparam valoarea initiala cu cea de pe urmatoarea pozitie, dar in cazul ordonarii descrescatoare, v[i] trebuie sa fie mai mare decat v[i+1].
{
aux=v [i];
v [i]=v [j];
v [j]=aux;
}
}
cout<<”Ordinea descrescătoare a numerelor introduse este: “;
for (i=0; i<n; i++)
cout<<v [i]<<”; “; //afisam fiecare numar din vector, in ordinea corecta
}
}
cout<<endl;
cout<<”Doriti să reporniti programul? (DA=1 / NU=0) “;
cin>>d;
} while (d==1); //aici cerem utilizatorului permisiunea de a repeta programul, dupa cum v-am explicat in posturile anterioare
}
#include <iostream.h>
void main ()
{
double long n, i, j, a, aux, d; //am declarat variabilele folosite: n pentru nr actual de spatii in vector, i pentru pozitia fiecarei valori ale vectorului, j pentru a afla pozitia “urmatoare” a lui v[i], a este o variabila care cere utilizatorului tipul de ordonare, aux este auxiliara care ajuta la interschimbare, iar d pentru a repeta programul, la cererea utilizatorului.
int v [1000];
do {
cout<<”Ordonarea numerelor introduse “<<endl;
cout<<”Alegeti tipul de ordonare: “<<endl;
cout<<”1.ORDONARE CRESCĂTOARE”<<endl;
cout<<”2.ORDONARE DESCRESCĂTOARE”<<endl;
cin>>a; //cerem de la tastatura tipul de ordonare
if (a==1) //daca am ales ordonarea crescatoare, atunci …>>
{
cout<<”Ati ales ordonarea crescătoare.”<<endl;
cout<<”Câte numere introduceti? (MAX=1000) “;
cin>>n; //aici citim numarul de spatii disponibile in vector
if (n>1000) //acesta nu trebuie sa fie mai mare de 1000
cout<<”Reporniti programul si introduceti un număr corespunzător.”; //in acest caz cerem utilizatorului sa introduca un numar mai mic de 1000.
else
{
cout<<”Introduceti numerele: “; //in cazul in care a introdus un numar corect
for (i=0; i<n; i++)
cin>>v [i]; //citim vectorul
for (i=0; i<n; i++) //incepem sa-l parcurgem
{
for (j=i+1; j<n; j++) //iar pentru j=i+1, adica valoarea urmatoarei pozitii
if (v [i]>v [j]) //comparam pozitia initiala cu cea urmatoare. Daca este mai mare, atunci schimbam pozitiile valorilor
{
aux=v [i];
v [i]=v [j];
v [j]=aux;
}
}
cout<<”Ordinea crescătoare a numerelor introduse este: “;
for (i=0; i<n; i++)
cout<<v [i]<<”; “; //si in final afisam ordinea corecta, in acest caz crescatoare, a numerelor din vector, cu “;” intre ele
}
}
else if (a==2) //daca am ales ordonarea descrescatoare, atunci…>>
{
cout<<”Ati ales ordonarea descrescătoare.”<<endl;
cout<<”Câte numere introduceti? (MAX=1000) “;
cin>>n; //la fel, citim numarul actual de spatii in vector
if (n>1000)
cout<<”Reporniti programul si introduceti un număr corespunzător.”; //cerem repornirea in cazul unui numar >1000
else
{
cout<<”Introduceti numerele: “;
for (i=0; i<n; i++)
cin>>v [i]; //citim fiecare numar de la tastatura si le memoram in vector
for (i=0; i<n; i++) //apoi il parcurgem
{
for (j=i+1; j<n; j++) //si pentru urmatoarea valoare din urmatoarea pozitie,
if (v [i]<v [j]) //comparam valoarea initiala cu cea de pe urmatoarea pozitie, dar in cazul ordonarii descrescatoare, v[i] trebuie sa fie mai mare decat v[i+1].
{
aux=v [i];
v [i]=v [j];
v [j]=aux;
}
}
cout<<”Ordinea descrescătoare a numerelor introduse este: “;
for (i=0; i<n; i++)
cout<<v [i]<<”; “; //afisam fiecare numar din vector, in ordinea corecta
}
}
cout<<endl;
cout<<”Doriti să reporniti programul? (DA=1 / NU=0) “;
cin>>d;
} while (d==1); //aici cerem utilizatorului permisiunea de a repeta programul, dupa cum v-am explicat in posturile anterioare
}
Tutorial - Interschimbarea variabilelor
c_-_tutorialul_1_-_interschimbarea_variabilelor.mp4 | |
File Size: | 1404 kb |
File Type: | mp4 |
Sau pe Youtube chiar aici: http://www.youtube.com/watch?v=FM9l8i13p18
Cautarea Binara
Va voi explica cum se face cautarea intr-un vector. Multi dintre voi probabil vor crede ca e floare la ureche. Dar nu uitati! Scopul unui algoritm este sa fie cat mai eficient posibil, adica sa execute cat mai putine repetitii. Nu are rost sa parcurgem tot vectorul, mai ales daca acesta are spre exemplu 1000 de spatii, si sa vedem daca numarul cerut a fost gasit. Ideea este de a porni de la jumatate! Atentie! Aceasta metoda functioneaza doar pentru un vector deja ordonat (crescator sau descrescator).
1.Mai intai verificam daca numarul cautat nu este chiar la jumatatea vectorului, iar daca nu, comparam valorile vecinilor lui.
2.Daca x-ul cautat este mai mare decat valoarea de la mijloc, atunci… continuam cautarea doar spre dreapta.
3.Daca x-ul cautat este mai mic decat valoarea de la mijloc, atunci… pornim spre stanga.
Cum scriem in C++? Foarte usor. Folosim niste variabile auxiliare, si anume lst (limita stanga), initiala 0, ldr (limita dreapta, initiala n-1, si una mij (mijlocul vectorului), care va fi egala cu (lst+ldr)/2.
Incepem cautarea: dupa ce am citit vectorul, il parcurgem, si vedem daca este egal cu mijlocul, adica verificam conditia x=v[mij]. Altfel, daca x este mai mic decat v[mij], pornim spre stanga, adica ldr=mij-1. Procesul se repeta, pana x este gasit. Altfel, daca x este mai mare decat v[mij], pornim cautarea spre dreapta, adica lst=mij+1. In schimb mai avem nevoie de o variabila care ne indica daca elementul x a fost gasit, si anume… gasit, initial 0
#include <iostream.h>
void main ()
{
int v[10], x, gasit, i, lst, ldr, mij, n; //v este vectorul, x este elementul cautat, gasit este variabila care ne va indica daca x este gasit, i=pozitia viecarui v[i], lst=limita stanga, ldr=limita dreapta, mij=pozitia de mijloc, n=lungimea actuala a vectorului
cout<<”Cate numere introduceti?”;
cin>>n; //citim lungimea vectorului
cout<<”Introduceti numerele din vector: “;
for (i=0; i<n; i++)
cin>>v[i];//citim elementele vectorului
gasit=0;//gasit este initial 0, adica “fals”
lst=0; //limita stanga este pe pozitia 0
ldr=n-1;//limita dreapta este pozitia n-1
cout<<”Introduceti elementul x cautat: “;
cin>>x; //citim elementul cautat
for (i=0; i<n && !gasit && lst<=ldr; i++) //parcurgem vectorul, conditia fiind ca variabila “gasit” sa nu devina 1, deoarece daca am gasit elementul, repetitia trebuie a se opreasca. Iar la sfarsit, limita stanga trebuie sa fie cel putin egala cu cea dreapta, altfel repetitia va fi la nesfarsit.
{
mij=(lst+ldr)/2;
{
if (x==v[mij]) gasit=1; //daca x este egal cu nr. din pozitia mij, atunci… l-am gasit pe x.
else if (x<v[mij]) ldr=mij-1; //daca x este mai mic decat nr. din pozitia mij, atunci parcurgem vectorul doar inspre stanga, deci limita dreapta va deveni mij-1, pentru ca mij a fost deja testat
else lst=mij+1; //daca x este mai mare decat nr. din pozitia mij, parcurgem vectorul inspre dreapta, adica limita stanga va deveni mij+1
}
}
if (!gasit) cout<<x<<”nu este in vector.”;
else cout<<x<<” este pe pozitia “<<mij<<”.”; //la sfarsit afisam rezultatul cautarii, iar daca x a fost gasit, putem afisa si pozitia acestuia, adica mij.
}
1.Mai intai verificam daca numarul cautat nu este chiar la jumatatea vectorului, iar daca nu, comparam valorile vecinilor lui.
2.Daca x-ul cautat este mai mare decat valoarea de la mijloc, atunci… continuam cautarea doar spre dreapta.
3.Daca x-ul cautat este mai mic decat valoarea de la mijloc, atunci… pornim spre stanga.
Cum scriem in C++? Foarte usor. Folosim niste variabile auxiliare, si anume lst (limita stanga), initiala 0, ldr (limita dreapta, initiala n-1, si una mij (mijlocul vectorului), care va fi egala cu (lst+ldr)/2.
Incepem cautarea: dupa ce am citit vectorul, il parcurgem, si vedem daca este egal cu mijlocul, adica verificam conditia x=v[mij]. Altfel, daca x este mai mic decat v[mij], pornim spre stanga, adica ldr=mij-1. Procesul se repeta, pana x este gasit. Altfel, daca x este mai mare decat v[mij], pornim cautarea spre dreapta, adica lst=mij+1. In schimb mai avem nevoie de o variabila care ne indica daca elementul x a fost gasit, si anume… gasit, initial 0
#include <iostream.h>
void main ()
{
int v[10], x, gasit, i, lst, ldr, mij, n; //v este vectorul, x este elementul cautat, gasit este variabila care ne va indica daca x este gasit, i=pozitia viecarui v[i], lst=limita stanga, ldr=limita dreapta, mij=pozitia de mijloc, n=lungimea actuala a vectorului
cout<<”Cate numere introduceti?”;
cin>>n; //citim lungimea vectorului
cout<<”Introduceti numerele din vector: “;
for (i=0; i<n; i++)
cin>>v[i];//citim elementele vectorului
gasit=0;//gasit este initial 0, adica “fals”
lst=0; //limita stanga este pe pozitia 0
ldr=n-1;//limita dreapta este pozitia n-1
cout<<”Introduceti elementul x cautat: “;
cin>>x; //citim elementul cautat
for (i=0; i<n && !gasit && lst<=ldr; i++) //parcurgem vectorul, conditia fiind ca variabila “gasit” sa nu devina 1, deoarece daca am gasit elementul, repetitia trebuie a se opreasca. Iar la sfarsit, limita stanga trebuie sa fie cel putin egala cu cea dreapta, altfel repetitia va fi la nesfarsit.
{
mij=(lst+ldr)/2;
{
if (x==v[mij]) gasit=1; //daca x este egal cu nr. din pozitia mij, atunci… l-am gasit pe x.
else if (x<v[mij]) ldr=mij-1; //daca x este mai mic decat nr. din pozitia mij, atunci parcurgem vectorul doar inspre stanga, deci limita dreapta va deveni mij-1, pentru ca mij a fost deja testat
else lst=mij+1; //daca x este mai mare decat nr. din pozitia mij, parcurgem vectorul inspre dreapta, adica limita stanga va deveni mij+1
}
}
if (!gasit) cout<<x<<”nu este in vector.”;
else cout<<x<<” este pe pozitia “<<mij<<”.”; //la sfarsit afisam rezultatul cautarii, iar daca x a fost gasit, putem afisa si pozitia acestuia, adica mij.
}