online: 9; azi: 280; total: 52286 Manual clasa a xi a - Tehnici de programare - Divide et impera

Probleme Rezolvate



Sa se rearanjeze elementele unui vector astfel incat in vector sa se gaseasca mai intai numerele impare si apoi numerele pare
Sa se deseneze figura geometrica obtinuta astfel
Sa se calculeze radicalul de ordinul 3 din numarul a
Sa se determine numarul de apariii ale unei valori x intr
Sa se calculeze valoarea unui polinom p
Sa se determine simultan valoarea minima si valoarea maxima
Sa se calculeze simultan produsul si suma a n numere memorate intr
Ntr un fisier text sunt scrise urmatoarele informatii
Ntr o matrice patrata cu dimensiunea n sa se interschimbe diagonala principala cu diagonala secundara
Sa se calculeze n
Desenai curba dragonului
Sa se calculeze c
Sa se calculeze radicalul de ordinul 2 din numarul a
Desenai praful lui cantor
Sa se verifice daca un vector conine numai numere pozitive sau numai numere negative
Ntr o matrice patrata cu dimensiunea n sa se interschimbe linia p cu coloana q
Sa se numere elementele pare dintr
Sa se deseneze covorul lui sierpinski
Desenai curba lui koch
Sa se calculeze partea intreaga a radicalului de ordinul 3 din numarul a fara a folosi functia matematica de sistem
Sa se calculeze suma 1
Sa se caute intr-un sir de numere intregi in care mai intai se gasesc num
Ntr o matrice cu n linii si m coloane sa se interschimbe coloana p cu coloana q

Manual clasa a Xi a

Tehnici de programare

Divide et impera
Să se verifice dacă un vector conţine numai numere pozitive sau numai numere negative.
Pentru a verifica dacă un vector conține numai numere pozitive sau numai numere negative, putem folosi algoritmul Divide et Impera . Algoritmul constă în împărțirea problemei în subprobleme mai mici, calcularea soluției pentru fiecare subproblemă și combinația soluțiilor pentru a obține soluția finală.
În cazul de față, putem împărți vectorul în două subvectori și verifica dacă fiecare subvector conține numai numere pozitive sau numai numere negative prin apelul recursiv al funcției. Dacă un subvector conține numai numere pozitive și celălalt subvector conține numai numere negative, atunci întregul vector conține numai numere pozitive sau numai numere negative.
Pentru a implementa acest algoritm în C++, putem utiliza o funcție recursivă care primește vectorul, indicele de început și indicele de sfârșit ca parametri și returnează true dacă vectorul conține numai numere pozitive sau numai numere negative, și false în caz contrar.
# include < iostream >
using namespace std ;
bool divideEtImpera ( int v[], int start, int end ) {
if (start == end ) {
return v[start] >= 0 ? true : false ;
} else {
int mid = (start + end ) / 2 ;
bool left = divideEtImpera (v, start, mid );
bool right = divideEtImpera (v, mid + 1 , end );
if (left && right ) {
if ((v[ mid ] >= 0 && v[ mid + 1 ] >= 0 ) || (v[ mid ] < 0 && v[ mid + 1 ] < 0 )) {
return true ;
}
}
return false ;
}
}
int main () {
int v[] = { -1 , -2 , -3 , -4 , -5 }; // Exemplu: vectorul {-1, -2, -3, -4, -5}
int n = sizeof (v) / sizeof (v[ 0 ]);
bool result = divideEtImpera (v, 0 , n - 1 );
if ( result ) {
cout << "Vectorul contine numai numere pozitive sau numai numere negative." << endl ;
} else {
cout << "Vectorul nu contine numai numere pozitive sau numai numere negative." << endl ;
}
return 0 ;
}
În acest exemplu, am verificat dacă vectorul {-1, -2, -3, -4, -5}
conține numai numere pozitive sau numai numere negative și am afișat rezultatul. În funcția divideEtImpera , verificăm dacă subvectorul are o singură valoare, caz în care returnăm true dacă valoarea este pozitivă și false în caz contrar. În caz contrar, împărțim subvectorul în două subvectori și verificăm dacă fiecare subvector conține numai numere pozitive sau numai numere negative prin apelul recursiv al funcției divideEtImpera .