Dom 19 Maggio, 14:56:43 - 2019

Autore Topic: Soluzione alternativa esame 10/02/2016-C  (Letto 224 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline John Marston

  • Studente
  • *
  • Post: 12
  • FeedBack: +3/-0
    • Mostra profilo
Soluzione alternativa esame 10/02/2016-C
« il: Mer 06 Febbraio, 11:15:37 - 2019 »
Buongiorno, vorrei dei chiarimenti riguardo un vecchio esame, il C del 10/02/2016. L'esercizio 1 richiede di fare una funzione che calcola max, min e il numero di chiamate ricorsive, che deve essere quello minimo.
Tuttavia la soluzione proposta non fa il numero minimo di chiamate ricorsive imho.

Questo il mio output:
Codice: [Seleziona]
(5,17,3) [corretto: (5,17,5)]
(5,25,2) [corretto: (5,25,4)]
(9,9,0) [corretto: (9,9,2)]
espresso come (min, max, numero_di_chiamate)

Il numero minore di chiamate nella mia soluzione e' dovuto al fatto che non viene "sprecata" una chiamata per entrare in un nodo che gia si sa essere vuoto. La chiamata viene fatta solo sui nodi pieni T()
Vorrei quindi capire se questa soluzione, seppur meno elegante, sia corretta :sisi:

questo e' il codice:
Codice: [Seleziona]
sealed abstract class Tree(){
    def minMax:(Int, Int, Int) = this match{
        case E()        =>  return (0, 0, 0)
        case T(l,x,r)   => {
            if(r==E() && l==E()) return (x, x, 0)
            else if(l==E()){
                val _max = r.max(1)
                return(x, _max._1, _max._2)
            }
            else if(r==E()){
                val _min = l.min(1)
                return(_min._1, x, _min._2)
            }
            else{
                val _min = l.min(1)
                val _max = r.max(1)
                return (_min._1, _max._1, (_min._2 + _max._2))
            }
        }
    }

    def min(num_calls:Int):(Int, Int) = this match {
        case E() => return (0, num_calls)
        case T(l,x,r) => {
            if(l==E()) return (x, num_calls)
            else l.min(num_calls+1)
        }
    }

    def max(num_calls:Int):(Int, Int) = this match{
        case E() => return (0, num_calls)
        case T(l,x,r) => {
            if(r==E()) return (x, num_calls)
            else r.max(num_calls+1)
        }
    }
}
case class E() extends Tree()
case class T(l:Tree, x:Int, r:Tree) extends Tree()
questa non è una firma.

Offline lupin

  • Prof
  • Direttore di Dipartimento
  • ******
  • Post: 2804
  • FeedBack: +340/-14
    • Mostra profilo
Re:Soluzione alternativa esame 10/02/2016-C
« Risposta #1 il: Mer 06 Febbraio, 18:53:26 - 2019 »
Dipende da come è formulato il testo. Potresti fare "unrolling" delle chiamate e fare ancora meno di quello che fai tu stesso. Diciamo che la logica ricorsiva "pulita" che ci si aspettava nel testo consiste nell'entrare sempre in un nodo e poi capire come fare. In sede di esame, è meglio parlarne a voce prima di procedere con una soluzione piuttosto che con un'altra.
Camil Demetrescu

"If you think education is expensive, try ignorance" (Robert Orben)