Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- fisica:informatica:201819:esercitazioni:esercitazione12sel [25/03/2019 alle 14:22 (6 anni fa)] – creata Susanna Pelagatti
+++ fisica:informatica:201819:esercitazioni:esercitazione12sel [01/04/2019 alle 13:58 (6 anni fa)] (versione attuale) – [Esercizio 4: Problema della corrispondenza di Post] Alessio Conte
@@ Linea 1: / Linea 1: @@
 ====== Esercizi strutture, stringhe e file ======
@@ Linea 68: / Linea 70: @@
 //Approfondimenti//: provare ad utilizzare la funzione di libreria ''getopt'' (''man 3 getopt'') per eseguire l'analisi (//parsing//) della linea di comando. Questa funzione e' realmente utilizzata per analizzare la linea di comando dei comandi di shell che utilizziamo normalmente.
+===== Esercizio 4: Problema della corrispondenza di Post =====
+Sia P un array di 'tessere di domino' P[1] .... P[N-1]. Ogni tessera a = P[i] e' una struct che contiene due campi di tipo stringa (char *), top e bottom:
+<code c>
+typedef struct tessera {
+	char * top;
+	char * bottom;
+} tessera_t;
+</code>
+Un 'match' e' una sequenza di tessere a_1, a_2, ... a_k (possibilmente con ripetizioni di tessere) tale che la sequenza "a_1.top a_2.top ... a_k.top" ottenuta concatenando tutti i campi top sia uguale alla sequenza "a_1.bottom a_2.bottom ... a_k.bottom" ottenuta concatenando tutti i bottom.
+Esempio:
+<code c>
+P[0] = { "c" , "ci" };
+P[1] = { "i" , "a" };
+P[2] = { "ao" , "o" };
+P[3] = { "a" , "a" };
+</code>
+P[0],P[1],P[2] e' un match: concatenando tutti i campi top otteniamo "c","i","ao" = "ciao", e ugualmente ottenamo "ci","a","o" = "ciao" concatenando tutti i campi bottom.
+Anche P[0],P[1],P[3],P[3],P[3],P[3],P[2] e' un match! otteniamo "c","i","a","a","a","a","ao" (top) e "ci","a","a","a","a","a","o" (bottom).
+Invece, se l'array e':
+<code c>
+P[0] = { "a" , "1" };
+P[1] = { "b" , "2" };
+</code>
+Chiaramente non esiste alcun match.
+Si scriva una funzione ''int post(tessera_t * P, int n)'' che prenda in input un array di n ''tessera_t'', e ritorni 1 se e' possibile trovare un qualsiasi 'match' in P, o 0 altrimenti.
+Suggerimento: prima di cominciare a scrivere codice, ragionare su come si puo' fare per stabilire se esiste o meno un match.