Il seguente frammento di programma è stato scritto per effettuare la ricerca di un elemento identificato dalla variabile chiave in array ordinato (in ordine crescente) vett con n componenti intere.
Se l’elemento chiave è presente nell’array allora il programma deve fornire nella variabile posizione il valore di un indice dell’array il cui valore è pari al valore di chiave; se l’elemento chiave non è presente allora il programma deve ritornare il valore –1.
Il frammento di programma seguente non è sempre corretto; tuttavia è possibile ottenere un programma che risponde alle specifiche modificando una sola istruzione.
Indicate il numero di istruzione e come deve essere scritta.
Const n=4; Type vett=Array[1..n] Of Integer; Function posizione(v: vett; chiave: Integer): Integer; Var inf, sup, i: Integer; found : Boolean; Begin inf:=1; sup:=n; found:=false; posizione:=-1; While(inf <= sup) And (Not found) Do Begin i:=(inf+sup) Div 2; If(chiave < v[i]) Then sup:=i Else If(chiave > v[i]) Then inf:=i+1 Else Begin found:=true; posizione:=i End End End;
Risposta: riga 18 diventa sup:= i-1;
Soluzione
Tratta da: Materiale didattico 2008
Il problema risulta difficile per coloro che non conoscono l’algoritmo di ricerca binaria.
Occorre infatti sempre escludere l’elemento centrale (indicato, nel nostro caso, dalla variabile i) dalla bisezione successiva per non incorrere in cicli infiniti.Questo evento su può creare, ad esempio, eseguendo il seguente corpo di programma principale:
Var a : vett; Begin a[1]:=10; a[2]:= 20; a[3]:=30; a[4]:=40; Writeln(posizione(a, 12)); End.I valori di inf e sup assunti via via all’inizio di ogni iterazione del while della funzione sono:
1 4
1 2
2 2
2 2
…La variabile sup resta dunque bloccata sul valore 2 (come inf) impedendo così l’uscita dal while.
Con la modifica proposta i valori assunti sarebbero invece:
1 4
1 1
2 1Determinando così la falsità della condizione (inf <= sup) e la conseguente uscita dal while.