{ File: progesol.pas } { Scopo: esercizio sull'uso di grafi } program Progetto; { Esercizio di esame di Fondamenti di Informatica del 12/2/1998. Soluzione completa. } const NumAttivita = 5; type TipoAttivita = 1..NumAttivita; TipoProgetto = array [TipoAttivita, TipoAttivita] of real; { matrice di adiacenza che rappresenta il grafo associato ad un progetto } TipoArco = record sorgente, destinazione : TipoAttivita; costo : real end; { elemento della lista di archi } TipoListaArchi = ^TipoRecordLista; TipoRecordLista = record arco : TipoArco; next : TipoListaArchi end; { Funzione che risolve il punto 2. Vengono fornite due versioni: - una non ottimizzata che usa cicli for, ed - una ottimizzata che usa cicli indefiniti ed esce dai cicli appena possibile. } function NonEsisteAttivitaIsolataNonOttim (progetto: TipoProgetto): boolean; { Restituisce TRUE se in progetto non esiste un'attivita` isolata e FALSE altrimenti. Versione non ottimizzata che usa cicli for. } var i, j : TipoAttivita; { indici usati nei cicli } isolata : boolean; begin { NonEsisteAttivitaIsolataNonOttim } NonEsisteAttivitaIsolataNonOttim := TRUE; { assumi che nessuna attivita` sia isolata } for i := 1 to NumAttivita do begin { considera l'attivita` i-esima } isolata := TRUE; { assumi che sia isolata } for j := 1 to NumAttivita do if (progetto[j,i] <> 0) or { se vi e` un arco da j entrante in i o } (progetto[i,j] <> 0) then { vi e` un arco uscente da i verso j } isolata := FALSE; { allora l'attivita` i non e` isolata } { N.B. NON CI DEVE ESSERE il ramo else } if isolata then { ho verificato che i e` isolata ... } NonEsisteAttivitaIsolataNonOttim := FALSE { e me ne ricordo } { N.B. NON CI DEVE ESSERE il ramo else } end end; { NonEsisteAttivitaIsolataNonOttim } function NonEsisteAttivitaIsolata (progetto: TipoProgetto): boolean; { Restituisce TRUE se in progetto non esiste un'attivita` isolata e FALSE altrimenti. Versione ottimizzata che esce dai cicli appena possibile. } var i, j : integer; { indici usati nei cicli } nessuna, isolata : boolean; begin { NonEsisteAttivitaIsolata } nessuna := TRUE; { assumi che nessuna attivita` sia isolata } i := 1; while (i <= NumAttivita) and nessuna do begin { considera l'attivita` i } isolata := TRUE; { assumi che i sia isolata } j := 1; while (j <= NumAttivita) and isolata do begin if (progetto[j,i] <> 0) or { se vi e` un arco da j entrante in i o } (progetto[i,j] <> 0) then { vi e` un arco uscente da i verso j } isolata := FALSE; { allora l'attivita` i non e` isolata } j := j+1 end; nessuna := not isolata; i := i+1 end; NonEsisteAttivitaIsolata := nessuna end; { NonEsisteAttivitaIsolata } { Procedura che risolve il punto 3. } procedure ListaArchiCostoAlto (progetto: TipoProgetto; r: real; var lista: TipoListaArchi); { Restituisce in lista la lista degli archi di costo maggiore di r. } var i, j : TipoAttivita; { indici usati nei cicli } paux : TipoListaArchi; begin { ListaArchiCostoAlto } lista := NIL; for i := 1 to NumAttivita do for j := 1 to NumAttivita do if progetto[i,j] > r then begin new(paux); with paux^.arco do begin sorgente := i; destinazione := j; costo := progetto[i,j] end; paux ^.next := lista; lista := paux end end; { ListaArchiCostoAlto } { procedure ausialiarie usate dal programma driver } procedure LeggiProgetto (nomefile : string; var progetto: TipoProgetto); { Legge dal file di testo nomefile le informazioni riguardo alle attivita di un progetto, rappresentato tramite matrice di adiacenza. Assume che il file contenga una matrice di reali di 5x5 elementi nonnegativi. } var f : text; i, j : TipoAttivita; begin { LeggiProgetto } assign(f, nomefile); reset(f); for i := 1 to NumAttivita do for j := 1 to NumAttivita do read(f, progetto[i, j]); close(f) end; { LeggiProgetto } procedure StampaProgetto (progetto: TipoProgetto); { Stampa su video le informazioni riguardo al progetto. } var i, j : TipoAttivita; begin { StampaProgetto } for i := 1 to NumAttivita do begin for j := 1 to NumAttivita do write(progetto[i, j]:6:1); writeln end end; { StampaProgetto } procedure StampaListaArchi (lista: TipoListaArchi); { Stampa su video le informazioni riguardo agli archi in lista. } begin { StampaListaArchi } writeln('sorgente':10, 'destinazione':14, 'costo':10); while lista <> NIL do begin with lista^.arco do writeln(sorgente:10, destinazione:14, costo:10:1); lista := lista^.next end end; { StampaListaArchi } { variabili usate nel programma principale } var prog : TipoProgetto; { progetto sul quale vengono fatte le elaborazioni } archi : TipoListaArchi; { lista di archi } nomefile : string; { nome del file contenente le informazioni sul progetto } r : real; { valore reale di soglia usato nel punto 3 } isolate : boolean; { tiene conto dell'esistenza di attivita` isolate } begin { Progetto } { Lettura delle informazioni sul progetto da file. } writeln('Immetti il nome del file dal quale leggere le informazioni sul progetto!'); writeln('(N.B. Il file deve gia` esitere)'); readln(nomefile); LeggiProgetto(nomefile, prog); { lettura da file } writeln; writeln('Matrice di adiacenza che rappresenta il progetto:'); StampaProgetto(prog); { stampa di conferma } { Verifica dell'esistenza di attivita` isolate } { Attivazione della funzione che risolve il punto 2, - prendendo in ingresso la matrice prog che rappresenta le attivita` di un progetto - e restituendo come valore di ritorno il valore booleano calcolato. } isolate := NonEsisteAttivitaIsolata(prog); { stampa del risultato dell'attivazione della funzione 2 } writeln; if isolate then writeln('Il progetto ha attivita` isolate.') else writeln('Il progetto non ha attivita` isolate.'); { Lettura del valore reale di soglia. } writeln; write('Valore di soglia (reale positivo)? '); readln(r); { Attivazione della procedura che risolve il punto 3, - prendendo in ingresso - la matrice prog che rappresenta le attivita` di un progetto e - il valore di soglia r - e restituento in archi la lista degli archi che hanno costo maggiore del valore di soglia r. } ListaArchiCostoAlto(prog, r, archi); { stampa del risultato dell'attivazione della procedura 3 } writeln; writeln('Archi con costo maggiore di ', r:4:1, ':'); StampaListaArchi(archi) end. { Progetto }