👤
SAHARRAZE
a fost răspuns

De ce nu iau 100p la pb aceasta?
Cerinţa
Se dă un şir cu n elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă în şir există elemente impare.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale şirului, separate prin spaţii.

Date de ieşire
Programul afișează pe ecran mesajul DA, dacă şirul conţine elemente impare, respectiv NU în caz contrar.

Restricţii şi precizări
1 ≤ n ≤ 100
elementele şirului vor fi mai mici decât 10000

#include


using namespace std;

int x[1001];

int main()
{
int n, i, st, dr, mij, ok ;
cin>>n;
for(i=1; i<=n; i++)
cin>>x[i];
st=1; dr=n; ok=0;
while(st<=dr&& ok==0){
mij=(st+dr)/2;
if(x[mij]%2==1)
{
ok++;
}
if(x[mij-1-mij/2]%2==1)
ok++;
if(x[mij+1+mij/2]%2==1){
ok++;
}
if(ok==0) {
st=st+1;
dr=dr-1;
}
}

if(ok==0)
cout<<"NU";
else cout<<"DA";


return 0;
}

Răspuns :

Nu este corect deoarece mereu testezi doar primul element, ultimul element si mijlocul. Incearca sa urmaresti codul, instructiune cu instructiune, pentru un exemplu.

Iti prezint eu doua variante de rezolvare :

Varianta 1):

 #include <iostream>
using namespace std;

int v[100];

bool divide(int v[], int n) {
  if (n == 1)
    return *v % 2 == 1;
  else
    return divide(v, n / 2) || divide(v + n / 2, n / 2 + n % 2);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
      cin >> v[i];
    if (divide(v, n))
      cout << "DA";
    else
      cout << "NU";
    return 0;
}


Varianta  2) :

# include <iostream>
using namespace std;

int v[101];

bool divide(int v[], int st, int dr) {
  if(st == dr) {
    if(v[st] % 2 == 0)
      return false;
    else
      return true;
  }
  else {
    int mij = (st + dr)/2;
    int i = divide(v, st, mij);
    int j = divide(v, mij+1, dr);
    if( i || j )
      return true;
    else
      return false;

 }
}

int main() {
  int n, ok;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  if(divide(v, 1, n))
    cout << "DA";
  else
    cout << "NU";
     return 0;
}
 


Vă mulțumim că ați ales să vizitați site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți alte întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Vă așteptăm cu drag să reveniți și nu uitați să ne salvați în lista de favorite!


Ze Teaching: Alte intrebari