Fondamenti di Informatica Modulo A - Compito B

Prof. Marco Gavanelli

19 feb 2013

Esercizio (punti 14)

Un file binario  lastra.bin contiene le istruzioni per tagliare una lastra di vetro. La lastra deve essere tagliata tramite una serie di tagli rettilinei, per produrre dei pezzi finiti. La macchina può effettuare esclusivamente tagli verticali e orizzontali. Ogni taglio è un segmento, descritto da:

• identificatore del segmento (int), univoco (nel file non compaiono due segmenti con lo stesso identificatore)
• coordinate degli estremi del segmento: X1, Y1, X2, Y2: (int)

Il file contiene al più 100 tagli; per semplificare l'esercizio, si sappia che in ogni taglio che si trova nel file si ha che X1 ≤ X2 e Y1 ≤ Y2.

Ad esempio, se il file lastra.bin contiene:

allora i tagli da effettuare saranno quelli in figura:

Si desidera sapere la lunghezza totale dei tagli verticali e quella dei tagli orizzontali. Nell'esempio sopra, i tagli verticali sono il taglio 1 (che ha lunghezza 5), il taglio 3 (che ha lunghezza 5) e il taglio 5 (che ha lunghezza 4); la lunghezza totale dei tagli verticali è quindi 14. I tagli orizzontali sono 2 (lunghezza 4) e 4 (lunghezza 4), per una lunghezza totale di 8.

Si usi il seguente algoritmo:

1. nel main, si invochi una procedura o funzione di lettura (punto 2), una di elaborazione (punto 3) e infine si stampino i risultati (nel main)
2. Si legga il file lastra.bin e se ne porti il contenuto in un opportuno array di strutture. Si mostri a video l'array.
3. la procedura o funzione di elaborazione prende come parametro l'array creato al punto 2 (più eventualmente altri parametri) e fornisce al main le due somme di lunghezze descritte in precedenza.

Facoltativo (punti 6)

La macchina, una volta iniziato un taglio, non è in grado di fermarsi, ma deve arrivare in fondo alla lastra che si sta tagliando. I tagli indicati nel file lastra.bin rispettano questa caratteristica della macchina: non viene mai dato un file lastra.bin in cui è impossibile realizzare i tagli senza fermarsi.

Tuttavia, i tagli vanno effettuati in un ordine: nell'esempio in figura non è possibile effettuare il taglio 2 prima che siano stati effettuati i tagli 1 e 3; una volta effettuati i tagli 1 e 3, si hanno 3 lastre separate:

• quella a sinistra del taglio 1
• quella a destra del taglio 3
• quella compresa fra i due tagli

La terza lastra a questo punto può essere tagliata in orizzontale da una parte all'altra, come stabilito nel taglio 2.

Si aggiunga una procedura o funzione che calcola, per ogni taglio, quali sono i 2 tagli da effettuare in precedenza. I nuovi tagli vanno inseriti in un nuovo array di strutture che, oltre ai dati contenuti nell'array precedente, per ogni taglio contiene gli identificatori dei due tagli da effettuare in precedenza. Qualora un taglio non richieda altri tagli in precedenza, bisogna inserire come precedenza il taglio 0.

Nel main , si stampi poi quest'ultimo array.

Nell'esempio in figura, il programma dovrà stampare:

taglio 1 (2,0) (2,5) precedenti: 0 0
taglio 2 (2,1) (6,1)  precedenti: 1 3
taglio 3 (6,0) (6,5)  precedenti: 0 0
taglio 4 (6,4) (10,4) precedenti: 3 0
taglio 5 (8,0) (8,4)  precedenti: 0 4