Diploma Universitario di Ingegneria Informatica
Esame di Fondamenti di Informatica II - secondo modulo
A.A. 1999/2000 - Appello del 19 luglio 2000

TipoAstratto Castello

Sorte Cas (sorta per il dominio di interesse)

Funzioni

• Crea : (Intero) --> Cas
  precondizioni e postcondizioni per crea(n) = c
  pre: nessuna
  post: c è un castello con n stanze e nessuna porta che le congiunge; le stanze sono rappresentate dai numeri 0...n-1; la stanza 0 è l'ingresso

• NumeroStanze : (Cas) --> Intero
  precondizione e postocondizioni per NumeroStanze(c) = n
  pre: nessuna
  post: n è il numero delle stanze di c

• AggiungiPorta : (Cas,Intero,Intero) --> (Cas)
  precondizione e postocondizioni per AggiungiPorta(c,i,j) = (Cas)
  pre: 0 <= i <= NumeroStanze(c)-1, 0 <= j <= NumeroStanze(c)-1, i =/= j
  post: d è il castello ottenuto da c aggiungendo una porta tra i e j; se c già contiene una porta tra i e j allora d=c

• QualiPorte : (Cas,Intero) --> (Enumerazione(Intero))
  precondizioni e postcondizioni per QualiPorte(c,i) = e
  pre: 0 <= i <= NumeroStanze(c)-1
  post: e è una (qualsiasi) enumerazione delle stanze direttamente connesse alla stanza i nel castello c

• EsistePorta : (Cas,Intero,Intero) --> Boolean
  precondizione e postocondizioni per EsistePorta(c,i,j) = b
  pre: 0 <= i <= NumeroStanze(c)-1, 0 <= j <= NumeroStanze(c)-1, i =/= j
  post: b=true se esiste una porta tra tra i e j; b=false altrimenti

FineTipoAstratto

Scrivere una classe C++ Castello (file .h e file .cpp) che realizzi il tipo astratto Castello, in modo che tutte le operazioni del tipo astratto, escluso Crea, siano realizzate in tempo costante (O(1)) nel caso atteso. Inoltre l'enemerazione restituita da QualiPorte deve permettere di passare da un elemento al successivo in tempo costante (O(1)). Qualora si faccia uso di strutture dati ausiliarie, quali Heap, AlberoRicerca, TavolaHash, Grafo, Iteratore, ecc., si riporti solo la definizione della classe (file .h) riportando una breve descrizione testuale delle funzioni più significative e del loro costo computazionale.

Problema 2   Realizzare una funzione esterna della classe Castello che dato un castello c restituisca la stanza più remota, cioè più lontana dalla stanza 0; qualora ne esista più di una se ne restituisca una qualsiasi.