Missioni segrete.
Descrizione del problema
Il Commissario Basettoni ha presentato a Topolino le missioni che egli dovrà svolgere segretamente nel corso dell'anno.
Per ogni missione, oltre al luogo da raggiungere, Basettoni ne indica la durata in giorni e la Info massima entro cui deve essere completata.
In altri termini, la missione può iniziare in qualunque giorno dell'anno ma deve durare esattamente il numero di giorni indicato e terminare
non oltre la Info di scadenza.
Topolino, presa la lista delle missioni ricevuta da Basettoni, ordina tali missioni in base alla loro Info di scadenza. Quindi, numera i giorni dell'anno da 1 a 365 (non esistono anni bisestili a Topolinia) e trasforma le date di scadenza in numeri secondo tale numerazione.
Per esempio, se una missione dura 15 giorni e deve essere svolta entro il 18 febbraio, Topolino la vede semplicemente come una coppia di interi 15 49 (in quanto il 18 febbraio è il quarantanovesimo giorno dell'anno).
Poichè può effettuare una sola missione alla volta, Topolino non sarà in grado di svolgerle tutte, pur iniziando una missione il giorno immediatamente successivo a quello in cui termina la precedente. Vuole perciò sapere il numero massimo di missioni che è in grado di eseguire rispettando i vincoli sulla loro durata e scadenza. Supponendo che Topolino già fornisca le coppie di interi ordinate per scadenza (il secondo membro delle coppie), aiutatelo a calcolare il massimo numero di missioni che può svolgere.
Per esempio, se ci sono quattro missioni, una di tre giorni da terminare entro il 5 gennaio, una di quattro giorni entro l'8 gennaio, una di tre giorni entro il 9 gennaio e una di 6 giorni entro il 12 gennaio, Topolino vi fornisce la lista di quattro coppie 3 5, 4 8, 3 9 e 6 12. Il numero massimo di missioni che può svolgere è pari a tre, ossia le missioni corrispondenti alle coppie 3 5, 3 9 e 6 12: la prima missione inizia il primo di gennaio e termina il 3 gennaio; la seconda inizia il 4 gennaio e termina il 6 gennaio; la terza inizia il 7 gennaio e termina il 12 gennaio. (Notare che, scegliendo la missione corrispondente alla coppia 4 8, Topolino può svolgere al più due missioni.)
Dati di input
Il file input.txt è composto da N+1 righe.
La prima riga contiene un intero positivo che rappresenta il numero N di missioni presentate da Basettoni a Topolino.
Le successive N righe rappresentano durata e scadenza delle missioni: ciascuna riga è composta da due interi d e s separati da uno spazio, a rappresentare che la corrispondente missione dura d giorni e deve essere completata entro l's-mo giorno dell'anno.
Dati di output
Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo numero di missioni che Topolino può svolgere. rispettando i vincoli su durata e scadenza.
Assunzioni
1 ≤ N ≤ 100.
1 ≤ d, s ≤ 365 e d < s
Esempio di input/output
| file input.txt | file output.txt |
| 4 | 3 |
| 3 5 | |
| 4 8 | |
| 3 9 | |
| 6 12 |
Analisi del problema: descrizione della soluzione.
La fase di analisi del problema ha lo scopo di individuare la strategia risolutiva e la più adeguata organizzazione dei dati.
Un metodo che consente di pervenire all'algoritmo risolutivo di un problema consiste nell'esaminare il procedimento pratico che una persona segue per giungere alla soluzione.
Riprendendo, quindi, in considerazione la tabella di dati fornita come esempio nel testo del problema e, che si presume sia registrata in un file di tipo testo denominato "Missioni.txt":
| file input.txt |
| 4 |
| 3 5 |
| 4 8 |
| 3 9 |
| 6 12 |
si vede che la prima missione si riesce sicuramente a svolgere per la condizione che d < s per ogni missione.
Si trova che la seconda missione può essere svolta purchè la prima missione venga anticipata di almeno un giorno.
La terza missione non potrà essere svolta.
A questo punto, esaminando le cause che ne impediscono lo svolgimento, si osserva che la somma delle durate delle 3 missioni è:
maggiore della scadenza della terza missione (=9).
Questa è un'osservazione cruciale per verificare la validità di una soluzione, ma resta ancora da stabilire con quale criterio si scarta una missione.
Il testo del problema specifica che si è interessati a svolgere il massimo numero possibile di missioni, quindi sembrerebbe che la scelta di quale scartare sia indifferente. Comunque è preferibile scartare quella di durata maggiore in modo da assicurare un margine di spostamento in anticipo delle missioni quando si cercherà di aggiungerne un'altra.
Quando si giunge all'ultima missione, per il presupposto che la lista è ordinata per data di scadenza, la ricerca della soluzione può terminare perchè si intuisce che non ne esiste una migliore.
Acquisizione dei dati iniziali
L'organizzazione dei dati che meglio agevola l'elaborazione consiste in
un puntatore f al file
Il numero N di missioni da esaminare
Il numero massimo di missioni che si potranno svolgere
variabili per calcoli intermedi (Somma, i, k, ecc..)
La Matrice di N righe e 2 colonne in cui sono elencate le missioni
Un array Sequenza in cui vengono raccolte le missioni che si potranno svolgere
(linea 7) Se il file di testo esiste, lo si apre,
(linea 12) si acquisisce il valore di N
(linee 13-18) si leggono tutte le righe del file e i valori vengono trasferiti nella matrice. Nota: l'istruzione della linea 15 serve a leggere, scartando, lo spazio di separazione tra i due valori.
(linea 17) si fornisce una stampa dei dati letti.
Programma
Il procedimento risolutivo, quindi, è il seguente:
Si accede in successione a tutte le righe della Matrice, per leggere i parametri della missione.
Per ciascuna di queste missioni si memorizza l'indice della riga nell'array Sequenza, contando una missione.
Si calcola la durata complessiva delle missioni incontrate fino a questo punto e si legge la scadenza dell'ultima missione prelevata dalla matrice.
Se la durata delle missioni è maggiore del giorno di scadenza dell'ultima missione scelta, si cerca la missione di durata massima tra quelle già scelte e la si elimina dalla sequenza, oltre, ovviamente, a sottrarre la sua durata dalla somma delle durate complessive delle missioni scelte e a decrementare il numero massimo di missioni.
La descrizione fornita sopra è realizzata con il seguente programma:
facendo variare la variabile i da 0 a N si eseguono le seguenti operazioni:
memorizza l'indice i nell'array Sequenza e conta una missione,
stampa di prova per avere l'informazione sulle operazioni svolte in fase di esecuzione,
La durata della missione i-ma viene aggiunta alla somma della durata compessiva di tutte le missioni scelte,
Si legge la scadenza dell'ultima missione scelta.
altra stampa informativa
il test di accettabilità
Si confronta la durata complessiva delle missioni scelte, contenuta nella variabile Somma con la scadenza dell'ultima missione scelta. Se le missioni terminano dopo, allora si dovrà cercare la missione di durata massima tra quelle scelte,
Per cercare il massimo tra un insieme di valori, si assume, per cominciare, che il primo elemento sia il massimo
si fornisce una stampa informativa
Ricerca del massimo valore di durata
vengono scanditi gli elementi contenuti nell'array Sequenza a iniziare dal secondo, e
quando se ne trova uno che dura più di quello che si era assunto che fosse il massimo,
lo sceglie come nuovo valore massimo
viene annotata, nella variabile Scarta, la sua posizione all'interno dell'array Sequenza
Eliminazione di una missione
L'indice Scarta indica l'elemento dell'array Sequenza che contiene il numero della missione da scartare. La durata di tale missione viene sottratta dalla durata complessiva delle missioni scelte,
Tutti gli elementi che seguono quello scartato vengono ricopiati in una posizione inferiore dell'array Sequenza,
Si decrementa il conteggio delle missioni che si sono trovate,
Tramite un messaggio di stampa si segnala la missione scartata.
Stampa del risultato
Si stampa il numero massimo di missioni,
Anche se non è richiesto, si stampa la sequenza di missioni trovate. Questo messaggio serve a valutare la correttezza della soluzione, in altri termini si vuole vedere ciò che si conta per accertarsi che sia corretto.
Soluzione con il metodo ricorsivo:
Un altro metodo per risolvere il problema delle missioni di Topolino potrebbe nascere dall'osservazione che bisogna determinare tutte le possibili disposizioni delle missioni a gruppi via via decrescenti fino a trovare che un gruppo di missioni si può svolgere.
Per meglio interpretare il procedimento si consiglia di rivedere l'algoritmo per determinare le combinazioni di N elementi a gruppi di k elementi.
