Rezolvare A.10

Nu parcurgeți acest articol înainte de rezolvarea problemei!

Enunț

Se dă următorul subalgoritm:

1: Subalgoritm cautare(x, n, val):
2:   Dacă n = 1 atunci
3:     returnează (x[1] = val)
4:   altfel
5:     returnează cautare(x, n - 1, val)
6:   SfDacă
7: SfSubalgoritm

Ce instrucțiune sau instrucțiuni trebuie adăugate și unde astfel încât în urma apelului, subalgoritmul cautare(x, n, val) să determine dacă elementul val face sau nu parte din șirul x cu n elemente (n număr natural strict mai mare ca zero)?

A. Linia 5 trebuie modificată în: returnează ((x[n] = val) și cautare(x - 1, n, val))
B. Linia 5 trebuie modificată în: returnează ((x[n] = val) sau cautare(x, n - 1, val))
C. Linia 5 trebuie modificată în: dacă (x[n] = val) atunci returnează true altfel returnează cautare(x, n - 1, val)
D. nu trebuie modificată nici o instrucțiune

Soluție

Răspuns corect: B, C.

Justificare

O formulare recursivă a algoritmului de căutare poate fi: valoarea val apare în tabloul de lungime n dacă și numai dacă apare în ultimul element – v[n] – sau apare în celelalte n-1 elemente.

Variantele B, C sunt corecte. La varianta B se folosește o operație logică, iar la varianta C structura alternativă.

Dacă nu modificăm nimic, rezultatul subprogramului este adevărat dacă și numai dacă primul element al tabloului este egal cu val – greșit.

În cazul modificării de la varianta A, parametrul n nu se modifică, ceea ce duce la recursivitate infinită!