mistergks
06-03-2012, 19:18
Ho trovato un esercizio un pò complicato per me!
TRACCIA (C'è anche un disegno di esempio...lo allego come pdf)
Si consideri il seguente rompicapo illustrato dalle figure nell allegato (che riportano, rispettivamente, una possibile istanza del gioco e la sua soluzione). Si ha una griglia quadrata NxN che rappresenta la pianta della city di una moderna città. In ogni casella è presente un edificio con un certo numero di piani; in ciascuna riga e colonna gli edifici sono tutti di altezza diversa: ad esempio, in una griglia 4x4 gli edifici in ogni riga o colonna sono di 10, 20, 30 e 40 piani (1-2-3-4, per semplicità); in una griglia 5x5 ci sono anche 50 piani (5, per semplicità); e così via. I numeri nelle caselle sui bordi grigi indicano quante costruzioni può vedere un osservatore da quella casella lungo la stessa riga o colonna. Ad esempio, nello schema riportato in figura, il “2” posizionato sul bordo sinistro della riga evidenziata, indica che un osservatore in quella posizione, guardando da sinistra verso destra, vedrebbe esattamente due grattacieli; il “3” a destra della stessa riga indica che un osservatore che guardasse la riga da destra verso sinistra ne vedrebbe esattamente tre. Infatti, guardando la corrispondente riga nella soluzione, abbiamo da sinistra a destra “3-4-2-1”: quindi, guardando da sinistra verso destra si vedono solo gli edifici di 30 e 40 piani (3-4), che nascondono quelli più bassi (2-1); guardando da destra a sinistra, abbiamo “1-2-4-3”, e gli edifici visibili sono quelli di 10, 20 e 40 piani (1-2-4), mentre quello di 30 piani (3) è nascosto alla vista da quello più alto (4). Naturalmente, gli indizi valgono nello stesso modo per ogni riga, e similmente per ogni colonna.
Si scriva in C++ una funzione che, ricevuta in input una soluzione candidata, restituisca “true” se la soluzione è ammissibile (cioè rispetta tutti gli indizi di riga e colonna), “false” altrimenti.
SUGGERIMENTO: La griglia (corrispondente alla parte “bianca” in figura) può essere rappresentata da una matrice di interi senza segno di dimensione NxN; gli indizi per righe e colonna (corrispondenti alla parte “grigia” in figura), invece, possono essere rappresentati da 2 matrici di interi senza segno: int indiziRiga[N][2], indiziColonna[N][2]. Ad esempio, nella matrice “indiziRiga”, per ogni riga “i”, l’elemento “indiziRiga[i][1]” potrebbe riportare l’indizio da sinistra a destra, e l’elemento “indiziRiga[i][2]” potrebbe riportare l’indizio da destra a sinistra; similmente si può intendere per gli indizi di colonna.
Oltre al fatto che ci abbia messo una vita per capire quello che chiede.... non sono riuscito a scrivere nulla!! Ho sempre scritto il mio codice nei post...ma questa volta non so da dove iniziare.
Infatti ho deciso di postare questa mia richiesta di aiuto non per chiedere la soluzione già pronta...ma per cercare qualcuno che mi aiuti a ragionare... e permettermi di iniziare a scrivere questa funzione:doh:
N.B.: Questa funzione non deve risolvere il gioco...ma deve solo verificare che una data soluzione sia corretta!
Allora... io avrei pensato a questa soluzione:
faccio due matrici: indiziRiga e indiziColonna dove vengono messi gli indizi
poi mi scansiono queste due matrici (non insieme ovviamente)e controllo che le condizioni siano verificate. cioè ad esempio:
se scansiono indiziRiga[0][0] trovo il numero 3... quindi in quella riga della matrice alla posizione 2 deve esserci un numero=dimensione matrice (in questo caso 4...perchè la matrice è 4x4)...
TRACCIA (C'è anche un disegno di esempio...lo allego come pdf)
Si consideri il seguente rompicapo illustrato dalle figure nell allegato (che riportano, rispettivamente, una possibile istanza del gioco e la sua soluzione). Si ha una griglia quadrata NxN che rappresenta la pianta della city di una moderna città. In ogni casella è presente un edificio con un certo numero di piani; in ciascuna riga e colonna gli edifici sono tutti di altezza diversa: ad esempio, in una griglia 4x4 gli edifici in ogni riga o colonna sono di 10, 20, 30 e 40 piani (1-2-3-4, per semplicità); in una griglia 5x5 ci sono anche 50 piani (5, per semplicità); e così via. I numeri nelle caselle sui bordi grigi indicano quante costruzioni può vedere un osservatore da quella casella lungo la stessa riga o colonna. Ad esempio, nello schema riportato in figura, il “2” posizionato sul bordo sinistro della riga evidenziata, indica che un osservatore in quella posizione, guardando da sinistra verso destra, vedrebbe esattamente due grattacieli; il “3” a destra della stessa riga indica che un osservatore che guardasse la riga da destra verso sinistra ne vedrebbe esattamente tre. Infatti, guardando la corrispondente riga nella soluzione, abbiamo da sinistra a destra “3-4-2-1”: quindi, guardando da sinistra verso destra si vedono solo gli edifici di 30 e 40 piani (3-4), che nascondono quelli più bassi (2-1); guardando da destra a sinistra, abbiamo “1-2-4-3”, e gli edifici visibili sono quelli di 10, 20 e 40 piani (1-2-4), mentre quello di 30 piani (3) è nascosto alla vista da quello più alto (4). Naturalmente, gli indizi valgono nello stesso modo per ogni riga, e similmente per ogni colonna.
Si scriva in C++ una funzione che, ricevuta in input una soluzione candidata, restituisca “true” se la soluzione è ammissibile (cioè rispetta tutti gli indizi di riga e colonna), “false” altrimenti.
SUGGERIMENTO: La griglia (corrispondente alla parte “bianca” in figura) può essere rappresentata da una matrice di interi senza segno di dimensione NxN; gli indizi per righe e colonna (corrispondenti alla parte “grigia” in figura), invece, possono essere rappresentati da 2 matrici di interi senza segno: int indiziRiga[N][2], indiziColonna[N][2]. Ad esempio, nella matrice “indiziRiga”, per ogni riga “i”, l’elemento “indiziRiga[i][1]” potrebbe riportare l’indizio da sinistra a destra, e l’elemento “indiziRiga[i][2]” potrebbe riportare l’indizio da destra a sinistra; similmente si può intendere per gli indizi di colonna.
Oltre al fatto che ci abbia messo una vita per capire quello che chiede.... non sono riuscito a scrivere nulla!! Ho sempre scritto il mio codice nei post...ma questa volta non so da dove iniziare.
Infatti ho deciso di postare questa mia richiesta di aiuto non per chiedere la soluzione già pronta...ma per cercare qualcuno che mi aiuti a ragionare... e permettermi di iniziare a scrivere questa funzione:doh:
N.B.: Questa funzione non deve risolvere il gioco...ma deve solo verificare che una data soluzione sia corretta!
Allora... io avrei pensato a questa soluzione:
faccio due matrici: indiziRiga e indiziColonna dove vengono messi gli indizi
poi mi scansiono queste due matrici (non insieme ovviamente)e controllo che le condizioni siano verificate. cioè ad esempio:
se scansiono indiziRiga[0][0] trovo il numero 3... quindi in quella riga della matrice alla posizione 2 deve esserci un numero=dimensione matrice (in questo caso 4...perchè la matrice è 4x4)...