[FORTRAN 95] Ricerca Binaria

[anna2312]

Salve a tutti, ho un problema con il linguaggio di programmazione Fortran 95, devo creare una function della ricerca binaria! Il problema sta proprio nella ricerca dell'elemento nel vettore e non nell'ordinamento di questo!
grazie mille!

[oregon]

E dove incontri i problemi? Hai cominciato a buttare giu' qualcosa? Qualche idea?

[anna2312]

Real function ricerca_binaria(n,v,x)
Integer, intent(in)::n
Real,dimension(100),intent(in)::v
Integer, intent(in)::x

!variabili locali
integer::max, min,med

max = n
min = 1
ricerca_binaria = 0
do
med = (max+min)/2
if (v(med) == x) then
ricerca_binaria = 1
else if (v(med) < x) then
max = med-1
else
min = med+1
end if
if (ricerca_binaria==1.or.max<=min) exit
end do

return
end function

ho provato cosi' ma nn funziona

[oregon]

Non funziona in che senso ? Errori? Malfunzionamenti ?

(E' da un po' che non tocco FORTRAN ... e non ho compilatori con cui provare ... ma chi lo usa ancora?)


Qualche ricerca?

http://ckw.phys.ncku.edu.tw/public/p...om/binsrch.htm

[anna2312]

Purtroppo lo usano gli studenti di matematioca del primo anno alla federico II!
Cmq nn mi da errori di compilazione solo che "ricerca_binaria" e' sempre uguale a 0! anche se io inserisco un numero da cercare presente nel vettore!

! Esempio di programma chiamante per la function ricerca_binaria
PROGRAM prova_ricerca
! Dichiarazione delle variabili
REAL,DIMENSION(100)::v
INTEGER::n
INTEGER::i
REAL::x
REAL::ricerca_binaria1
WRITE(*,*) "Questo programma ricerca un elemento x in un array composto"
WRITE(*,*) "da numeri reali distinti con il metodo della ricerca binaria"
DO
WRITE(*,*)"Inserisci la dimensione dell'array"
READ(*,*) n
WRITE (*,*) n
WRITE(*,*)"Inserisci gli elementi tra cui cercare l'elemento x"
READ(*,*) (v(i),i=1,n)
WRITE(*,*) (v(i),i=1,n)
WRITE(*,*) "Inserisci l'elemento x da cercare"
READ(*,*) x
WRITE(*,*) x
CALL bubble_sort(v,n)
WRITE(*,*)"Il vettore ordinato e'",(v(i),i=1,n)
! chiamata alla function ricerca_binaria
ricerca_binaria1=ricerca_binaria(n,v,x)
WRITE(*,*) ricerca_binaria1
IF (ricerca_binaria1==1) THEN
WRITE(*,*) "L'elemento x e' presente nell'elenco di numeri inserito"
ELSE
WRITE(*,*) "L'elemento x non e' presente nell'elenco di numeri inserito"
END IF
DO
WRITE(*,*)"Digita 1 per ripetere, 0 per terminare"
READ(*,*) s
IF(s==0.OR.s==1)EXIT
END DO
IF(s==0)EXIT
END DO
WRITE(*,*)"Il numero digitato e' 0, quindi il programma e' terminato"
STOP
END PROGRAM


Questo è il programma chiamante!!

[YuYevon]

Ma la ricerca binaria dovrebbe avere una chiamata ricorsiva, scritta così non va bene... comunque è lì il problema, il programma chiamante va bene (il bubble_sort() non lo vedo ma penso sia fatto bene, anche perché la stampa del vettore dovrebbe garantirlo).

[anna2312]

Ma che vuol dire deve essere ricorsiva?
e cosa devo fare per farla diventre cosi?

[YuYevon]

Originariamente inviato da anna2312
Ma che vuol dire deve essere ricorsiva?

Ah ottimo, a quanto leggo il Fortran non consente funzioni ricorsive, sarà per questo che non ne hai mai sentito parlare.
Per la ricorsione ti consiglio di leggere qui ma in ogni caso non risolve il problema. L'algoritmo di ricerca binaria è un classico esempio di algoritmo che si risolve con un approccio Divide et Impera, paradigma che trova la sua massima esaltazione proprio nella ricorsione. È comunque possibile scrivere anche una funzione iterativa, e in effetti è quello che hai fatto tu, solo che la sintassi orribile del Fortran (che conosco pochissimo e che ricorda tantissimo l'assembly, come del resto è normale che sia date le sue origini storiche) e il fatto che tu non abbia utilizzato i tag code per postare il codice mi avevano fatto fare confusione.

La routine di ricerca binaria è strutturata abbastanza bene, ma ci sono 3 errori fondamentali:

1) all'interno della funzione hai ridefinito il parametro x come integer, laddove invece nel programma chiamante questo è un real. Ridefiniscilo come real anche nella funzione;

2) sbagli l'aggiornamento di max e min: se v(med) < x devi proseguire con la ricerca nella seconda metà del vettore, non nella prima, quindi anziché essere max = med - 1 devi scrivere min = med + 1. Viceversa nel caso in cui risulti v(med) > x;

3) nel predicato di uscita del ciclo iterativo hai scritto if (ricerca_binaria==1.or.max<=min) ma al posto di <= scrivi solo <.

Così dovrebbe andare. Facci sapere e soprattutto la prossima volta posta il codice indentato con i tag appositi come segue:

Real function ricerca_binaria(n,v,x)

	Integer, intent(in)::n
	Real,dimension(100),intent(in)::v
	Real, intent(in)::x

	!variabili locali
	integer::max, min,med

	max = n
	min = 1
	ricerca_binaria = 0

	do
		med = (max+min)/2

		if (v(med) == x) then
			ricerca_binaria = 1
		else if (v(med) < x) then
			min = med+1
		     else
			max = med-1
		end if

		if (ricerca_binaria==1.or.max<min) exit
	end do

	return

end function

PS: il Fortran a livello accademico, purtroppo, è ben più diffuso di quanto si possa credere. Si usa anche a "Matematica e informatica" presso la SUN di Caserta, ad esempio. Probabilmente Il C ai matematici fa particolarmente schifo.

[anna2312]

Grazie mille!Così funziona, non mi ero resa conto degli errori fatti!Ancora grazie! Scusate per il tag ma nn sapevo dovesse farsi cosi!