Algoritmi e Programmazione Avanzata
Compito di programmazione – 13 maggio 2008
Tempo: 90 minuti, è possibile consultare libri o appunti.
Sia data una sequenza X di massimo N caratteri immessa dall'utente tramite la tastiera, ed un vettore di stringhe D composto da k parole lette da file. Il file è costituito da una prima riga contentente un numero intero che rappresenta il numero di parole contenute nel file. Seguono una per riga le k parole.
Si realizzi un programma in linguaggio C che utilizzi la ricorsione per determinare se esiste una decomposizione di X in parole distinte appartenenti a D (le parole di D possono cioè essere usate una ed una sola volta).
Ad esempio, per X = abracadabra e D = { w1=”ab”, w2=”abra”, w3=”d”, w4=”ca”, w5=”abra” }, allora X sarà composta da w2w4w3w5 e la decomposizione esiste, mentre per X = abracadabrabra tale decomposizione non esiste.
Nella versione sviluppata in aula si trascuri la lettura del file di dati e si ipotizzi che questi siano già presenti in memoria in una struttura dati che dovrà essere opportunamente definita.
N.B. Allo studente è richiesto di consegnare una copia dell’elaborato scritto al termine della presente prova d’esame. Tale elaborato scritto verrà valutato quando lo studente ne avrà effettuato l'auto-correzione e provveduto ad inviare al docente – via email: servetti@polito.it – il programma così riveduto e corretto, con l'aggiunta della lettura dei dati da file, entro il 27.05.2008, insieme a:
– il codice prodotto in aula e trascritto al computer in un file .c
– una relazione con il codice sorgente del programma funzionante correttamente su cui vengono evidenziate (come per la gestione delle revisioni del programma Word) le differenze rispetto alla versione redatta in classe (in rosso il codice aggiunto, barrato il codice cancellato) corredato da una breve descrizione della struttura del programma e dalle motivazioni per le modifiche apportate.
Nella mail specificare come oggetto la sigla del corso ed il proprio numero di matricola, nella forma: [APA-TO + matricola].