Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
# include < iostream >
using namespace std ;
int cubeRoot ( int a, int low , int high ) {
if ( low > high ) {
return low - 1 ;
}
int mid = ( low + high ) / 2 ;
if ( mid * mid * mid <= a) {
return cubeRoot (a, mid + 1 , high );
} else {
return cubeRoot (a, low , mid - 1 );
}
}
int main () {
int a;
cout << " Introduceti numarul a pentru care sa se calculeze partea intreaga a radicalului de ordinul 3: " ;
cin >> a;
int cubeRootInt = cubeRoot (a, 0 , a);
cout << "Partea intreaga a radicalului de ordinul 3 al lui " << a << " este: " << cubeRootInt << endl ;
return 0 ;
}
using namespace std ;
int cubeRoot ( int a, int low , int high ) {
if ( low > high ) {
return low - 1 ;
}
int mid = ( low + high ) / 2 ;
if ( mid * mid * mid <= a) {
return cubeRoot (a, mid + 1 , high );
} else {
return cubeRoot (a, low , mid - 1 );
}
}
int main () {
int a;
cout << " Introduceti numarul a pentru care sa se calculeze partea intreaga a radicalului de ordinul 3: " ;
cin >> a;
int cubeRootInt = cubeRoot (a, 0 , a);
cout << "Partea intreaga a radicalului de ordinul 3 al lui " << a << " este: " << cubeRootInt << endl ;
return 0 ;
}
Algoritmul folosește o abordare divide et impera pentru a reduce intervalul de căutare și pentru a găsi partea întreagă a rădăcinii cubice a lui a. În funcția cubeRoot () , se împarte intervalul [0, a] în două sub-intervale, verificând în care sub-interval se află soluția. Dacă mijlocul sub-intervalului ridicat la puterea a treia este mai mic sau egal cu a, se continuă căutarea în sub-intervalul din dreapta. În caz contrar, se continuă căutarea în sub-intervalul din stânga. Acest proces se repetă recursiv până când se găsește partea întreagă a rădăcinii cubice a lui a.
Este important să se acorde atenție condiției de oprire a recursivității, pentru a evita bucle infinite și a asigura că algoritmul se termină într-un timp rezonabil.