1511 - FCautareRec: Difference between revisions

Revision as of 11:19, 25 March 2023

Cerinţa

Scrieţi definiția completă a unei funcții recursive care are ca parametrii un număr natural n, un șir crescător X de numere reale având n elemente și un număr real v și care returnează poziția pe care apare în șir valoarea v. În cazul în care v nu apare în șir, se va returna valoarea -1. În cazul în care v apare în șir pe mai multe poziții, se va returna una dintre acestea.

Date de intrare

Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

0 < n <= 100 v și elementele lui X sunt numere reale – se va folosi tipul double numele subprogramului cerut este cautare parametrii sunt, în această ordine: n, X, v elementele tabloului X sunt indexate de la zero se recomandă realizarea unei soluții recursive

Exemplu

Dacă n=6, X=(9.5,16.3,28.3,49.7,52.4,73), iar v=52.4, funcția va returna valoarea 4.

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

def cautare(n, X, v):
   # verificare dacă v se află între capetele șirului
   if v < X[0] or v > X[n-1]:
       return -1
   
   # calculăm mijlocul șirului
   mijloc = int((n-1)/2)
   
   # dacă valoarea v se află în mijlocul șirului, returnăm poziția
   if v == X[mijloc]:
       return mijloc
   
   # dacă v este mai mic decât mijlocul, căutăm recursiv în jumătatea stângă a șirului
   elif v < X[mijloc]:
       return cautare(mijloc, X[:mijloc], v)
   
   # dacă v este mai mare decât mijlocul, căutăm recursiv în jumătatea dreaptă a șirului
   else:
       return cautare(n - mijloc - 1, X[mijloc+1:], v) if n-mijloc-1>0 else -1

@@ Line 19: / Line 19: @@
 ==Exemplu==
 Dacă n=6, X=(9.5,16.3,28.3,49.7,52.4,73), iar v=52.4, funcția va returna valoarea 4.
+==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==
   def cautare(n, X, v):
-     # Caz de bază: lista X este goală
+     # verificare dacă v se află între capetele șirului
-     if n == 0:
+     if v < X[0] or v > X[n-1]:
-        return -1
+         return -1
-    # Caz de bază: valoarea v este pe prima poziție din lista X
-    if X[0] == v:
+     # calculăm mijlocul șirului
-         return 0
+     mijloc = int((n-1)/2)
-     # Apel recursiv pentru lista X fără prima valoare
-     poz = cautare(n-1, X[1:], v)
+     # dacă valoarea v se află în mijlocul șirului, returnăm poziția
-     # Dacă valoarea v a fost găsită în lista X fără prima valoare, se va returna poziția respectivă +1
+     if v == X[mijloc]:
-     if poz != -1:
+         return mijloc
-         return poz+1
-     # Dacă valoarea v nu a fost găsită în lista X, se va returna -1
+     # dacă v este mai mic decât mijlocul, căutăm recursiv în jumătatea stângă a șirului
-     return -1
+     elif v < X[mijloc]:
- # Citire date de intrare
+        return cautare(mijloc, X[:mijloc], v)
- n = int(input())
- # Verificare condiții de intrare
+    # dacă v este mai mare decât mijlocul, căutăm recursiv în jumătatea dreaptă a șirului
- if n <= 0 or n > 100:
-    print("Datele de intrare nu corespund restricțiilor impuse.")
- else:
-    X = list(map(float, input().split()))
-    v = float(input())
-    # Apel funcție și afișare rezultat
-    pozitie = cautare(n, X, v)
-     if pozitie == -1:
-        print("Valoarea", v, "nu a fost gasita in lista.")
      else:
-         print("Valoarea", v, "a fost gasita pe pozitia", pozitie)
+         return cautare(n - mijloc - 1, X[mijloc+1:], v) if n-mijloc-1>0 else -1