matteo.pata
08-11-2010, 21:00
Ciao ragazzi sono di nuovo qui alle prese con il progetto di algoritmi per l'università.
Avrei bisogno di una grossa mano nello scegliere la struttura + adatta per il progetto che devo implementare in C.
Specifiche:
1 Il problema
Si vuole rivestire un pavimento rettangolare con un mosaico di tasselli e di malta a presa rapida. Ogni tassello ha la stessa grandezza ma `e delimitato da quattro bordi frastagliati di forma (in generale) diversa. I bordi di un tassello possono collimare pi`u o meno bene con i bordi degli altri tasselli. I tasselli
hanno un orientamento predefinito e devono essere collocati con quell’orientamento, a causa della fantasia disegnata nella parte superiore. Quindi ogni tassello ha un bordo Nord, uno Sud, uno Ovest e uno Est. I tasselli inizialmente sono dentro a delle scatole dall’identico contenuto. Queste scatole sono sempre
disponibili in numero sufficiente per terminare il lavoro. Ciascuna scatola contiene un numero prefissato k di tasselli numerati da 1 a k, sempre gli stessi in ogni scatola. Ad esempio, il tassello con numero di serie 3 della prima scatola ha la stessa forma (gli stessi bordi) del tassello numero 3 di tutte le altre scatole. Il numero di ordinamento `e scritto sul retro di ogni tassello, in piccolo. I tasselli possono essere estratti dalle scatole solo in tal ordine, da quello con numero di serie 1 a quello con numero di serie k.
Il pavimento, delimitato dalle quattro pareti, si pu`o immaginare come una griglia regolare di caselle quadrate, ciascuna delle quali dovr`a alla fine del lavoro contenere un tassello o essere riempita di malta. All’inizio del lavoro, ogni casella della griglia `e vuota.
2 Costruzione del mosaico
Ecco come si procede alla costruzione del pavimento. Per cominciare, si apre la prima scatola, e si mette il suo primo tassello nel mezzo del pavimento, nell’orientamento prescritto (i pavimenti hanno una numero dispari di caselle per lato, quindi esiste una casella centrale). Si rovescia il resto del contenuto della scatola in una apposita cesta di lavoro. Si apre
una scatola di riserva, se ne estrae il primo tassello e lo si pone nella cesta, in modo che questa contenga ora tanti tasselli quanti ce ne sono in una scatola. A questo punto, si procede sempre nello stesso modo, fino a quando l’intero pavimento sia completato,
cio`e non vi siano pi`u caselle vuote: si incolla un tassello alla volta sul pavimento, e talvolta, dopo averlo
fatto, si usa la malta liquida per riempire alcune zone del pavimento delimitate da tasselli gi`a posizionati. Ad ogni passaggio, si deve prendere un tassello dalla cesta per incollarlo sul pavimento, sempre accanto ad un tassello gi`a posizionato, in una casella ancora libera adiacente lato a lato a quest’ultimo. La scelta del tassello e della casella viene effettuata in modo da far collimare il pi`u possible il bordo del nuovo tassello con quello del tassello gi`a posizionato (vedi sotto).
Nell’estrarre il tassello dalla cesta di lavoro, lo si rimpiazza immediatamente col prossimo tassello preso dalla scatola di riserva, in modo che durante l’intero lavoro la cesta contenga sempre lo stesso numero di tasselli (tanti quanti ce ne sono in una scatola). Se la scatola di riserva rimane vuota, si apre semplicemente la scatola successiva, che servir`a da nuova scatola di riserva.
Dopo aver posto un tassello, si controlla se il pavimento presenta delle zone completamente delimitate da tasselli gi`a incollati: queste zone vengono subito riempite con la malta a presa rapida. Per “zona completamente delimitata” si intende un qualunque sottoinsieme di caselle vuote ciascuna delle quali sia adiacente lato a lato solo ad altre caselle di questo sottoinsieme oppure a tasselli gi`a incollati (ma non alle pareti che delimitano la stanza). La malta viene versata nella zona (o le zone) fino a riempirla, dopodich`e si indurisce. Le caselle piene di malta indurita non possono pi`u accogliere alcun tassello.
2.1 Bordi che collimano e bordi che non collimano
Come detto, i bordi dei tasselli sono frastagliati. Ognuno dei quattro bordi `e infatti caratterizzato da un certo numero n di dentellature in sequenza (n `e lo stesso per tutti i bordi di tutti i tasselli di un dato problema). Ciascuna dentellatura pu`o essere piatta, oppure rientrante, oppure sporgente. Rientranze (e sporgenze) possono essere profonde (o estroflesse) di una lunghezza variabile. Le rientranze sono descritte da numeri negativi, le sporgenze da numeri positivi: tanto maggiore il modulo del numero tanto pi`u profonda o estroflessa `e la rientranza o la sporgenza; una dentellatura piatta `e descritta dal numero zero.
Le rientranze rappresentate dal numero −k (con k naturale) collimano perfettamente con sporgenze della stessa entit`a, rappresentate dal numero opposto +k, e viceversa. In generale, il mismatch fra due dentellature k1 k2 `e un numero che rappresenta quanto quelle due dentellature sono lontane dal collimare perfettamente. E’ calcolato semplicemente con (k1 + k2)2 . Il mismatch fra un intero bordo e un altro `e la somma dei mismatch delle rispettive dentellature, in ordine.
Un tassello viene descritto da tutte le dentellature che si trovano sui suoi bordi, in ordine orario (n per lato cio`e 4n), a partire da quelle pi`u a Ovest del bordo Nord.
ESEMPIO
http://img683.imageshack.us/img683/9274/immaginebvh.jpg (http://img683.imageshack.us/i/immaginebvh.jpg/)
2.1.2 Scelta del tassello e della casella
Quando si deve scegliere il tassello fra quelli contenuti nella cesta, e il bordo libero a cui attaccarlo, bisogner`a preferire quel tassello e quel bordo libero che ottengano fra di loro un mismatch minore, fra tutte le scelte valide possibili di questo tipo (per “bordo libero” si intende il bordo di un tassello gi`a posizionato adiacente ad una casella ancora vuota). In caso di parit`a fra due o pi`u alternative, si sceglier`a di posizionare il tassello che presenti il numero di serie minore. Se il tassello scelto pu`o essere messo in due caselle diverse con lo stesso valore di mismatch, si scelga la posizione pi`u a Nord delle due, e in caso di ulteriore parit`a, quella pi`u a Est.
Nota: puo succedere che alcune caselle vuote saranno adiacenti a pi`u di un tassello gi`a incollato, cio`e che pi`u bordi liberi siano adiacenti ad una stessa casella vuota. Il criterio di scelta per`o valuta sempre ogni bordo separatamente, e nel sceglierne uno non conta quanto bene o quanto male gli altri bordi liberi collimino col tassello che viene eventualmente posto accanto ad essi. Ad esempio, si consideri la seguente situazione, dove in un minuscolo pavimento 2 × 2 siano stati collocati i tasselli A, B e C in questo modo:
AB
C. Un nuovo tassello D sar`a posizionato nella casella vuota rappresentata dal puntino a condizione che il bordo Ovest di D abbia un mismatch col bordo Est di C minore di quello ottenuto con qualunque altra scelta – e se questo si verifica non conta il mismatch fra il bordo Nord di D e il bordo Sud di B (se il mismatch minore possibile si trovasse fra il bordo Sud di B e il bordo Nord di D, ugualmente il tassello D sar`a posizionato nella casella vuota
– indipendentemente dal valore di mismatch fra il bordo Ovest di D e quello Est di C.)
3 Input e Output
Il file deve prendere dalla riga di comando il nome del file di input. Deve produrre in risposta un file di output, con un nome uguale a quello del file di input, giustapposto alla stringa .pnm. (ad esempio, se prende in input il file test.txt dovr`a produrre in output il file: test.txt.pnm
3.1 Dati in input
L’input consiste in file di testo, in cui il problema viene descritto con una serie di numeri interi (separati da spazi,
caratteri di accapo, etc). Per prima cosa compare la dimensione orizzontale e verticale del pavimento (sempre due numeri dispari). Segue il numero di tasselli contenuti in ogni scatola, e il numero di dentellature che compaiono in ognuno dei quattro lati di ogni tassello. Dopodiche’ compare la descrizione di ciascun tassello, uno dopo l’altro. La descrizione di un tassello consiste nella sequenza dei i valori numerici che rappresentano ciascuna dentellatura di ciascun lato (nell’ordine sopra descritto).
3.2 Dati in output
Il file di output deve consistere in un file di testo. All’inizio di questo file, nella sua prima riga, deve comparire la stringa di due caratteri “P1”. Nella seconda riga, devono comparire la larghezza e la lunghezza del pavimento, separate da uno spazio.
Di seguito, deve comparire la descrizione di come appare il pavimento alla fine del lavoro, a partire dalla fila pi`u a Nord del pavimento, fino alla riga piu’ a Sud, con una riga di testo per ogni fila. Ogni fila viene descritta da un numero binario per ogni casella, separati da uno spazio: 0 se la casella contiene un tassello, 1 se contiene malta.
3.3 Altri vincoli
La correttezza delle soluzioni `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).
La sfida consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze pi`u complesse possibili. Quali delle istanze proposte sar`a possibile risolvere?
4 Dimensioni e natura delle tipiche istanze del problema
I pavimenti possono essere molto grandi (o equivalentemente, i tasselli molto piccoli). Pavimenti composti di migliaia di tasselli per lato non sono incomuni. Anche il numero di tasselli diversi presenti nelle scatole pu`o essere
assai grande. Il numero di dentellature per ogni lato di tassello e’ di solito contenuto.
Grazia a tutti in anticipo.
Spero che qualcuno mi dia una mano....:help: :help: :help: :help:
Avrei bisogno di una grossa mano nello scegliere la struttura + adatta per il progetto che devo implementare in C.
Specifiche:
1 Il problema
Si vuole rivestire un pavimento rettangolare con un mosaico di tasselli e di malta a presa rapida. Ogni tassello ha la stessa grandezza ma `e delimitato da quattro bordi frastagliati di forma (in generale) diversa. I bordi di un tassello possono collimare pi`u o meno bene con i bordi degli altri tasselli. I tasselli
hanno un orientamento predefinito e devono essere collocati con quell’orientamento, a causa della fantasia disegnata nella parte superiore. Quindi ogni tassello ha un bordo Nord, uno Sud, uno Ovest e uno Est. I tasselli inizialmente sono dentro a delle scatole dall’identico contenuto. Queste scatole sono sempre
disponibili in numero sufficiente per terminare il lavoro. Ciascuna scatola contiene un numero prefissato k di tasselli numerati da 1 a k, sempre gli stessi in ogni scatola. Ad esempio, il tassello con numero di serie 3 della prima scatola ha la stessa forma (gli stessi bordi) del tassello numero 3 di tutte le altre scatole. Il numero di ordinamento `e scritto sul retro di ogni tassello, in piccolo. I tasselli possono essere estratti dalle scatole solo in tal ordine, da quello con numero di serie 1 a quello con numero di serie k.
Il pavimento, delimitato dalle quattro pareti, si pu`o immaginare come una griglia regolare di caselle quadrate, ciascuna delle quali dovr`a alla fine del lavoro contenere un tassello o essere riempita di malta. All’inizio del lavoro, ogni casella della griglia `e vuota.
2 Costruzione del mosaico
Ecco come si procede alla costruzione del pavimento. Per cominciare, si apre la prima scatola, e si mette il suo primo tassello nel mezzo del pavimento, nell’orientamento prescritto (i pavimenti hanno una numero dispari di caselle per lato, quindi esiste una casella centrale). Si rovescia il resto del contenuto della scatola in una apposita cesta di lavoro. Si apre
una scatola di riserva, se ne estrae il primo tassello e lo si pone nella cesta, in modo che questa contenga ora tanti tasselli quanti ce ne sono in una scatola. A questo punto, si procede sempre nello stesso modo, fino a quando l’intero pavimento sia completato,
cio`e non vi siano pi`u caselle vuote: si incolla un tassello alla volta sul pavimento, e talvolta, dopo averlo
fatto, si usa la malta liquida per riempire alcune zone del pavimento delimitate da tasselli gi`a posizionati. Ad ogni passaggio, si deve prendere un tassello dalla cesta per incollarlo sul pavimento, sempre accanto ad un tassello gi`a posizionato, in una casella ancora libera adiacente lato a lato a quest’ultimo. La scelta del tassello e della casella viene effettuata in modo da far collimare il pi`u possible il bordo del nuovo tassello con quello del tassello gi`a posizionato (vedi sotto).
Nell’estrarre il tassello dalla cesta di lavoro, lo si rimpiazza immediatamente col prossimo tassello preso dalla scatola di riserva, in modo che durante l’intero lavoro la cesta contenga sempre lo stesso numero di tasselli (tanti quanti ce ne sono in una scatola). Se la scatola di riserva rimane vuota, si apre semplicemente la scatola successiva, che servir`a da nuova scatola di riserva.
Dopo aver posto un tassello, si controlla se il pavimento presenta delle zone completamente delimitate da tasselli gi`a incollati: queste zone vengono subito riempite con la malta a presa rapida. Per “zona completamente delimitata” si intende un qualunque sottoinsieme di caselle vuote ciascuna delle quali sia adiacente lato a lato solo ad altre caselle di questo sottoinsieme oppure a tasselli gi`a incollati (ma non alle pareti che delimitano la stanza). La malta viene versata nella zona (o le zone) fino a riempirla, dopodich`e si indurisce. Le caselle piene di malta indurita non possono pi`u accogliere alcun tassello.
2.1 Bordi che collimano e bordi che non collimano
Come detto, i bordi dei tasselli sono frastagliati. Ognuno dei quattro bordi `e infatti caratterizzato da un certo numero n di dentellature in sequenza (n `e lo stesso per tutti i bordi di tutti i tasselli di un dato problema). Ciascuna dentellatura pu`o essere piatta, oppure rientrante, oppure sporgente. Rientranze (e sporgenze) possono essere profonde (o estroflesse) di una lunghezza variabile. Le rientranze sono descritte da numeri negativi, le sporgenze da numeri positivi: tanto maggiore il modulo del numero tanto pi`u profonda o estroflessa `e la rientranza o la sporgenza; una dentellatura piatta `e descritta dal numero zero.
Le rientranze rappresentate dal numero −k (con k naturale) collimano perfettamente con sporgenze della stessa entit`a, rappresentate dal numero opposto +k, e viceversa. In generale, il mismatch fra due dentellature k1 k2 `e un numero che rappresenta quanto quelle due dentellature sono lontane dal collimare perfettamente. E’ calcolato semplicemente con (k1 + k2)2 . Il mismatch fra un intero bordo e un altro `e la somma dei mismatch delle rispettive dentellature, in ordine.
Un tassello viene descritto da tutte le dentellature che si trovano sui suoi bordi, in ordine orario (n per lato cio`e 4n), a partire da quelle pi`u a Ovest del bordo Nord.
ESEMPIO
http://img683.imageshack.us/img683/9274/immaginebvh.jpg (http://img683.imageshack.us/i/immaginebvh.jpg/)
2.1.2 Scelta del tassello e della casella
Quando si deve scegliere il tassello fra quelli contenuti nella cesta, e il bordo libero a cui attaccarlo, bisogner`a preferire quel tassello e quel bordo libero che ottengano fra di loro un mismatch minore, fra tutte le scelte valide possibili di questo tipo (per “bordo libero” si intende il bordo di un tassello gi`a posizionato adiacente ad una casella ancora vuota). In caso di parit`a fra due o pi`u alternative, si sceglier`a di posizionare il tassello che presenti il numero di serie minore. Se il tassello scelto pu`o essere messo in due caselle diverse con lo stesso valore di mismatch, si scelga la posizione pi`u a Nord delle due, e in caso di ulteriore parit`a, quella pi`u a Est.
Nota: puo succedere che alcune caselle vuote saranno adiacenti a pi`u di un tassello gi`a incollato, cio`e che pi`u bordi liberi siano adiacenti ad una stessa casella vuota. Il criterio di scelta per`o valuta sempre ogni bordo separatamente, e nel sceglierne uno non conta quanto bene o quanto male gli altri bordi liberi collimino col tassello che viene eventualmente posto accanto ad essi. Ad esempio, si consideri la seguente situazione, dove in un minuscolo pavimento 2 × 2 siano stati collocati i tasselli A, B e C in questo modo:
AB
C. Un nuovo tassello D sar`a posizionato nella casella vuota rappresentata dal puntino a condizione che il bordo Ovest di D abbia un mismatch col bordo Est di C minore di quello ottenuto con qualunque altra scelta – e se questo si verifica non conta il mismatch fra il bordo Nord di D e il bordo Sud di B (se il mismatch minore possibile si trovasse fra il bordo Sud di B e il bordo Nord di D, ugualmente il tassello D sar`a posizionato nella casella vuota
– indipendentemente dal valore di mismatch fra il bordo Ovest di D e quello Est di C.)
3 Input e Output
Il file deve prendere dalla riga di comando il nome del file di input. Deve produrre in risposta un file di output, con un nome uguale a quello del file di input, giustapposto alla stringa .pnm. (ad esempio, se prende in input il file test.txt dovr`a produrre in output il file: test.txt.pnm
3.1 Dati in input
L’input consiste in file di testo, in cui il problema viene descritto con una serie di numeri interi (separati da spazi,
caratteri di accapo, etc). Per prima cosa compare la dimensione orizzontale e verticale del pavimento (sempre due numeri dispari). Segue il numero di tasselli contenuti in ogni scatola, e il numero di dentellature che compaiono in ognuno dei quattro lati di ogni tassello. Dopodiche’ compare la descrizione di ciascun tassello, uno dopo l’altro. La descrizione di un tassello consiste nella sequenza dei i valori numerici che rappresentano ciascuna dentellatura di ciascun lato (nell’ordine sopra descritto).
3.2 Dati in output
Il file di output deve consistere in un file di testo. All’inizio di questo file, nella sua prima riga, deve comparire la stringa di due caratteri “P1”. Nella seconda riga, devono comparire la larghezza e la lunghezza del pavimento, separate da uno spazio.
Di seguito, deve comparire la descrizione di come appare il pavimento alla fine del lavoro, a partire dalla fila pi`u a Nord del pavimento, fino alla riga piu’ a Sud, con una riga di testo per ogni fila. Ogni fila viene descritta da un numero binario per ogni casella, separati da uno spazio: 0 se la casella contiene un tassello, 1 se contiene malta.
3.3 Altri vincoli
La correttezza delle soluzioni `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).
La sfida consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze pi`u complesse possibili. Quali delle istanze proposte sar`a possibile risolvere?
4 Dimensioni e natura delle tipiche istanze del problema
I pavimenti possono essere molto grandi (o equivalentemente, i tasselli molto piccoli). Pavimenti composti di migliaia di tasselli per lato non sono incomuni. Anche il numero di tasselli diversi presenti nelle scatole pu`o essere
assai grande. Il numero di dentellature per ogni lato di tassello e’ di solito contenuto.
Grazia a tutti in anticipo.
Spero che qualcuno mi dia una mano....:help: :help: :help: :help: