1845 - OrdonareF Rec

Cerinţa

Scrieţi definiția completă a subprogramului recursiv ordonare care are 2 parametri: a, prin care primeşte un tablou unidimensional cu maximum 1000 de numere naturale mai mici decât 1.000.000.000 și n, numărul efectiv de elemente ale tabloului. Subprogramul ordonează crescător elementele tabloului a, fără a returna valori.

Date de intrare

Se va introduce de la tastatură 2 numere naturale care vor fi transmise ca perimetrii

Date de ieșire

Dacă datele de intrare corespund restrictiilor impuse se va afișa mesajul "Datele de intrare corespund restricțiilor" și pe un rând nou se afișează ceea ce se cere. Altfel, dacă datele de intrare nu corespund cerinței se va afișa mesajul: "Datele de intrare nu corespund cerinței".

Restricţii şi precizări

• 0 < n <= 1000
• numele subprogramului cerut este ordonare
• parametrii sunt, în această ordine: a, n
• elementele tabloului a sunt indexate de la zero
• se recomandă realizarea unei soluții recursive

Exemplu

Exemplu 1

Intrare:

Introduceti numarul de elemente

6

Introduceti cele 6 numere separate prin spatiu

63 273 9 83 93 123

Iesire:

Datele de intrare corespund restricțiilor

Tabloul sortat este

[9, 63, 83, 93, 123, 273]

Exemplu 2

Intrare:

Introduceti numarul de elemente

1001

Iesire:

Datele de intrare nu corespund cerinței

Important

Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Rezolvare

<syntaxhighlight lang="python" line="1"> def validate_input(n):

   if n <= 0 or n > 1000:
       print("Datele de intrare nu corespund cerinței")
       exit()

def ordonare(a, n):

   if n <= 1:
       return a
   for i in range(n - 1):
       if a[i] > a[i + 1]:
           a[i], a[i + 1] = a[i + 1], a[i]
   return ordonare(a, n - 1)

def main():

   n = int(input("Introduceti numarul de elemente: "))
   validate_input(n)
   a = list(map(int, input("Introduceti cele " + str(n) + " numere separate prin spatiu: ").split()))
   print("Datele de intrare corespund restricțiilor")
   a_sortat = ordonare(a, n)
   print("Tabloul sortat este:", a_sortat)

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicații

Funcția validate_input(n) primește ca parametru numărul n și verifică dacă acesta respectă restricțiile impuse. Dacă numărul este mai mic sau egal cu 0 sau mai mare decât 1000, atunci se afișează un mesaj corespunzător și se iese din program prin apelarea funcției exit(). Funcția ordonare(a, n) primește ca parametri tabloul a și numărul de elemente n și sortează tabloul folosind algoritmul "Bubble Sort". Dacă numărul de elemente este mai mic sau egal cu 1, atunci se consideră că tabloul este deja sortat și se returnează tabloul. În caz contrar, se parcurge tabloul de la stânga la dreapta și se verifică dacă două elemente consecutive sunt în ordine inversă. Dacă da, atunci se schimbă locurile lor. După aceasta, se apelează funcția recursiv, dar cu un element mai puțin. Funcția main() primește de la utilizator numărul de elemente și tabloul de numere și validează datele introduse. Dacă datele sunt valide, atunci se afișează un mesaj corespunzător și se apelează funcția ordonare() pentru a sorta tabloul.