PDA

Visualizza la versione completa : [FORTRAN 95] Ricerca Binaria


anna2312
07-01-2010, 19:31
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
07-01-2010, 19:36
E dove incontri i problemi? Hai cominciato a buttare giu' qualcosa? Qualche idea?

anna2312
07-01-2010, 19:37
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
07-01-2010, 19:41
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/pub/Notes/Languages/Fortran/Resources/www.pdas.com/binsrch.htm

anna2312
07-01-2010, 19:44
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
07-01-2010, 20:47
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
07-01-2010, 21:48
Ma che vuol dire deve essere ricorsiva?
e cosa devo fare per farla diventre cosi?

YuYevon
08-01-2010, 09:54
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 (http://it.wikipedia.org/wiki/Algoritmo_ricorsivo) 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
08-01-2010, 12:59
Grazie mille!Così funziona, non mi ero resa conto degli errori fatti!Ancora grazie! Scusate per il tag ma nn sapevo dovesse farsi cosi!

Loading