269
Cerința
Se consideră un șir cu n
elemente, numere naturale. Folosind metoda Divide et Impera, determinați câte elemente impare sunt în acest șir.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi cele n
elemente ale șirului.
Date de ieșire
Programul va afișa pe ecran numărul C
, reprezentând valoarea cerută.
Restricții și precizări
1 ≤ n ≤ 1000
- elementele șirului vor fi mai mici decât
1.000.000
- se recomandă folosirea metodei Divide et Impera
Exemplu
Intrare
64 1 8 4 3 5
Ieșire
3
#include <bits/stdc++.h> using namespace std; int cnt_impare(int a[], int st, int dr){ if(st == dr) return a[st] % 2 == 1; else{ int mij = (st + dr) / 2; return cnt_impare(a, st, mij) + cnt_impare(a, mij + 1, dr); } } int main() { int n, a[1001]; cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; cout << cnt_impare(a, 1, n); return 0; }
Comentarii