Problema 1  Una società che offre servizi su internet (provider) gestisce diversi clienti abbonati. La specifica del tipo astratto ``provider'' è:

TipoAstratto Provider

Commento

ogni valore del tipo rappresenta una società che offre servizi su internet

Sorte

Pro (sorta per il dominio di interesse),    Cliente sorta per il dominio dei clienti

Funzioni

  

Crea : () ===> Pro
precondizioni e postcondizioni per Crea() = p
pre: nessuna
post: p è una società che non ha clienti abbonati

NumeroClienti : (Pro) ===> Intero
precondizioni e postcondizioni per NumeroClienti(p) = i
pre: nessuna
post: i è il numero di clienti di p

AggiungiCliente : (Pro, Cliente) ===> Pro
precondizioni e postcondizioni per AggiungiCliente(p,c) = r
pre: nessuna
post: se c non è presente in p, r è la società ottenuta da p aggiungendo il cliente c, che è identificato dal numero NumeroClienti(p) + 1; altrimenti, r è uguale a p

DammiCliente : (Pro,Intero) ===> Cliente
precondizioni e postcondizioni per DammiCliente(p,i) = c
pre: 1 <= i <= NumeroClienti(p)
post: c è l'i-esimo cliente di p

FineTipoAstratto

Domanda 1   Scrivere la definizione (solo file.h) di una classe C++ Provider che realizzi il tipo astratto Provider in modo da rendere DammiCliente il più efficiente possibile. Si assuma l'esistenza della classe Cliente, così specificata

class Cliente
{public:
  Cliente(int d);            // costruisce un cliente che ha bisogno di d KByte di memoria
  int DammiRichiesta();      // restituisce il numero di KByte di cui il cliente ha bisogno
  // non interessa il resto
};

Domanda 2   Il provider deve decidere di quali clienti soddisfare la richiesta di memoria. La decisione deve essere presa sulla base dei seguenti criteri:

• esiste un limite sulla dimensione della memoria che il provider mette complessivamente a disposizione dei clienti,
• ad ogni cliente viene assegnato o zero KByte, oppure tutti i KByte che egli richiede,
• occorre massimizzare il numero di clienti soddisfatti.

• un oggetto p della classe Provider,
• un intero b che rappresenta il numero di Kbyte che il provider mette complessivamente a disposizione dei clienti,

Si risolva detto problema utilizzando la tecnica greedy (o golosa), discutendo brevemente la suddivisione in stadi della generico elemento dello spazio di ricerca utilizzato (cioè la strutturazione della soluzione astratta) ed il criterio di scelta greedy adottato. Scrivere una funzione che risolva il problema mediante l'algoritmo generico Greedy.