Question

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;
}

Answer 1

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;
}