Dom 18 Agosto, 06:31:58 - 2019

Autore Topic: Nuova modalità esame  (Letto 9891 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Gianzo

  • Studente
  • *
  • Post: 4
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #90 il: Gio 08 Giugno, 12:07:01 - 2017 »
Buon giorno a tutti! Anche io sto preparando quest'esame e ho pensato a questa soluzione per l'esercizio proposto dal Prof, sia la prima che la seconda parte. ecco a voi:

Codice: [Seleziona]
int i = 0;
int n = 0;
public boolean isComplete(){
i = 0;
n = 0;
BinTree b = this;
isComplete(b);
int h = (int) (n-1)/2;
if(h>i&& h!=0||n!= (2*i)+1) return false;
return true;
}

public void isComplete(BinTree root){
n++;
if(root.left!= null && root.right!= null)
i++;
if(root.left!=null){
  isComplete(root.left);
}
if(root.right!= null)
isComplete(root.right);

}
questo è il metodo isComplete(), praticamente ho ragionato sulle proprietà dei nodi in un albero binario completo, con n conto i nodi totali e con i solo quelli interni. ecco cosa mi restituisce:
Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo

Per la seconda parte invece mi sono servito del TDA coda implementato in queue.java, servendomene per fare una visita in preOrder senza usare la ricorsione. Non ho capito cosa significhi l'intero che rappresenta il "livello" dell'albero, io l'ho interpretato come il log2 del numero dei nodi che sono alla stessa "altezza". il test di completezza viene sempre corretto ma non riesco a far eseguire l'ultima chiamata nel programma di test:
Codice: [Seleziona]
Random rnd = new Random();

public BinTree generateCompleteTree(int level){
BinTree bt = this;
BinTree ris = bt;
Queue q = new Queue();

int i = 0;
int nodes = 0;

while(i<level){
if(i>0)
bt = (BinTree) q.dequeue();
BinTree sx = new BinTree(rnd.nextInt(50));
BinTree dx = new BinTree(rnd.nextInt(50));
if(bt.right == null){
bt.setRightChild(dx);
q.enqueue(dx);}
if(bt.left==null){
bt.setLeftChild(sx);
q.enqueue(sx);}
nodes = nodes+1;
double l2 =  Math.floor(Math.log(nodes)/Math.log(2));
if((int) l2==i){
nodes = 0;
i++;}
}
return ris;
}
Ed ecco cosa mi restituiscono i test sul secondo metodo...
Codice: [Seleziona]
1
-29
--38
---#
---#
--49
---#
---#
-17
--38
---#
---#
--36
---#
---#
Albero Completo
Figlio destro già presente
1
-40
--#
--#
-1
--#
--#
Albero Completo
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Random.<init>(Random.java:137)
        at java.util.Random.<init>(Random.java:105)
        at binTree.BinTree.<init>(BinTree.java:64)
        at binTree.BinTree.generateCompleteTree(BinTr
        at test.BinTreeTest.main(BinTreeTest.java:78)
Come vedete non riesce a lanciare l'ultimo metodo... aiuti?  ;D

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #91 il: Gio 08 Giugno, 12:58:41 - 2017 »
Buon giorno a tutti! Anche io sto preparando quest'esame e ho pensato a questa soluzione per l'esercizio proposto dal Prof, sia la prima che la seconda parte. ecco a voi:

Codice: [Seleziona]
int i = 0;
int n = 0;
public boolean isComplete(){
i = 0;
n = 0;
BinTree b = this;
isComplete(b);
int h = (int) (n-1)/2;
if(h>i&& h!=0||n!= (2*i)+1) return false;
return true;
}

public void isComplete(BinTree root){
n++;
if(root.left!= null && root.right!= null)
i++;
if(root.left!=null){
  isComplete(root.left);
}
if(root.right!= null)
isComplete(root.right);

}
questo è il metodo isComplete(), praticamente ho ragionato sulle proprietà dei nodi in un albero binario completo, con n conto i nodi totali e con i solo quelli interni. ecco cosa mi restituisce:
Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo

Per la seconda parte invece mi sono servito del TDA coda implementato in queue.java, servendomene per fare una visita in preOrder senza usare la ricorsione. Non ho capito cosa significhi l'intero che rappresenta il "livello" dell'albero, io l'ho interpretato come il log2 del numero dei nodi che sono alla stessa "altezza". il test di completezza viene sempre corretto ma non riesco a far eseguire l'ultima chiamata nel programma di test:
Codice: [Seleziona]
Random rnd = new Random();

public BinTree generateCompleteTree(int level){
BinTree bt = this;
BinTree ris = bt;
Queue q = new Queue();

int i = 0;
int nodes = 0;

while(i<level){
if(i>0)
bt = (BinTree) q.dequeue();
BinTree sx = new BinTree(rnd.nextInt(50));
BinTree dx = new BinTree(rnd.nextInt(50));
if(bt.right == null){
bt.setRightChild(dx);
q.enqueue(dx);}
if(bt.left==null){
bt.setLeftChild(sx);
q.enqueue(sx);}
nodes = nodes+1;
double l2 =  Math.floor(Math.log(nodes)/Math.log(2));
if((int) l2==i){
nodes = 0;
i++;}
}
return ris;
}
Ed ecco cosa mi restituiscono i test sul secondo metodo...
Codice: [Seleziona]
1
-29
--38
---#
---#
--49
---#
---#
-17
--38
---#
---#
--36
---#
---#
Albero Completo
Figlio destro già presente
1
-40
--#
--#
-1
--#
--#
Albero Completo
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Random.<init>(Random.java:137)
        at java.util.Random.<init>(Random.java:105)
        at binTree.BinTree.<init>(BinTree.java:64)
        at binTree.BinTree.generateCompleteTree(BinTr
        at test.BinTreeTest.main(BinTreeTest.java:78)
Come vedete non riesce a lanciare l'ultimo metodo... aiuti?  ;D
Io il parametro level per generare l' albero completo l'ho interpretato in questo modo:
level=0 c'è il nodo radice
level=1 ci devono essere due nodi
level=2 ci devono essere 4  nodi
level=3 ci devono essere 8 nodi
......
level=i ci devono essere 2i nodi

Non so se è la tua stessa interpretazione

Offline Gianzo

  • Studente
  • *
  • Post: 4
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #92 il: Gio 08 Giugno, 15:09:39 - 2017 »
E' la stessa che ho dato io! Mi sono dimenticato di aggiungere che ho provato pure a farla in maniera ricorsiva (senza l'ausilio della coda) ma mi da sempre il solito errore

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #93 il: Gio 08 Giugno, 15:38:36 - 2017 »
E' la stessa che ho dato io! Mi sono dimenticato di aggiungere che ho provato pure a farla in maniera ricorsiva (senza l'ausilio della coda) ma mi da sempre il solito errore
ah ok :D :D non mi ero reso conto che stavamo dicendo la stessa cosa scusami  :asd:

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #94 il: Gio 08 Giugno, 16:07:02 - 2017 »
Nel secondo esercizio generi l'albero ma non hai la certezza che esso sia completo. L'esercizio 2 chiede che quando fai generateCompleteTree ti deve creare sempre un albero completo. E nel codice non sembra che lo faccia questo. Ma sinceramente è un mio pensiero, non sono tanto sicuro che sia corretto ciò che ho detto

No non genero un albero qualsiasi, genero sempre un albero "pieno" in tutti i suoi livelli. Allora lo crea sempre un albero completo. infatti in "generateCompleteTree" io creo la radice dell'albero (ogni nodo di un livello avranno la stassa chiave che corrisponde appunto al loro livello nell'albero). La radice infatti la creo con chiave 1, poi passo la radice appena creata alla funzione "appoGenerateCompleteTree" con la sua chiave e con il livello diminuito di 1, questo perchè ogni nodo deve avere al massimo un sottoalbero di altezza level-1, level-2, level-3 ecc ecc, questo a seconda di dove si trovi il nodo.
La funzione ricorsivamente crea i vari figli sinistri e destri, ogni nodo e ogni livello sarà pieno, la ricorsione si fermerà quando level sarà 0.
Ed essendo pieno in ogni livello, e quando ha questa caratteristica l'albero è sempre un albero completo.
« Ultima modifica: Gio 08 Giugno, 16:09:22 - 2017 da john »

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #95 il: Gio 08 Giugno, 16:51:47 - 2017 »
Ragazzi, ma qualcuno ha fatto l'esercizio 3 "Livello con somma con chiavi più alta" dell'esercitazione del 21 marzo?

https://drive.google.com/drive/folders/0B4_lsbtik3xJMjhVY29SWW9HU2c

Vi lascio il link, e in allegato il testo, sto scapocciando perchè non so come impostare l'algoritmo, ho visto anche la soluzione ma proprio non riesco a capire la logica che ha seguito il prof  :asd: :sisi:


Offline Gianzo

  • Studente
  • *
  • Post: 4
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #96 il: Ven 09 Giugno, 10:30:59 - 2017 »
Ragazzi, ma qualcuno ha fatto l'esercizio 3 "Livello con somma con chiavi più alta" dell'esercitazione del 21 marzo?

https://drive.google.com/drive/folders/0B4_lsbtik3xJMjhVY29SWW9HU2c

Vi lascio il link, e in allegato il testo, sto scapocciando perchè non so come impostare l'algoritmo, ho visto anche la soluzione ma proprio non riesco a capire la logica che ha seguito il prof  :asd: :sisi:

In realtà dovresti usare una visita in ampiezza dell'albero, la soluzione è basata su coda, infatti nella visita lui salva sempre il primo figlio del nodo n in q e poi scorre i fratelli di n (se ne ha) per ottenere la somma delle chiavi

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #97 il: Ven 09 Giugno, 11:34:26 - 2017 »
In realtà dovresti usare una visita in ampiezza dell'albero, la soluzione è basata su coda, infatti nella visita lui salva sempre il primo figlio del nodo n in q e poi scorre i fratelli di n (se ne ha) per ottenere la somma delle chiavi

Ah ok ok, ora ho capito. Grazie tante.
Tu come hai svolto il punto due della terza domanda? Qualcuno per caso ha lo svolgimento fatto a lezione?

Offline nox91

  • Global Moderator
  • Studente
  • *****
  • Post: 24
  • FeedBack: +1/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #98 il: Ven 09 Giugno, 12:30:19 - 2017 »
Scusate, ma il primo esercizio della simulazione non viene come costo la sommatoria da 1 a array.length?
Nel caso peggiore, ovvero un array in ordine decrescente [4,3,2,1] esegue 6 chiamate, con 5 elementi 10.

Offline zeusm

  • Studente
  • *
  • Post: 32
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #99 il: Ven 09 Giugno, 15:57:46 - 2017 »
Scusate, ma il primo esercizio della simulazione non viene come costo la sommatoria da 1 a array.length?
Nel caso peggiore, ovvero un array in ordine decrescente [4,3,2,1] esegue 6 chiamate, con 5 elementi 10.

Io l'ho svolto così, non so se sia corretto :
La dimensione dell'input è la dimensione dell'array che chiamo n. f3(int[]) ha costo costante se n <=1 altrimenti ha costo pari al costo di f2(int[],int).
f2 ha costo costante se n<=1 ovvero se i > n altrimenti ha costo n*(costo di f1) dato che la chiamata ricorsiva di f2 viene eseguita nel caso peggiore n volte.  f1(int[],int ,int) dovrebbe avere nel caso peggiore costo O(n) quindi in totale il costo di f3 dovrebbe essere O(n2

Offline roberto93

  • Studente
  • *
  • Post: 25
  • FeedBack: +2/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #100 il: Sab 10 Giugno, 10:24:09 - 2017 »
qualcuno ha svolto l'esercizio 2 dell'esempio del "nuovo" ? quello sui terminali isolati del BST

Offline Gianzo

  • Studente
  • *
  • Post: 4
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #101 il: Sab 10 Giugno, 12:07:39 - 2017 »
qualcuno ha svolto l'esercizio 2 dell'esempio del "nuovo" ? quello sui terminali isolati del BST

Ecco una mia soluzione... ho provato vari test ed effettivamente finora mi ha sempre dato il risultato giusto. Il tempo è sicuramente lineare perchè fa due visite dell'albero in postorder ma in metodi separati, ma non so se effettivamente sarebbe possibile ridurre tutto ad una visita sola. l'unica accortezza è che non ritorna null perchè il metodo è void, ma non dovrebbe essere difficile modificare la signature dei metodi.

Codice: [Seleziona]
public void trovaIsolati(BinTree T){

BinTree[] Ts = new BinTree[2];
trovaIsolati(T,T,Ts,0);

if(Ts[0] == null|| Ts[1] == null){
                 System.out.print("nessuna coppia di isolati trovata!");
return ;
                }
BinTree pred = null;
creaPercorso(T,Ts[0],Ts[1],pred);
System.out.println(s.toString()+" "+s2.toString());
int ciaone = s.pop();
while(s2.size()>0){
n++;
s.push(s2.pop());
}
System.out.println(n);
System.out.println(s.toString());
}

        Stack <Integer> s= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();

public void creaPercorso(BinTree T,BinTree fst, BinTree snd, BinTree pred){
if(T.left!=null)
creaPercorso(T.left,fst,snd,T);
if(T.right!=null)
creaPercorso(T.right,fst,snd,T);
if(T.key == fst.key){
s.push(T.key);
}
if(T.key == snd.key){
s2.push(T.key);
s2.push(pred.key);
}
if(!s.isEmpty()&&!s2.isEmpty()&&s2.peek() == s.peek())return ;
if(s.size()>0 && T.key == s.peek()&& pred!=null)
s.push(pred.key);
else if(s2.size()>0){
    if(T.key == s2.peek()&& pred!=null)
s2.push(pred.key);
}
}

int l1 = 0;
int l2 = 0;


public void trovaIsolati(BinTree T,BinTree pred,BinTree[] ts,int lvl){
if(T.left!= null)
trovaIsolati(T.left,T,ts,lvl+1);
if(T.right!=null)
trovaIsolati(T.right,T,ts,lvl+1);
if((ts[0]== null||l1<lvl)&&(pred.left == T || pred.right == T)
&&(pred.right == null || pred.left == null)&&(T.left== null&& T.right== null)){
if(l1 <= lvl){ts[1] = ts[0];
ts[0] = T;}
if(ts[0]==null||l1<lvl)
  ts[0] = T;
l1 = lvl;
}
               else if((ts[1]== null||l2<=lvl)&&(pred.left == T|| pred.right == T)
&&(pred.left == null || pred.right == null)&&(T.left== null&& T.right== null)){

      ts[1] = T;
      l2 = lvl;
}
}

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #102 il: Mar 13 Giugno, 10:01:19 - 2017 »
Ragazzi ma a voi come è andata ieri?

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #103 il: Mar 13 Giugno, 10:17:27 - 2017 »
per quanto mi riguarda ho avuto un pò di difficoltà al problema 1  e al problema 4 nei punti (b) e (c). Il problema 2 riguardante la programmazione per fortuna non è stato difficile e l'ho fatto tutto.

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #104 il: Mer 14 Giugno, 05:55:26 - 2017 »
Io invece ho avuto difficoltà con la domanda 2, penso me lo valuta pochissimo. Vabbè  :-X :-X Poi della seconda domanda il punto "c" non sono riuscito a finirlo che ho avuto dei problemi con il punto a che sono riuscito a farlo ma ci ho messo troppo tempo. Poi la domanda 4 il punto "c" l'ho lasciato praticamente in bianco.  :-X :-X :-X
Sicuramente per quanqto riguarda la prova al calcolatore era abbastanza fattibile, ma le domande di teoria erano abbastanza impegnative specie la 2.