Algoritmi e Programmazione Avanzata
Compito di programmazione – 14 Maggio 2007
Tempo: 90 minuti, è possibile consultare libri o appunti.
Si scriva un programma in linguaggio C che risolva il seguente problema.
Sia dato un diagramma come in figura dove sono presenti le cifre, non ripetute, da 1 a 9 incluse.
Identificare tutte le disposizioni di tali cifre che soddisfano il seguente vincolo, che cioè il numero nella seconda riga è pari al doppio del numero nella prima riga, e che il numero nella terza riga è tre volte il numero nella prima riga.
1 9 2
3 8 4
5 7 6
Soluzione di esempio indicante le possibili combinazioni, oltre a quella indicata precedentemente:
2 1 9
4 3 8
6 5 7
2 7 3
5 4 6
8 1 9
3 2 7
6 5 4
9 8 1
NOTE
– La soluzione deve essere implementata tramite un algoritmo ricorsivo e deve prescindere dall'effettiva dimensione della tabella (nota comunque a priori).
– L'algoritmo deve cercare di ridurre il numero di combinazioni da testare imponendo dei vincoli opportuni nella composizione dei numeri di ciascuna riga. Cioè, componendo il quadrato dall'alto verso il basso, se il numero nella seconda riga non è il doppio del numero nella prima riga, non si devono completare e testare le varie combinazioni della terza riga.
N.B. Allo studente è richiesto di consegnare una copia dell’elaborato scritto al termine della presente prova d’esame. Affinché lo scritto venga valutato lo studente dovrà realizzare su PC il programma funzionante ed inviare al docente (servetti@polito.it) il codice sorgente [ ENTRO il 28.05.2007 ] corredato da una breve relazione che illustri le eventuali modifiche apportate rispetto alla versione redatta in sede d’esame. Nella mail specificare come oggetto la sigla del corso ed il proprio numero di matricola, nella forma: [APA-TO + matricola]. La data ed il luogo per la registrazione del voto verrà comunicata via email.