Esercizio 1 Scrivere un programma che legga da tastiera un intero positivo n e successivamente una sequenza di n valori interi. Il programma deve allocare dinamicamente un vettore A di lunghezza n ed inserire gli elementi letti nel vettore. Il programma deve restituire la lunghezza del piu' lungo sottovettore palindromo di A. Si dovra' modificare QUESTO file definendo il corpo della funzione max_len_pal(). E' possibile comunque introdurre eventuali funzioni ausiliarie. Lo scheletro del programma fornito si occupa della lettura di n, dell'allocazione del vettore A e dell'inserimento dei valori nel vettore stesso. Si deve modificare il programma intervenendo sul corpo della funzione max_len_pal(), che dovra' restituire la lunghezza del piu' lungo sottovettore palindromo di A. Si possono aggiungere funzioni ausiliarie, ma non si deve assolutamente modificare il codice del main. La stampa del risultato non deve essere implementata, essendo gia' presente nello scheletro del programma fornito. Il la funzione max_len_pal ha il seguente prototipo: int max_len_pal(int *A, int n) La funzione restituisce la lunghezza del piu' lungo sottovettore palindromo di A. Note: Dato un vettore A, un sottovettore di A e' un vettore formato da elementi contingui di A. Ad esempio, se A =[1,2,3,4] allora B=[2,3] e' un sottovettore di A, mentre C = [1,3,4] non e' un sottovettore di A. Essendo un vettore di lunghezza 1 palindromo, per ogni vettore A la funzione restituisce un valore >= 1. Esempio 1: Si inseriscono i valori 5 6 9 1 9 9 Si ha n = 5, A = [6,9,1,9,9]. Il sottovettore [9,1,9] e' il piu' lungo sottovettore palindromo, quindi il programma deve quindi stampare: 3 Notare che, ad esempio, anche i sottovettori [9,9], [1], [6] sono palindromi, ma hanno lunghezza inferiore. Esercizio 2 Scrivere un programma che legga da tastiera gli interi positivi k, n ed m, e successivamente una sequenza di k+(n x m) valori interi positivi. Il programma deve allocare dinamicamente un vettore A di lunghezza k ed una matrice M di dimensione n x m. Il programma deve inserire i primi k elementi letti in A ed i restanti in M. Il programma deve stampare l'indice della riga di M che contiene il maggior numero di elementi distinti di A. Si dovra' modificare QUESTO file definendo il corpo della funzione find_index_row(). E' possibile comunque introdurre eventuali funzioni ausiliarie. Lo scheletro del programma fornito si occupa della lettura dei valori k, n ed m, dell'allocazione del vettori A e della matrice M, e dell'inserimento dei valori nel vettore e nella matrice. Si deve modifare il programma intervenendo sul corpo della funzione. Si possono aggiungere funzioni ausiliarie, ma non si deve assolutamente modificare il codice del main. La stampa del risultato non deve essere implementata, essendo gia' presente nello scheletro del programma fornito. Il prototipo della funzione da implementare e' il seguente: int find_index_row(int *A, int k, int** M, int n, int m) La funzione deve restituire l'indice della riga di M che contiene il maggior numero di elementi distinti del vettore A. L'ordine con cui questi elementi compaiono è ininfluente. In una visione insiemistica, sia A l'insieme dei gli elementi contenuti nel vettore e sia M[i] l'insieme degli elementi contenuti nella riga i-esima di M, il numero di elementi in comune e' dato dalla cardinalita' dall'intersezione tra A ed M[i]. Si deve restituire l'indice della riga che massimizza la cardinalita' di questa intersezione. Note Si puo' assumere che esista una riga che contenga un numero strettamente maggiore delle altre di elementi di A. Fare attenzione che un elemento del vettore A potrebbe comparire piu' volte in una riga di M, ma va conteggiato una sola volta, come nell'intersezione insiemistica. Esempio 4 3 5 6 1 6 2 1 2 5 6 1 6 7 6 6 8 2 2 2 0 2 Il vettore A ha dimentsione 4 e si ha A = [6,1,6,2]. M ha dimensione 3x5, e le righe sono le seguenti: M[0] = [1,2,5,6,1], M[1] = [6,7,6,6,8], M[2] = [2,2,2,0,2]. La riga 0 ha in comune con A 3 elementi: 1,2,6, mentre le righe 1 e 2 hanno in comune con A solamente un elemento. Il programma deve quindi stampare: 0 Esercizio 3 Scrivere un programma che legga da tastiera due interi positivi n e m, e successivamente una sequenza di n x m valori interi. Il programma deve allocare dinamicamente una matrice M di dimensione n x m ed inserire gli elementi letti nella matrice. Il programma deve implementare due funzioni, sort_row() e sort_col(), che permettano di ordinare parzialmente una riga o una colonna. Si dovra' modificare QUESTO file definendo il corpo delle funzioni sort_row() e sort_col(). E' possibile comunque introdurre eventuali funzioni ausiliarie. Lo scheletro del programma fornito si occupa della lettura dei valori di n ed m, dell'allocazione della matrice M e dell'inserimento dei valori nella matrice stessa. Si deve modifare il programma intervenendo sul corpo delle funzioni sort_row() e sort_col(). Si possono aggiungere funzioni ausiliarie, ma non si deve assolutamente modificare il codice del main. La stampa del risultato non deve essere implementata, essendo gia' presente nello scheletro del programma fornito. La funzione sort_row() ha il seguente prototipo: void sort_row(int **M, int n, int m, int i, int j, int k) La funzione ordina la riga i dalla colonna con indice j alla colonna con indice k, incluse. In altre parole, si ordina il sottovettore M[i][j]...M[i][k] della riga i-esima di M. La funzione sort_col() ha il seguente prototipo: void sort_col(int **M, int n, int m, int j, int i, int h) La funzione ordina la colonna j dalla riga con indice i alla riga con indice h, incluse. In altre parole, si ordina il sottovettore M[i][j]...M[h][j] della colonna j-esima di M. Note: Si puo' utilizzare uno qualsiasi degli algortimi di ordinamento visti a lezione Nella funzione sort_row si puo' assumere j <= k Nella funzione sort_col si puo' assumere i <= h Esempio Si inseriscono i valori 4 5 1 2 5 6 1 6 7 6 1 8 4 3 2 0 1 9 8 7 6 5 M ha dimensione 3x5, e le righe sono le seguenti: M[0] = [1,2,5,6,1], M[1] = [6,7,6,1,8], M[2] = [4,3,2,0,1], M[3] = [9,8,7,6,5]. La matrice risulta quindi essere: 1 2 5 6 1 6 7 6 1 8 4 3 2 0 1 9 8 7 6 5 Invocando la funzione sort_row(M, 4, 5, 1, 1, 3), si deve ordinare la riga con indice 1 di M, dalla colonna 1 alla colonna 3. La riga diviene quindi M[1] = [6,1,6,7,8], la matrice diviene quindi: 1 2 5 6 1 6 1 6 7 8 4 3 2 0 1 9 8 7 6 5 Invocando la funzione sort_col(M, 4, 5, 2, 0, 4) si vuole ordinare la colonna di indice 2 dalla riga 0 alla riga 4, quindi si vuole ordinare tutta la colonna con indice 2 di M, la matrice diviene quindi: 1 2 2 6 1 6 1 5 7 8 4 3 6 0 1 9 8 7 6 5