1152 - Verificare Ordonat Div Imp

Cerința

Se dă un vector cu n elemente numere naturale. Folosind metoda Divide et Impera să se verifice dacă are elementele ordonate crescător.

Date de intrare

Programul citește de la tastatură numărul n, apoi n numere naturale, reprezentând elementele vectorului.

Date de iesire

Programul afișează pe ecran mesajul DA, dacă vectorul are elementele ordonate crescător, sau NU, în caz contrar.

Restricții si precizări

• 1 ≤ n ≤ 500
• fiecare element al vectorului va avea cel mult patru cifre

Exemplu

Date de intrare

7

4 5 7 9 9 10 12

Date de ieșire

DA

Rezolvare

<syntaxhighlight lang="python"> def ordonat(a, st, dr):

   if st == dr:
       return 1
   else:
       mij = (st + dr) // 2
       a1 = ordonat(a, st, mij)
       a2 = ordonat(a, mij + 1, dr)
       if a1 == a2 and a[mij] <= a[mij + 1]:
           return 1
       else:
           return 0

n = int(input()) a = [0] + list(map(int, input().split()))

if ordonat(a, 1, n):

   print("DA")

else:

   print("NU")

</syntaxhighlight>