1511 - FCautareRec

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

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 <= 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

Exemplu 1

Intrare:

Introduceti numarul de elemente

6

Introduceti elementul 0

9.5

Introduceti elementul 1

16.3

Introduceti elementul 2

28.3

Introduceti elementul 3

49.7

Introduceti elementul 4

52.4

Introduceti elementul 5

73

Introduceti valoarea de cautat

52.4

Iesire:

Datele de intrare corespund restrictiilor

Valoarea a fost gasita la pozitia 4

Exemplu 2

Intrare:

Introduceti numarul de elemente

101

Iesire:

Datele de intrare nu corespund cerintei.

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 validare(n):

   if n > 0 and n <= 100:
       return True
   else:
       return False

def cautare(n, X, v):

   def rec_cautare(i):
       if i == n:
           return -1
       if X[i] == v:
           return i
       return rec_cautare(i + 1)
   return rec_cautare(0)

def main():

   n = int(input("Introduceti numarul de elemente: "))
   if validare(n):
       X = []
       for i in range(n):
           x = float(input(f"Introduceti elementul {i}: "))
           X.append(x)
       v = float(input("Introduceti numarul v: "))
       pozitie = cautare(n, X, v)
       if pozitie != -1:
           print(f"Numarul {v} se afla pe pozitia {pozitie} in lista.")
       else:
           print(f"Numarul {v} nu se afla in lista.")
   else:
       print("Datele de intrare nu corespund cerintei.")

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicații

Codul implementează o funcție numită cautare care primește trei parametrii: n reprezentând numărul de elemente din șirul X de numere reale, X reprezentând șirul propriu-zis și v reprezentând valoarea căutată. Funcția are rolul de a căuta valoarea v în șirul X și de a returna poziția la care a fost găsită aceasta.

Inițial, funcția verifică dacă valoarea lui n respectă restricția impusă de cerință (0 < n <= 100). Dacă nu, se afișează mesajul "Datele de intrare nu corespund cerinței" și funcția se termină. În caz contrar, se afișează mesajul "Datele de intrare corespund restricțiilor".

În continuare, funcția intră în recursivitate. Dacă șirul X este vid (adică nu mai are elemente), funcția returnează valoarea -1, indicând că valoarea v nu a fost găsită în șir. Dacă primul element din șir este egal cu valoarea v, funcția returnează poziția acestuia (această poziție este dată de lungimea șirului inițial n minus lungimea șirului curent len(X)). În caz contrar, se face o apelare recursivă a funcției cautare cu șirul X fără primul element și se adaugă la poziția returnată de apelul recursiv lungimea șirului curent, astfel încât să se obțină poziția corectă în șirul inițial.

În final, funcția este apelată în cadrul funcției main, unde utilizatorul este întâmpinat cu un mesaj de introducere și se citesc de la tastatură datele de intrare. Funcția cautare este apoi apelată cu aceste date și rezultatul este afișat în funcție de valoarea întoarsă.