Un a b an ca da ti c he co ntie ne film

(1)

Es erc izi

Franco ScarselliFondamenti di Informatica I, 2005-2006

Un a b an ca da ti c he co ntie ne film

Si vuol realizzare una banca dati che contiene informazioni su film.

Un fillmècaratterizzato da un nome, un anno di uscita, un produttore e il costo. Si dovranno anche memorizzare gli attori che partecipano al film indicando per ciascuno i ruoli svolti (ad. es. attore protagonista, comparsa,…) e il compensoricevuto.

Si dovràtenere traccia anche di tutti gli attori con il loro nome, cognome, la data di nascita e un curriculum.

L’applicazione dovràavere un’interfaccia utente e si vuol seguire il principio diseparazione fra interfaccia e dati

Per l’insieme degli attori si usi una lista per gli altri insiemi dei vettori

Progettare le classi necessarie, per il momento, indicando solo le variabili e le classi (senza metodi e costruttori)

(2)

Un a b an ca da ti c he co ntie ne film

class Film{Stringnome, produttore;Date dataUscita:intcosto;}class Attore{Stringnome, cognome;Stringcurriculum; Date dataNascita; }class Partecipazione{Attorep;Film f;String ruoli[];} class ListaAttori{ItemAttorihead; }class ItemAttori{Attore value; ItemAttorinext;}class BancaDati{ListaAttoriattori; Film films[];Partecipazione partecipazioni[];}class interfaccia{BancaDatib; }

Un a b an ca da ti c he co ntie ne film : so luz ion e 2

class Film{Stringnome, produttore;Date dataUscita:intcosto;Partecipazione partecipazioni[];}class Attore{Stringnome, cognome;Stringcurriculum; Date dataNascita; }class Partecipazione{Attorep;// Film f;String ruoli[];} class ListaAttori{ItemAttorihead; }class ItemAttori{Attore value; ItemAttorinext;}class BancaDati{ListaAttoriattori; Film films[];// Partecipazione partecipazioni[];}class interfaccia{BancaDatib; } I cambiamentisonoin grassetto

(3)

Un a b an ca da ti c he co ntie ne film : i m eto di

Def inire i m eto di d ell’in terf acc ia e de lla c lass e B anc aD ati

Dov ran no e sse re p oss ibile le s egu enti op era zion i

inse rire un film

rim uov ere un film pe r tit olo e a nno

inse rire un att ore

rim uov ere un att ore pe r no me e c ogn om e

cerc are tu tti i film a c ui u n a ttor e h a p arte cipa to f orn end o il nom e e il cog nom e d ell’a ttor e

Un a b an ca da ti c he co ntie ne film : i m eto di

class BancaDati{ListaAttoriattori; Film films[];Partecipazione partecipazioni[];voidinserisciFilm(Film f);voidrimuoviFilm(Stringtitolo, Date anno);voidinserisciAttore(Attore a);voidrimuoviAttore(Stringnome, Stringcognome);Film[] searchFilm(Stringnome, Stringcognome;} class interfaccia{BancaDatib; voidinserisciFilm();voidrimuoviFilm();voidinserisciAttore();voidrimuoviAttore();voidsearchFilm();}

(4)

Un ’ap plic azio ne pe r la bib lio tec a

Una bib liote ca vuo l re aliz zare un ’ap plic azio ne per ges tire un arc hivio de i libri dis pon ibili. L’a pplic azio ne dov rà me mo rizz are tu tti i libri po sse duti , tutt i gli au tori dei libri e t utti gli e dito ri. P er o gni auto re s i re gist ra il no me , il c ogn om e, il luo go di n asc ita e u na bre ve bio gra fia. Per ogn i ed itor e s i reg istra il nom e e l’in diriz zo. Per ogn i lib ro si r egis tra il tit olo , g li a uto ri, l’ed itor e e l’IS BN ch e è un c odic e d i 13 cifr e.

L’ap plic azio ne dov rà pos sed ere un m enu util izza ndo il q uale sa ra’ pos sibil e inse rire un lib ro, un auto re o u n e dito re. Ino ltre , d ovrà ess ere po ssib ile elim ina re u n lib ro id enti fica ndo lo c on il co dice IS BN . In fine , il me nu dov ra’ perm ette re di cerc are tu tti i lib ri p oss edu ti d alla bib liote ca per tito lo o auto re. Que st’u ltim a fu nzio ne d eve vis ualiz zare tu tti i libri ch e so ddis fan o il crite rio d i ric erca .

Per rea lizza re l’ insie me de gli e dito ri u sare un a st rutt ura da ti d i tip o lis ta. P er gli a ltri i nsie me usa re u na s trut tura di t ipo ve ttor e.

Un ’ap plic azio ne pe r la bib lio tec a

Progettare leclassi Java necessarieper realizzare l’applicazione.

Si richiede la definizione delle classi, variabili e metodi. Nonènecessario implementare i metodi.

Indicare anche la classe che contiene il main.

(5)

Un ’ap plic azio ne pe r la bib lio tec a

class Autore{Stringnome, cognome, biografia;Date dataNascita:}class Editore{Stringnome, indirizzo;}class Libro{Stringtitolo; AutoreautoriLibro[];EditoreeditoreLibro;intISBN[];} class EditorList{EditorItemhead;void insert(intv);void remove(intv);EditorItemsearch(intv); }class EditorItemEditore value;EditorItemnext;}

Un ’ap plic azio ne pe r la bib lio tec a

class Biblioteca{Libro libri[];Autoreautore[];EditorListeditori[]; void inserireAutore(Stringnome, String cognome, String biografia, Date dataNascita);void inserireEditore(Stringnome, String indirizzo);void inserireLibro(Stringtitolo, Autoreautori[],Editoreeditore, intISBN[]);void rimuoviLibro(intISBN[]);Libro[] cerca(Stringtitolo);Libro[] cerca(Autoreautore);}

(6)

Un ’ap plic azio ne pe r la bib lio tec a

class Menu{Biblioteca biblioteca;void inserireAutore();void inserireEditore();void inserireLibro();void rimuoviLibro();void cerca1();void cerca2();static void main(Stringargv);}

Un ’ap plic azio ne pe r la se gre ter ia stu de nti

Una segreteria studenti vuol realizzare un’applicazione per gestire un archivio congli studenti, i corsi e gli esami di un anno accademico. L’applicazione dovràmemorizzare tutti gli studenti, tutti gli esami e tutti i corsidi una facoltà. Per ogni corso si registra il nome e il docente. Per ogni studente si registra il nome, il cognome, la matricola e la data di nascita. Per ogni esame si registra il voto, la data e ovviamente il corso e lo studente.

L’applicazione dovràpossedere un menu utilizzando il quale saràpossibile inserire uno studente, un esame o un corso. Inoltre, dovràessere possibile ricercare uno studente per matricola o cognome e nome. Allo stesso modo dovràessere possibilerimuoverlo indicando il numero di matricola. Infine, l’applicazione dovràpermettere di calcolare le media di ogni studente e ogni corso

Per realizzare l’insieme degli studenti, degli esami e dei corsi usare una strutturadati di tipo vettore

(7)

Un ’ap plic azio ne pe r la se gre ter ia stu de nti

Pro gett are le c lass i Ja va n ece ssa rie p er r ealiz zare l’ap plic azio ne.

Si ri chie de l a d efin izio ne d elle cla ssi, vari abili e c ostr utto ri.

Non è nec ess ario im ple me nta re i m eto di. Ind icar e a nch e la cla sse ch e con tien e il ma in.

Un ’ap plic azio ne pe r la se gre ter ia stu de nti

class Studente{Stringnome, cognome, matricola;Date dataNascita:}class Corso{Stringnome, docente; }class Esame{intvoto; booleanlode;Date data;Studentestudente;Corsocorso;} class Archivio{Studente studenti[];Corsocorsi[];Esameesami[]; void inserireStudente(Stringnome, String cognome, String matricola, Date dataNascita);void inserireCorso(Stringnome, String docente);void inserireEsame(Studentes, intvoto, booleanlode, Date data);Studentecerca(Stringmatricola);Studentecerca(Stringcognome, String nome);void rimuovi(Stringmatricola);float mediaStudente(Stringmatricola);float mediaCorso(stringnome);}

(8)

Un ’ap plic azio ne pe r la se gre ter ia stu de nti

class Menu{Archivio archivioSegreteria;void inserireStudente();void inserireCorso();void inserireEsame();void cercaStudentePerMatricola();void cercaStudentePerNome();void rimuoviStudente();void mediaStudente();void mediaCorso();static void main(Stringarg[]);}

Us o di u na pila

Son o d ate le cla ssi che im ple me nta no una pila di me ssa ggi: cre are il cod ice Jav a ch e

cre a u na p ila c on a l più 10 m ess agg i

inse risc e i m ess agg i:

“messaggio 1”, inviato a “marte”, indirizzo ip“10.0.0.1”da “giove”, indirzzoip“10.0.0.2”

“risposta 1”, inviato a “giove”, indirizzo ip“10.0.0.2”da “marte”, indirzzoip“10.0.0.1”

estr arre da lla p ila t utti i m ess agg i st am pan do il te sto , il n om e d el d estin ata rio e de l m itte nte

class Messaggio{Stringtesto;Indirizzo destinatario, mittente;Messaggio(Indirizzomitt, Indirizzodest, String testo);} class Indirizzo{Stringnome, ip;Indirizzo(Stringnome, Stringip)} class Pila{Pila(intmaxMessaggi);Messaggio Pop();Messaggio Top();voidPush(Messaggio m);booleanisEmpty();}

(9)

Us o di u na pila

Pila p=newPila(10);Indirizzo marte=newIndirizzo(“marte”,”10.0.0.1”);Indirizzo giove=newIndirizzo(“giove”,”10.0.0.2”);Messaggio m1=new Messaggio(giove,marte,”messaggio 1”);Messaggio m2=new Messaggio(marte,giove,”risposta 1”);p.push(m1);p.push(m2);while(!p.isEmpty()){Messaggio m=p.pop();System.out.print(m.testo)System.out.print(”da ”+m.mittente.nome)System.out.println(”a ”+m.destinatario.nome)}

Us o di u n a rch ivi o stu de nti

Son o d ate le clas si c he im ple me nta no u n a rch ivio de gli s tud enti .Sc rive re il co dice Jav a ch e

cre a u n a rch ivio

inse risc e

“Paolo”, “Rossi”residente in “via Verdi 16, Siena”

“Roberto”, “Bianchi”residente in “via Gialli 10, Siena, 53110”

cerc a tu tti g li st ude nti a bita nti a Sie na e ne sta mp a il cog nom e

class Studente{StringNome, Cognome;Indirizzo residenzaStudente(Stringnome, Stringcognome, Stringresidenza)} class Indirizzo{Stringvia, numero, citta;Indirizzo(Stringvia, Stringnumero, Stringcitta)} class Archivio{private Studente studenti[];Archivio();voidinserisci(Studente s)Studente [] cerca(Stringcity)}

(10)

Us o di u n a rch ivi o stu de nti

Archivio a=newArchivio();Indirizzo i1=new Indirizzo(“via Verdi”,”16”,”Siena”);Indirizzo i2=new Indirizzo(“via Gialli”,”10”,”Siena”);Studente paoloRossi=newStudente(“Paolo”,”Rossi”,i1);Studente robertoBianchi=newStudente(“Roberto”,”Bianchi”,i2);a.inserisci(paoloRossi);a.inserisci(robertoBianchi);Studente [] studentiDiSiena=a.search(“siena”);for(inti=0;i<studentiDiSiena.length;i++){System.out.println(studentiDiSiena[i].cognome);}

So m m a co n u na list a di o pe raz ion i

Son o d ate le c lass i ch e im ple me nta no u na lista di o pera zion i (a d e sem pio di u n co nto corr ente )

Ogn i ope razio ne è cara tter izza ta dalla qua ntità e d a u n c ara tter e c he è ‘P’ se l’op era zion e è un pre liev o e ‘D’ se l’op era zion e è un d epo sito

Si im ple me nti (in ma nie ra itera tiva ) u n me tod o ch e ca lcola tot ale delle op era zion i con tan o co me ne gati vi i pre liev i e p osit ivi i dep osit i

class operazione{operazione(floatquantita, char pd);char getPd();float getQuantita();} class itemOperazione{operazione value;itemOperazionenext;} class ListaOperazioni{itemOperazionehead;}

floatcalcolaTotale(ListaOperazioniA)

(11)

So m m a co n u na list a di o pe raz ion i

floatcalcolaTotale(ListaOperazioniA){floatsomma=0;for(itemOperazioneit=A.head; it!=null; it=it.next){if(it.value.getPd()==‘D’) {somma=somma+it.value.getQuantita();}else{somma=somma-it.value.getQuantita();}}return somma;}

So m m a co n u na list a di o pe raz ion iII

La ste ssa fu nzio ne potr ebb e e sse re im ple me nta ta in m anie ra r icor siva . Per farlo occ orre im ple me nta re il m eto do: calc ola Tota leR icor sivo

floatcalcolaTotale(ListaOperazioniA){return calcolaTotaleRicorsivo(A.head);}floatcalcolaTotaleRicorsivo(ItemOperazioniit)….

(12)

So m m a co n u na list a di o pe raz ion iII

floatcalcolaTotaleRicorsivo(ItemOperazioniit){if(it==null) {return 0;}else{if(it.value.getPd()=‘D’){return it.value.getQuantita()+calcolaTotaleRicorsivo(it.next);}else{return -it.value.getQuantita()+calcolaTotaleRicorsivo(it.next);}}}

Pro fon dità di u n a lbe ro bin ario

Son o d ate le c lass i ch e im ple me nta no u n a lbe ro b ina rio d i in teri

Si im ple me nti u n m eto do r icor sivo che ca lcola la p rofo ndit àd ell’a lbe ro

Si re aliz zi il me tod o p rofo ndit aRic orsi va

class Tree{root;} class Node{intvalue;nodo left, right;}

intprofondita(TreeT){return profonditaRicorsiva(T.root);}

intprofonditaRicorsiva(nodo n);

(13)

Pro fon dità di u n a lbe ro bin ario

intprofonditaRicorsiva(nodo n){if(n==null){return 0;}else{intpDestra=profonditaRicorsiva(n.right);intpSinistra=profonditaRicorsiva(n.left);if(pDestra>pSinistra) {return pDestra+1;}else{return pSinistra+1;}}}

No rm a u no

Scrivere un metodo che scorre una matrice a due dimensioni “floatB[][]”e necalcola la norma 1.

La norma1 di unamatricee’ilmassimoper colonna dellasommadeimodulideglielementi

    

 

    

 =

mnnn m m

bbb bbb bbb

B

,2,1, ,22,21,2 ,12,11,1

L MOMM K K

 

 

 

  = ∑

= = mj ji ni

b B

1 ,1 1

m ax

(14)

No rm a u no

^float_normaUno(

floatB[][]){floatnorm=0;for(inti=0;i<B.length;i++){floatcol=0;for(intj=0;j<B[i].length;j++){col=col+Math.abs(B[i][j]);}if(col>norm){norm=col;}}returnnorm;}

No rm a u no II

La ste ssa fu nzio ne potr ebb e e sse re im ple me nta ta in m anie ra r icor siva . Per farlo occ orre im ple me nta re il m eto do n orm aU noR icor sivo che ca lcola rico rsiv am ente la s om ma di o gni colo nna

floatnormaUno(floatB[][])){floata=normaUnoRicorsivo(B,0,B.length);floatmax=Integer.MAX_VALUE;for(inti=0;i<B[0].length;i+){if(max<a[i]) {max=a[i];}}return max;}float[] normaUnoRicorsivo(floatB[][], intminRow, intmaxRow)….

(15)

No rm a u no II

floatnormaUnoRicorsivo(floatB[][], intminRow, intmaxRow){int[] res=newint[B[0].length];if(maxRow==minRow){for(inti=0;i<res.length;i++){res[i]=B[minRow][i];}}else{int[] a=normaUnoRicorsivo(floatB[][], minRow+1,maxRow);for(inti=0;i<res.length;i++){res[i]=B[minRow][i]+a[i];}}return res;}

So m m a ele m en tim ag gio rid i ze ro

Son o d ate le cla ssi che im ple me nta no una lis ta di inte ri: scriv ere il me tod o ja va c he c alco la la so mm a

Variabilie metodidellalistaUn elementodellalista

intsomma(Listlista) Il metododaimplementareclass Lista{Itemhead;void insert(intv);void remove(intv);Item search(intv); } class Item{intvalue;Item next;}

(16)

So m m a ele m en tim ag gio rid i ze ro

intsomma(ListA){intres=0;for(Itemit=A.head; it!=null; it=it.next){if(it.value>0) {res=res+it.value;}}return res;}

So m m a ele m en tim ag gio rid i ze ro II

La stessa funzionepotrebbe essereimplementata inmaniera ricorsiva. Per farlo occorre implementare il metodosommaRicorsivo

intsomma(Listlista){return sommaRicorsivo(Lista.head);}intsommaRicorsivo(Itemit)

(17)

So m m a ele m en tim ag gio rid i ze ro II

intsommaRicorsivo(Itemit){if(it==null) {return 0;}if(it.value>=0){return it.value+ sommaRicorsivo(it.next);}else {return sommaRicorsivo(it.next);}}

So m m a de l c ost o di u na list a di art ico li

Son o d ate le cla ssi che im ple me nta no una lis ta di Artic oli in ven dita : scriv ere il me tod o c he calc ola la som ma de l co sto de gli artic oli di u n cert o tip o

Variabilie metodidellalista Un elementodellalista

intsomma(Listlista, intcodice) Il metododaimplementareclass Lista{Itemhead;void insert(intv);void remove(intv);Item search(intv); } class Item{Articolo value;Item next;}class Articolo{floatcosto;Stringnome;intcodice;} Un articolo

(18)

So m m a de l c ost o di u na list a di art ico li

floatsomma(ListA, intcodice){intres=0;for(Itemit=A.head; it!=null; it=it.next){if(it.value.codice==codice) {res=res+it.value.costo;}}return res;}

So m m a de l c ost o di u na list a di art ico li

La stessa funzionepotrebbe essereimplementata inmaniera ricorsiva. Per farlo occorre implementare il metodosommaRicorsivo

floatsomma(Listlista, intcodice){return sommaRicorsivo(Lista.head,intcodice);}floatsommaRicorsivo(Itemit, intcodice)

(19)

So m m a ele m en tim ag gio rid i ze ro II

floatsommaRicorsivo(Itemit, intcodice){if(it==null) {return 0;}if(it.value.codice=codice){return it.value.costo+ sommaRicorsivo(it.next);}else {return sommaRicorsivo(it.next);}}

Co m ple ssit a’ di u n p rog ram m a

Calc ola re l’ ord ine asin totic o (n ota zion e O (f(n ))) del num ero di m oltip lica zion i svo lte d al s egu ente m eto do r ispe tto al v alo re d el p ara me tro n

void metodo2(int n){inti=1;intres=1;while(i<=n){for(intj=0;j<n;j++){res=res*j+i;} i=2*i; }} Il corpodel while vieneeseguitolog2n volteIl corpodel for vieneeseguiton volte RispostaO(n*log2 n)

(20)

Co m ple ssit a’ di u n p rog ram m a

Calcolare l’ordine asintotico (notazione O(f(n))) del numero di moltiplicazionisvolte dal seguente metodo rispetto al valore del parametro n

Nelcasoservisse, siricordache…2 )1(

1 +=

∑

= aai a

ivoid metodo2(int n){intres=1;for(inti=1;i<=Math.pow(n,2);i++){for(j=1;j<=i;j++){res=res*2;} }} Il corpodel for vieneeseguiton2volteIl corpodel for vieneeseguitoi volteRispostaO(n 4) 2 )1( 22

1 2+=

∑

= nni n

i Poiche’…

Co m ple ssit a’ di u n p rog ram m a

Calc ola re l’ ord ine asin totic o (n ota zion e O (f(n ))) del num ero di som me svo lte dal seg uen te m eto do s ulla va riab ile r es r ispe tto al v alo re d el p ara me tro n

void metodo3(int n){inti=1;intres=1;while(i<=Math.pow(n,2)){for(intj=0;j<Math.pow(n,3);j++;){res=res+3;} i=2*i; }} Il corpodel while vieneeseguito2 log2n volteIl corpodel for vieneeseguiton 3volte RispostaO(n 3*log2 n)

(21)

Co m ple ssit a’ di u n p rog ram m a

Nelcasoservisse, siricordache…

6 32 269

1 2 12 3

3 nnnii n

ini ++==

∑ ∑

== void metodo4(int n){intres=1;for(inti=Math.pow(n,3);i>=1;i--){for(j=1;j<=Math.pow(i,2);j++){res=res*2;} }} Il corpodel for vieneeseguiton3volteIl corpodel for vieneeseguitoi2volte

RispostaO(n 9) Poiche’… 6 32 23

1 2aaai a

i ++=∑=

Co m ple ssit a’ di u n p rog ram m a

void metodo5(int n){intres=1;for(inti=1;i<=n*n;i++){for(j=1;j<=Math.pow(3,i);j++){res=res+2;} }} Il corpodel for vieneeseguiton2volteIl corpodel for vieneeseguito3ivolteRispostaO( ) Poiche’…

13 133 1

1 22

− −= +

=

∑

nn

i i

23 n

(22)

Co m ple ssit a’ di u n p rog ram m a

Calc ola re l’ ord ine asin totic o (n ota zion e O (f(n ))) del num ero di som me svo lte dal seg uen te m eto do s ulla va riab ile r es r ispe tto al v alo re d el p ara me tro n

void metodo6(int n){intres=1;for(inti=1;i<=Math.log10(n);i=i+1){for(intj=0;j<Math.pow(2,i);j++;){res=res+3;} }} Il corpodel while vieneeseguitolog3n volteIl corpodel for vieneeseguito2ivolte

RispostaO(n 1/log 10)

Poiche’…

2 1

2 1 ) 2( 2

2 1 2

1 3 1 2 2

10log 110log 1110log log

1loglog

1 2 2 2log2 2

1010

− = − ⋅ = − = − − =

++

=

∑ n

n n

nn

i i

Fo rm ule ut ili

2 )1 (

1

+ = ∑

=

a a i

a

i

6 3 2

23

1 2

a a a i

a

i

+ + = ∑

=

1 1

1

− − =

+

=

∑ b b b

aa

i i