Una compagnia di traghetti offre 12 viaggi giornalieri per un'isola (ad es., uno ogni ora dalle 8 alle 19), ciascuno identificato da un codice intero compreso tra 0 e 11. Ogni traghetto della compagnia può trasportare autoveicoli per una lunghezza complessiva massima fissata. Il numero di autoveicoli già assegnati e la disponibilità residua in metri per ciascuno dei 12 viaggi sono memorizzati in una opportuna struttura di dati in memoria centrale.
Si richiede di risolvere i seguenti punti:
Ad esempio, se al viaggio 5 sono già assegnati 30 autoveicoli con disponibilità residua di 4.20 metri, al viaggio 6 sono già assegnati 28 autoveicoli con disponibilità residua di 3.40 metri, e al viaggio 7 sono già assegnati 32 autoveicoli con disponibilità residua di 6.80 metri, allora, ad un autoveicolo di 4.50 metri che richiede l'imbarco sul viaggio 5, può essere assegnato il viaggio 7, e per tale viaggio 7 il numero di autoveicoli assegnati diventa 33 con disponibilità residua di 2.30 metri.
Progettare una funzione C (o funzione/procedura Pascal) che, presi in ingresso attraverso opportuni parametri il nome di un file di richieste di imbarco e la struttura di dati che memorizza, per ciascuno dei 12 viaggi, la disponibilità residua in metri e il numero di autoveicoli già assegnati, costruisca e restituisca alla funzione chiamante una lista, rappresentata attraverso strutture (Pascal: record) e puntatori, in cui ciascun elemento contiene la targa di un autoveicolo ed il codice del viaggio che gli viene assegnato. Gli autoveicoli devono comparire nella lista nello stesso ordine che avevano nel file. Gli autoveicoli a cui non può essere assegnato alcun viaggio non devono comparire nella lista. La funzione deve inoltre aggiornare la struttura di dati passata come parametro in base alle assegnazioni effettuate.
Ovviamente, per determinare il codice del viaggio a cui un autoveicolo può essere assegnato, la funzione dovrà attivare in modo opportuno la funzione sviluppata al punto 2.
Considerare il numero m ottenuto anteponendo 3 all'ultima cifra del proprio numero di matricola (in decimale), ed il numero n ottenuto anteponendo 2 alla penultima cifra del proprio numero di matricola. Fornire le rappresentazioni binarie di m ed n, illustrando il procedimento seguito per il calcolo.
Calcolare m+n, m-n e n-m, effettuando le operazioni in complemento a 2 ed utilizzando in tutti e tre i casi un numero di cifre sufficienti per rappresentare gli operandi ed effettuare l'operazione senza avere trabocco.
Descrivere l'algoritmo di ricerca binaria in un vettore, utilizzando codice C/Pascal, oppure pseudocodice ad un livello di dettaglio sufficiente per essere direttamente implementato. Discuterne la complessità computazionale. Sotto quali condizioni può essere utilizzata la ricerca binaria?
Fornire la specifica del tipo di dato astratto Pila. Illustrare una delle possibili rappresentazioni in C/Pascal e fornire le dichiarazioni di tipo opportune. Fornire l'implementazione in C/Pascal della funzione di inserimento di un elemento in pila nella rappresentazione scelta.