Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Perdonatemi se ho messo un titolo tanto idiota, ma è la verità: non so che titolo dare a un thread che parte da una domanda come quella che sto per fare.
Sto (provando a) realizzare un giochino che consiste nel raggruppare caselle di colore diverso in "aree" di colore uniforme, per cui dovrei a un certo punto verificare quanti e quali caselle sono contenute in ciascuna area di colore uniforme (ad esempio, nell'immagine in coda è mostrata la situazione dello schema in un certo momento d'una ipotetica partita).
I numeri corrispondono alla quantità degli spostamenti che il giocatore ha posto in essere per spostare le varie caselle dalla posizione di partenza a quella corrente, e in base a quei numeri dovrò in qualche modo (che non ho ancora pensato) calcolare il punteggio.
Per il momento, non riesco a farmi venire in mente un metodo SEMPLICE (anche a costo di rimetterci qualcosa in termini di prestazioni, che non sono importanti) e COMPRENSIBILE per rilevare le aree di colore uniforme e poterle poi analizzare in termini di dimensioni (quante caselle) e valore (con che punteggio). Vorrei rilevare solo le aree costituite da una quantità minima arbitraria di caselle in su, ad esempio 5. Nello schema d'esempio si possono vedere, per dire, un'area rossa di cinque caselle, piuttosto compatta, una gialla molto articolata con 19 caselle, due aree arancioni da 7 caselle ciascuna, alcune caselle "annullate" per aver esaurito le mosse a disposizione e così via.
Pensavo di generare dei vettori di strutture che descrivano le caselle "scelte", uno per ogni area, ma fatico a capire come individuare le caselle da inserirci.
E' possibile una soluzione iterativa o dovrò ricorrere a una ricorsiva (le ricorsioni ancora mi confondono)?
Che tipo di algoritmo posso provare a seguire? Fino ad ora mi son venute in mente solo soluzioni cervellotiche che temo siano più stupide del dovuto.
Non è un problema che dia luogo a questioni di vita o di morte, anzi, non è proprio un problema. Diciamo piuttosto che è un rompicapo che mi piacerebbe riuscire a risolvere ma rispetto al quale sono bloccato.
Ultima modifica effettuata da AldoBaldo il 26/08/2017 alle 15:21
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Postato originariamente da AldoBaldo: (le ricorsioni ancora mi confondono)
Mettiti sotto a fare esercizi perché le funzioni ricorsive sono fondamentali nello sviluppo di algoritmi e quindi non andrebbero assolutamente lasciate come buco formativo.
L'algoritmo più semplice è quello a ricerca in un labirinto mediante albero, ora non ricordo il nome ma il concetto è questo.
Prendi una cella e verifichi che le celle adiacenti siano valide per il tuo processo di ricerca(stesso colore) per ognuna di queste celle riesegui l'algoritmo.
Importante è tenere traccia delle celle già indicizzate e del numero di celle valide trovate(semplicemente il numero di chiamate della funzione). Ad ogni iterazione ti puoi trovare davanti a due casi: non ci sono caselle adiacenti dello stesso non visitate quindi la funzione termina, oppure c'è almeno una una cella dello stesso colore non visitata e allora come detto in precedenza rilanci la funzione su quelle celle.
Può andare?
E' proprio quel che ho già provato a fare, anche se con formulazione iterativa anziché ricorsiva, e mi viene fuori una cosa piuttosto cervellotica. Diciamo "articolata", tò. Speravo potessero esistere soluzioni più lineari ma, se mi dici che non ne esistono, insisto a "spaccarmi" la testa su quella finché riesco. E ci riesco, vedrai! ("l'ottimismo è il sale della vita") Pensi che una soluzione ricorsiva sarebbe migliore di una iterativa? Giusto per sapere come mi conviene incamminanrmi.
Comunque mi hai già dato un bell'indirizzo segnalandomi l'affinità con la ricerca d'un percorso in un labirinto: ricordo d'aver trovato fior di articoli sul tema, quindi andare a rileggermeli potrebbe aiutarmi.
Ultima modifica effettuata da AldoBaldo il 26/08/2017 alle 15:46
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Speravo potessero esistere soluzioni più lineari ma, se mi dici che non ne esistono,
Io non ho detto che non esistono, le funzioni ricorsive hanno sempre una rappresentazione iterativa, ma si perde la generalità della soluzione e si complica l'algoritmo con soli effetti negativi.
Le funzioni ricorsive sono importanti e sono un tassello indispensabile nel bagaglio formativo di un programmatore. Ostinarsi a non imparare questa tecnica è come lo studente di modellistica che continua imperterrito a non volere imparare il calcolo differenziale.
Grazie Lumo! Da una primissima e superficiale occhiata credo proprio che quello che mi indichi sia quel che mi serve. Certo, ora si tratta di capirlo e vedere come usarlo, e questa è tutta un'altra faccenda. Ci provo questa sera stessa!!! Anzi, ora.
Ah, aggiungo che da solo non l'avrei mai scoperto, non sapendo cosa cercare.
Roby, non è che la ricorsione non so cos'è, è che ancora mi confonde, ovvero per usarla devo spaccarmi il cervello. In alcuni casi semplici l'ho anche usata (spaccandomi, appunto, il cervello). Dai e dai, imparerò ben, no? Il fatto è che già non sono sicuro di capire bene il procedimento, ancora che ci metto il "carico da undici" camminando sulle sabbie mobili d'un terreno sul quale mi sento instabile... ehm...
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Allora... per prima cosa un invito alla clemenza, perché sto sondando un terreno del quale non so nulla, e lo faccio poggiando su basi non certo solide. Diciamo che il mio è un gesto di coraggio.
Ho letto un po' di cose sulla questione dei grafi e di come organizzare la loro analisi. M'è sembrato di capire che un primo passo che occorre fare per ottenere quel che mi serve (ma potrei sbagliarmi) consiste nel realizzare una "matrice d'adiacenza" da usare poi nell'algoritmo d'analisi. Dunque ho cercato di informarmi su cosa fosse questa sconosciuta "matrice d'adiacenza" e ne è emerso che è una specie di tabellina. Nella sua forma più semplice (che credo sia quella che mi serve) l'ho ottenuta così:
Codice sorgente - presumibilmente C++
#include <stdio.h>
#include <stdlib.h>
#define QR 3 // quantita' delle righe (nella matrice dei colori)
#define QC 4 // quantita' delle colonne (nella matrice dei colori)
char mc[QR][QC]={// mc = matrice dei colori
{'G','G','B','B'},
{'R','G','B','R'},
{'R','B','B','B'},
};
int ma[QR*QC][QR*QC]={{0},{0}};// ma = matrice d'adiacenza
void esplora_adiacenze(int ra, int rc, int cc );
void print_mc(void);
void print_ma(void);
int main(){
int r, c;
// analizza uno per uno i caratteri presenti nella matrice dei
// colori, al fine di compilare una matrice delle adiacenze
Per non perderci troppo tempo ho temporaneamente usato delle variabili globali, ma non è importante. Quel che vorrei sapere è: è corretto quel che ho fatto? Serve davvero o è un "vicolo cieco"?
P.S. print_mc() e print_ma() sono irrilevanti nel contesto del discorso: mi son servite solo per vedere cosa stavo facendo.
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Il codice non riesco a leggerlo, ti dico che con la matrice di adiacenza puoi di sicuro combinare qualcosa, anche se probabilmente qui non serve.
La matrice di adiacenza si usa quando vuoi rispondere in modo rapido alla domanda "il nodo X e Y sono connessi?".
Inoltre si usano di solito solo quando il grafo ha un numero di nodi prefissato, altrimenti devi aumentarne la dimensione, copiare tutto ecc... nel caso di grafi dinamici si usa infatti la lista di adiacenza di solito.
Detto questo, non ti serve a molto la matrice di adiacenza perché dovresti costruirla, ma per costruirla devi definire un concetto di connessione sulla tua griglia, e inizialmente questo sarà: ogni cella ha come vicini quelli che stanno sopra sotto, a sinistra a destra (o una cosa simile).
Quindi verrebbe fuori una matrice di adiacenza abbastanza scontata.
Ti consiglio invece di capire l'algoritmo per trovare le componenti connesse e dopo applicarlo direttamente sulla griglia, senza costruire esplicitamente il grafo associato: alla fine è esattamente quello che ti ha descritto Roby.