ESERCITAZIONI IN LABORATORIO

Alcuni degli esercizi consegnati verranno selezionati per essere discussi durante la lezione di laboratorio e poi trasferiti da me nella cartella EserciziCorrettiInAula del canale Generale come riferimento per tutti gli studenti.

• Laboratorio 1 : Esercizi assegnati (Codice lab01_x):
  
  1. Scrivere un programma che scrive sullo schermo "Benvenuti al corso di programmazione in C".
  2. Scrivere un programma che richiede all'utente di inserire due numeri interi e poi calcola e stampa la loro somma, differenza, prodotto e risultato della divisione.
  3. Scrivere un programma che chiede all'utente di inserire da tastiera un numero intero di 5 cifre e lo riscrive "in verticale" cioe' mettendo un accapo dopo ogni cifra. (Sugg. usare l'operatore % che calcola il resto della divisione intera.)
  4. Scrivere un programma che, utilizzando degli asterischi, disegna sullo schermo un rettangolo (pieno) di base 8 e altezza 6 e poi sotto un triangolo rettangolo (pieno) di altezza 6 e poi ancora un triangolo isoscele (pieno) di altezza 7. Come qui di sotto:

     ********
     ********
     ********
     ********
     ********
     ********
     

     *
     **
     ***
     ****
     *****
     ******
     

• Laboratorio 2 : Esercizi assegnati (Codice lab02_x):
  
  1. Scrivere un programma che, utilizzando degli asterischi, disegna sullo schermo i due triangoli rettangoli di altezza 6 qui di sotto e poi ancora sotto un triangolo isoscele (pieno) di altezza 7. Come qui di sotto. ATTENZIONE: usare una istruzione printf diversa per ogni riga del triangolo.

     *
     **
     ***
     ****
     *****
     ******
     

          *
         **
        ***
       ****
      *****
     ******
     

             *
            ***
           *****
          *******
         *********
        ***********
       *************
     
     

  2. Scrivere un programma che legge da tastiera 5 numeri interi e scrive sullo schermo la loro somma e la loro media.
  3. Scrivere un programma che legge da tastiera 5 numeri interi e scrive sullo schermo la loro somma e la loro media. Il programma dovra' utilizzare solo tre variabili .
  4. Ricopiare, eseguire e poi completare il programma al LINK: minTra2numeri.C
  5. Scrivere un programma che legge da tastiera 5 numeri interi e scrive sullo schermo qual'è il più grande e qual'è il più piccolo dei numeri inseriti.
• Laboratorio 3 : Esercizi assegnati (Codice lab03_x):
  In tutti gli esercizi seguenti usare una istruzione while.
  1. Scrivere un programma che richiede all'utente un numero intero x e poi scrive sullo schermo una linea composta da x asterischi seguiti da x pallini. Esempio: se l'utente inserisce 4, allora il programma dovrà stampare ****oooo
     
  2. Scrivere un programma che richiede l'inserimento di 10 numeri interi e alla fine scrive sullo schermo quanti numeri pari sono stati inseriti.
     
  3. Scrivere un programma che richiede l'inserimento di 10 numeri interi e alla fine scrive sullo schermo il valore massimo e il valore minimo che sono stati inseriti.
  4. Scrivere un programma che richiede l'inserimento di una serie di numeri interi positivi; l'inserimento termina quando l'utente inserisce 0 o un valore negativo. Al termine dell'inserimento, sullo schermo viene scritta la somma e la media dei numeri inseriti. ATTENZIONE: organizzare il ciclo in modo che il numero <=0 non venga sommato al totale e al contatore.
  5. Scrivere un programma che richiede all'utente di inserire 10 numeri interi compresi tra 1 e 100 (estremi inclusi), ne calcola la somma e la scrive sullo schermo.
     Attenzione: ogni volta che l'utente inserisce un valore errato (fuori dall'intervallo previsto) il programma dovra' segnalare l'errore e richiedere un altro numero... il ciclo di immissione termina SOLO quando sono stati immessi 10 numeri VALIDI.
• Laboratorio 4: Esercizi assegnati (Codice lab04_x):
  
  1. Scrivere un programma che prende in input un numero intero e scrive sullo schermo se il numero è un numero primo.
  2. Scrivere un programma che richiede l'inserimento di 10 numeri interi e alla fine scrive sullo schermo il valore massimo e il secondo più grande che sono stati inseriti. Se quello che risulta essere il valore max è stato inserito due volte, allora verrà riportato come massimo e secondo massimo. Usare un solo ciclo while .
  3. Scrivere un programma che legge da tastiera sequenza di numeri interi positivi. L'immissione termina quando l'utente inserisce il valore 0. In output viene riportato se la sequenza inserita conteneva due o più valori consecutivi uguali. Esempio: nella sequenza 5 6 6 5 3 3 4 compaiono due volte due numeri consecutivi uguali; nella sequenza 3 3 3 4 2 2 compaiono tre volte due numeri consecutivi uguali.
  4. Numeri di Fibonacci. I numeri di Fibonacci, f1, f2, ... fn sono definiti ricorsivamente come segue:
     f1=1
     f2=1
     ...
     f_n = f_n-1 +f_n-2 .
     Scrivere un programma che prende in input un numero positivo N e scrive in output l' N-esimo numero di Fibonacci.
  
  
• Laboratorio 5: Esercizi assegnati (Codice lab05_x):
  OGGI TRIANGOLI! ... ricordiamo la sintassi del for.. esempio per disegnare un quadrato di lato 10:

  ----------------------------------------------------------------
  		int r;
  		int c;
  
  		for( r=1; r ≤ 10;  r++){
  			for (c=1; c ≤ 10; c++)
  				printf(  "*" );
  
  		printf("\n" );
  		}
  ----------------------------------------------------------------
  

  1. Scrivere un programma che prende in input un numero positivo N compreso tra 3 e 33 (inserire controllo input!) e disegna in output i seguenti triangoli di N righe. (usare istruzioni for). L'esempio è per N=6.
     Triangolo 1:

     *
     **
     ***
     ****
     *****
     ******
     

     Triangolo 2:

     ******
     *****
     ****
     ***
     **
     *
     

     Triangolo 3:

     ******
      *****
       ****
        ***
         **
          *
     

     Triangolo 4:

          *
         **
        ***
       ****
      *****
     ******
     

  2. Il Triangolo di Floyd è definito come un triangolo costruito utilizzando numeri naturali consecutivi. Ad esempio qui di sotto è definito il triangolo di Floyd di 5 righe.

      1
      2  3 
      4  5  6
      7  8  9  10
      11 12 13 14 15
     

     Scrivere un programma che prende in input un numero positivo N compreso tra 3 e 33 (inserire controllo input!) e disegna in output il triangolo di Floyd di N righe.
  3. Scrivere un programma che calcola quanti sono i triangoli rettangoli con lati interi ≤ 500.
     Opzionale : produrre in ouput tutte le terne pitagoriche trovate.
     
  4. Scrivere un programma che prende in input 3 numeri interi inseriti da tastiera e li scrive in output in ordine crescente utilizzando in totale soltanto 3 confronti (con operatore ≤ ) tra i numeri stessi all'interno di istruzioni if-else annidate. No variabili supplementari (solo 3 variabili per i 3 numeri).
• Laboratorio 6: Esercizi assegnati (Codice lab06_x):
  
  1. Svolgere almeno uno dei seguenti esercizi utilizzando l'istruzione switch (qui un esempio per ricordare la sintassi).
     

     --------------------------------------
     	switch(x) {                      
     	case 0:                       
     		printf("zero\n");
     		break;
     		case 1:                       
     		printf("uno\n");
     		break;
     	case 2:                       
     		printf("due\n");
     		break;
     	case 3:                       
     		printf("tre\n");
     		break;
     	default:                      
     		printf("non compreso\n"); 
     		break;
     	}
     --------------------------------------
     

     Utilizzare la nota filastrocca per il numero dei giorni dei mesi e non dimenticare gli anni bisestili! Si ricorda che gli anni bisestili sono quelli divisibili per 4, con eccezione dei secoli che devono essere divisibili per 8 (ad esempio il 1900 non è stato bisestile). Assumiamo valori di anno validi a partire dall'inizio del calendario gregoriano 1582 e fino al 2100.
     CURIOSITA': il calendario gregoriano fu promulgato da papa Gregorio XIII a villa Mondragone adesso proprietà dell'Università di Roma Tor Vergata.
     • Scrivere un programma che chiede all’utente di inserire tre numeri interi giorno, mese, anno corrispondenti ad una data "iniziale", poi chiede di inserire ulteriori tre numeri interi giorno, mese, anno corrispondenti ad una data "finale" successiva alla precedente e poi calcola il numero di giorni tra le due date.
       Nota: inserendo la propria data di nascita come data iniziale e il giorno attuale come data finale possiamo scoprire qual'è la nostra età in giorni!
     • Scrivere un programma che chiede all’utente di inserire tre numeri interi giorno, mese, anno corrispondenti ad una data "iniziale", poi chiede di inserire un numero intero positivo che corrisponde ad un numero di giorni trascorsi dalla data iniziale e calcola la data finale corrispondente.
       Nota: inserendo la propria data di nascita come data iniziale possiamo calcolare quando sarà il nostro compleanno di 10.000 giorni!
  2. Un numero si dice perfetto se è uguale alla somma dei suoi divisori (escluso il numero stesso). Scrivere un programma che, dato un numero intero positivo, calcola se e' un numero perfetto.
  3. Scrivere un programma che stampa tutti i numeri interi tra 1 e 300 in righe contenenti 15 numeri ciascuna. I numeri devono essere ben incolonnati. Inoltre, se il numero termina per 7 oppure è divibile per 7 NON deve essere stampato ed nel suo posto deve essere scritto BUM.
• Laboratorio 7: Esercizi assegnati (Codice lab07_x):
  
  1. Scrivere una funzione che, dato un numero intero positivo, calcola se e' un numero primo (non stampa messaggio ma restituisce valore booleano). Scrivere poi un programma, che utilizza questa funzione, che conta quanti sono i numeri primi p <10000.
  2. Def.: un numero si dice perfetto se è uguale alla somma dei suoi divisori (escluso il numero stesso). Scrivere una funzione che, dato un numero intero positivo, calcola se e' un numero perfetto (non stampa messaggio ma restituisce valore booleano). Scrivere poi un programma, che utilizza questa funzione, che scrive sullo schermo tutti i numeri perfetti <10000.
  3. Ridisegnare i triangoli del Lab05_1 chiedendo all'utente l'altezza dei triangoli e il carattere di tastiera con cui riempirli (quindi non necessariamente *) e utilizzando la seguente funzione vista a lezione:

     void stampaRiga(char simb, int lung)
      {   int i;
          for ( i= 1; i <= lung; i++)
              printf("%c", simb);
      }
     

  4. Piccola calcolatrice Scrivere un programma che legge un valore di tipo double, uno di tipo char e poi ancora uno di tipo double (in questo ordine!) e infine fa in modo che: se il carattere letto è '+' allora stampa la somma dei due valori numerici; se il carattere è '-' allora stampa la differenza dei due valori numerici; se il carattere è '*' allora stampa il prodotto dei due valori numerici; se il carattere è '/' allora stampa la divisione tra i due valori numerici; se è un altro carattere allora stampa un messaggio di errore.
     (Utilizzare l'istruzione switch)
     ATTENZIONE a svuotare il buffer dopo l'immissione dell'int come nell'esempio charinput1.c visto nella lezione 6)
• Laboratorio 8: Esercizi assegnati (Codice lab08_x): :
  
  1. Utilizzare la funzione:

     #include < stdlib.h >
     #include < time.h>
     .
     .
     .
     int genera()
      {   int x;
          x=rand()%201 - 100;
     	 return x;
      }
     

     e scrivere un programma che genera 10000 numeri random compresi tra -100 e 100 e scrive in output: 
     • quanti sono rispettivamente i numeri positivi/negativi/nulli 
     • quanti sono rispettivamente i numeri pari/dispari 
     • quante coppie di numeri consecutivi uguali sono state generate
  2. Scrivere un programma che simula una successione di lanci di moneta (Testa o Croce); continua a generare lanci di moneta fino a che è verificata la seguente condizione di terminazione : la sequenza generata contiene almeno 5 esiti uguali consecutivi (es: 5 volte Testa, oppure 5 volte Croce). Il programma deve stampare "testa" o "croce" relativa ad ogni lancio e alla fine restituire il numero di lanci di moneta che sono stati necessari per verificare la condizione di terminazione.
  3. Ho fatto un sogno in cui una fatina dai capelli turchini mi dava un numero del lotto. Decido di giocare questo numero alle estrazioni del lotto della ruota di Roma: 1 Euro ogni settimana per un anno intero (52 settimane).
     Scrivere un programma per simulare la situazione e stabilire quanto vinco/perdo sapendo che:
     • Nella ruota di Roma vengono estratti 5 numeri distinti tra 1 e 90
     • La vincita per aver indovinato un numero, avendo giocato 1 Euro è di 11,23 Euro. (Vedi tutti gli importi su ) lotto-italia.
     NOTA: utilizzare 5 variabili distinte per le 5 estrazioni della ruota di Roma.
  4. Scrivere un programma C per risolvere il seguente quesito:
     Esiste un numero formato da 8 cifre che moltiplicato per un numero primo dà come risultato un numero di 9 cifre uguali?
  
  
• Laboratorio 9: Esercizi assegnati (Codice lab09_x): :
  
  1. Varie su vettori
     Scrivere un programma che:
     • Genera un vettore random di 35 valori interi tra 15 e 85.
     • Lo stampa sullo schermo (ben incolonnato con 7 numeri per riga).
     • Calcola la media (restituisce il valore corrispondente)
     • Calcola quanti valori pari sono stati generati
     • Calcola il valore minimo (restituisce l'indice)
     • Controlla se ci sono due elementi consecutivi uguali (restituisce l'indice del primo dei due oppure -1 se non ci sono)
     • Controlla se tutti gli elementi sono distinti (restituisce 1 oppure 0)
     Ognuno dei punti precedenti deve essere svolto con una (diversa) funzione mentre nel main vengono stampati tutti i vari risultati restituiti dalle funzioni. (Utilizzare eventualmente come base il programma ) Vettori.c visto a lezione.)
  2. Scrivere un programma che prende in input un numero positivo N e scrive in output il valore di n!. Il programma deve definire e utilizzare una funzione ricorsiva int fatt(int) per calcolare tale numero.
  3. Scrivere un programma che prende in input un numero positivo B e un numero positivo N e scrive in output il valore della potenza N-esima di B. Il programma deve definire e utilizzare una funzione ricorsiva int pot(int,int) per calcolare tale numero.
  4. Numeri di Fibonacci. Riscrivere l'esercizio lab04_4 utilizzando una funzione ricorsiva per il calcolo dei numeri di fibonacci. (eventualmente scrivere tutte e due le versioni e nel main eseguierle entrambe per notare la differenza di velocità di calcolo)
  5. Def.: Un numero naturale n si dice quadratoso se è un quadrato ed inoltre cancellando ad n una delle sue cifre si ottiene ancora un quadrato.
     Ad esempio 1369 è quadratoso infatti 1369=37² e, cancellando la cifra 3, si ottiene 169=13² . Analogamente 2025= 45² è quadratoso infatti eliminando la prima cifra si ottiene 025 = 25 = 5² .
     Scrivere una funzione che, dato un numero intero positivo, calcola se e' un numero quadratoso (non stampa messaggio ma restituisce valore booleano). Scrivere poi un programma che scrive in output tutti i numeri quadratosi di 4 cifre.
  
  
• Laboratorio 10: Esercizi assegnati (Codice lab10_x): :
  1. Il gioco "Indovina il numero"
     Scrivere un programma che simula il gioco IndovinaNumero in cui si deve indovinare un numero da 1 a 100 a seguito di risposte "troppo alto" o "troppo basso". Scrivere un programma per la versione UtenteVsComputer in cui il computer "pensa" (cioè genera in modo random il numero) e l'utente lo deve indovinare. Ad ogni tentativo dell'utente il computer risponde "troppo alto" o "troppo basso" finchè l'utente non indovina. Quando l'utente indovina, viene scritto sullo schermo il numero di tentativi che sono stati necessari per indovinare il numero.
  2. Congettura di Collatz ver.1
     La congettura di Collatz è una delle più semplici congetture matematiche non ancora risolte. La congettura riguarda il seguente algoritmo:
     Si prenda un intero positivo n.
     

      1.Se n = 1, l'algoritmo termina.

      2.Se n è pari, si divida per due; altrimenti si moltiplichi per 3 e si aggiunga 1.

      3.Si ripete l'algoritmo da 1. sul numero ottenuto.

     Per esempio, iniziando con n = 6, otteniamo la successione 6, 3, 10, 5, 16, 8, 4, 2, 1.
     La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza.
     Scrivere una funzione Collatz (eventualmente ricorsiva!) che prende in input un numero intero x (restituisce void) e stampa sullo schermo la sequenza di Collatz da x a 1. Scrivere un programma (fuzione main) che chiede all'utente di inserire un numero intero e, usando la funzione Collatz, stampa la sequenza ottenuta.
  3. Congettura di Collatz ver.2
     In riferimento all'esercizio precedente, chiamiamo lunghezza di Collatz (Lc) il numero di elementi della successione per arrivare ad 1. Dall'esempio precedente Lc(6)= 9.
     Scrivere una funzione Collatz che prende in input un numero intero x e restituisce la sua lunghezza di Collatz Lc(x). Scrivere poi un programma che, usando tale funzione, calcola la lunghezza di Collatz di tutti i numeri tra 1 e 1000 e li scrive in un array. Calcola poi il valore massimo di tale lunghezza tra quelli ottenuti e stampa sullo schermo quali sono i numeri interi che hanno tale lunghezza di Collatz massima.
  4. Crivello di Eratostene
     Implementare una funzione che simula il crivello di Eratostene per il calcolo dei numeri primi. Utilizzarla per calcolare tutti i numeri primi tra 2 e 1000.
     La funzione int Crivello(int C[], int n) sarà definita su un array booleano C di dimensione n tale che
     • C[i] =1 significa che i è primo e C[i] =0 significa che i NON è primo
     • All’inizio pongo C[i]=1 per ogni i
     • Realizzo n-1 cicli che iniziano ogni volta dall’elemento che contiene il primo 1
     • Se un ciclo comincia da C[i] allora assegno 0 a tutti i C[j] tale che j è un multiplo di i
• Laboratorio 11 (Codice lab11_x): :
  
  1. Problema del Baricentro (tratto da un vecchio esame)
     Dato un vettore v di interi di dimensione n, definisco baricentro del vettore l’indice i tale che:
     v[0] + v[1] + . . . + v[i] = v[i + 1] + . . . + v[n − 1]
     • Scrivere una funzione int baricentro(int v[], int n) che restituisce l'indice del baricentro del vettore v, se esiste, oppure restituisce -1 se non esiste un baricentro.
     • Scrivere poi un programma (funzione main) che genera e stampa un vettore di dimensione 100 di valori interi random tra -5 e 5 e poi, richiamando la funzione baricentro calcola il suo baricentro.
     • Qual è la complessità della funzione baricentro? Nell'ipotesi che tutti i valori del vettore siano positivi, l'algoritmo può essere realizzato in modo più efficiente?
  2. Segmenti in un vettore
     Dato un vettore a valori interi in {0, 1}, definisco segmento una successione di 1 consecutivi. La lunghezza del segmento è il numero di 1 contenuti mentre l’inizio del segmento è l'indice i del primo 1. Vogliamo calcolare la lunghezza e l’inizio del segmento di lunghezza massima. Ad esempio nel vettore:

     1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1
     

     un segmento di lunghezza massima si trova in posizione 11 (iniziando a contare da zero) e ha lunghezza 8. Ce n'è anche un'altro di lunghezza 8.
     1. Scrivere una funzione in C, MaxSegm, che prende in input un vettore e calcola e stampa la posizione del massimo segmento contenuto e la sua lunghezza. (Se nel vettore ci sono più segmenti di lunghezza massima, riportare quello di inizio in i con i minimo).
        
     2. Scrivere un programma in C (funzione main) che genera un vettore di interi random in {0, 1} di lunghezza 100 e richiamando la funzione MaxSegm scrive le informazioni calcolate.
     3. Analizzare la complessità dell’algoritmo utilizzato nella funzione MaxSegm. (inserirlo alla fine del file .C come commento).
  3. Gioco IndovinaNumero
     Scrivere un programma che simula il gioco IndovinaNumero discusso a lezione in cui si deve indovinare un numero da 1 a 100 a seguito di risposte "troppo alto" o "troppo basso". Il programma, oltre ad eventuali funzioni ausiliarie, dovrà contenere 2 funzioni ComputerVsUtente e UtenteVsComputer che restituiscono il numero di tentativi necessari per indovinare il numero. Il programma principale si compone poi delle due chiamate di funzione e della "proclamazione" del vincitore.
• Laboratorio 12 (Codice lab12_x) :
  
  Utilizzare gli algoritmi di ordinamento visti nella lezione 11.
  
  1. Scrivere una funzione int SelectionSort(int v[], int s) che prende in input un vettore di interi di dimensione s e lo ordina con l'algoritmo di selectionSort e restituisce il numero di confronti tra elementi del vettore che sono stati effettuati.
     Scrivere poi un programma che per 10 volte genera un vettore di interi di 30 elementi tra 10 e 99, lo stampa sullo schermo, lo ordina richiamando SelectionSort e stampa sullo schermo il numero di confronti tra elementi del vettore effettuati.
     Poi genera un vettore ordinato ed esegue l'algoritmo sul vettore ordinato e ancora genera un vettore ordinato al contrario ed ancora esegue l'algoritmo stampando il numero di confronti effettuati.
  2. Scrivere una funzione int BubbleSort(int v[], int s) che prende in input un vettore di interi di dimensione s e lo ordina con l'algoritmo di BubbleSort e restituisce il numero di confronti tra elementi del vettore che sono stati effettuati.
     Ripetere l'esercizio 1 con questo altro algoritmo di ordinamento.
  3. Scrivere una funzione int InsertionSort(int v[], int s) che prende in input un vettore di interi di dimensione s e lo ordina con l'algoritmo di insertionSort e restituisce il numero di confronti tra elementi del vettore che sono stati effettuati.
     Ripetere l'esercizio 1 con questo altro algoritmo di ordinamento.
  4. Scrivere un programma che genera un vettore random di 50 elementi interi tra 10 e 99 e lo stampa sullo schermo. Poi applica i diversi algoritmi di ordinamento degli esercizi 1,2 3 (ricopiare le tre funzioni) sul vettore generato e stampa sullo schermo quanti confronti tra elementi sono stati necessari per ordinarlo.
     ATTENZIONE: fare una copia del vettore generato e ordinare la copia in modo da poter confrontare i diversi algorimi di ordinamento.
• Laboratorio 13: Esercizi assegnati (Codice lab13_x): :
  
  1. Varie su Matrici
     Scrivere un programma in C che:
     1. Genera una matrice di dimensione 20x30 di numeri casuali compresi tra -10 e 10 (estremi inclusi)
     2. Stampa la matrice sullo schermo
     3. Verifica se esiste una riga della matrice la cui somma sia 0. In caso affermativo stampa la riga sullo schermo.
     4. Verifica se esiste una colonna della matrice la cui somma sia 0. In caso affermativo stampa la colonna sullo schermo.
     5. Identifica la riga della matrice la cui somma degli elementi è maggiore. Stampa sullo schermo l'indice di tale riga.
     6. Verifica se esiste una riga la cui somma degli elementi è uguale alla somma degli elementi di una colonna. In caso affermativo stampa tali indici di riga e colonna, in caso negativo segnala che la condizione non è verificata. Sugg.: utilizzare un vettore di supporto.
     7. Calcola il max della matrice int maxMatrice(int a[][COL], int r, int c)
     8. Calcola il max di ogni riga void massimiRighe(int a[][COL], int r, int c, int rmax[RIG]) e lo mette in un vettore rmax.
     I vari punti devono essere svolti come funzioni. (Scaricare il file array2dim.c) .
  2. Scrivere una funzione int MergeSort(int v[], int s) che prende in input un vettore di interi di dimensione s e lo ordina con l'algoritmo di MergeSort e restituisce il numero di confronti tra elementi del vettore che sono stati effettuati.
     Ripetere l'esercizio 12.1 con questo altro algoritmo di ordinamento.
  3. Scrivere una funzione int QuickSort(int v[], int s) che prende in input un vettore di interi di dimensione s e lo ordina con l'algoritmo di QuickSort e restituisce il numero di confronti tra elementi del vettore che sono stati effettuati.
     Ripetere l'esercizio 12.1 con questo altro algoritmo di ordinamento.
• Laboratorio 14: Esercizi assegnati (Codice lab14_x): :
  
  1. Matrice dell'Amicizia
     Scrivere un programma in C che:
     1. Genera una matrice M quadrata simmetrica di 10 righe (colonne) con valori random tra 0 e 1.
     2. Stampa la matrice sullo schermo.
     3. Interpretando la matrice con il significato M(i,j)=1 se e solo se i è amico di j, elencare sullo schermo tutte le triple (r,s,t) in cui r, s e t sono tutti amici.
     4. (Difficile)Trovare il gruppo più grande in cui sono tutti amici. NOTA: Per questo punto sarebbe utile generare una matrice con molti 1. Un modo di realizzarlo potrebbe essere di generare valori random tra 0 e 3 e poi trascrivere i valori >0 come tutti 1.
  2. Problema delle caselle speciali.
     Data una scacchiera quadrata di lato dispari 2N+1, diciamo che una casella è speciale se il suo colore è predominante sia nella riga che nella colonna a cui appartiene.
     Scrivere un programma che genera in input una matrice quadrata di lato 2N+1 a valori random (interi) in {0,1} che rappresentano i colori "bianco" e "nero" e calcola quante caselle speciali ci sono.
     Nota: Un buon algoritmo realizza la soluzione senza leggere "troppe volte" ciascun elemento della matrice. Per esempio, utilizzando un vettore come struttura dati aggiuntiva, si puo' realizzare una soluzione in cui ogni elemento della matrice viene letto soltanto 3 volte.
     Curiosità Esiste una matrice del tipo suddetto con (soltanto) 4N caselle speciali (sapete trovarla?) e si può dimostrare che non esistomo matrici con meno di 4N caselle speciali.
  3. Problema MaxSum
     Dato un array v di dimensione n di valori interi (positivi e negativi), per ogni coppia (i, j) con i<=j, definisco S_i,j=v[i]+v[i+1]+v[i+2]+....+v[j] cioè la somma degli elementi consecutivi da v[i] a v[j]. Scrivere una funzione int MaxSum(int v[], int n) che determina e restituisce il valore massimo tra tutte le somme S_i,j. Scrivere poi un programma che inizializza un vettore di dimensione 100 con valori random tra - 50 e 50 e applicando poi la funzione MaxSum calcola il valore della massima somma definita come sopra.
     Valutare la complessità della funzione MaxSum che avete scritto. (Riuscite a scrivere una funzione MaxSum quadratica? Riuscite a scriverne una lineare?)

• Laboratorio 15: Esercizi assegnati (Codice lab15_x): :
  
  1. Lettura e scrittura su file
     • Scrivere una funzione writeMatrixToFile(const char *filename, int matrix[ROW][COL], int rows, int cols) che scrive la matrice di tipo int, di dimensioni rows x cols, su un file con il nome fornito.
     • Scrivere una funzione readMatrixFromFile(const char *filename, int matrix[ROW][COL], int *rows, int *cols) che legge una matrice da un file con il nome fornito e la memorizza in una matrice di tipo int. La funzione dovrebbe anche determinare le dimensioni della matrice e memorizzarle in rows e cols.
     • Scrivere una funzione principale che chiede all'utente di specificare tre nomi di file, ad esempio A.txt, B.txt, C.txt, e implementare il prodotto di matrici A.B=C. Pertanto, il programma dovrebbe leggere la matrice A da A.txt, la matrice B da B.txt, calcolare il prodotto delle matrici C e scrivere il risultato in C.txt.
  2. Problema della bandiera italiana (difficile?)
     Input: array random i cui elementi hanno valore "verde", "bianco" o "rosso" codificato in qualche modo.
     Output: array "colorato" come bandiera italiana (tutti i verdi a sinistra, i bianchi al centro e i rossi a destra).
     Progettare un algoritmo lineare. Scrivere un programma che risolve il problema e che opera con UNA SOLA lettura dell'array (se non ci riuscite utilizzate comunque non più di tre passate!) e che effettua SOLO SCAMBI tra gli elementi. (Non si deve ordinare l'array con algoritmo di ordinamento e non è consentito "contare" quanti elementi hanno un dato colore)
  
  
• Laboratorio 16: Esercizi assegnati (Codice lab16_x): :
  
  1. Completare gli esercizi su array/matrici lab14_1,lab14_2,lab14_3 e lab15_2.
  2. Data una matrice mxn a valori interi, la riga t è un taglio orizzontale se la somma di tutti i valori nelle posizioni dalla riga 0 alla riga t differisce al più di 10 dalla somma di tutti i valori nelle posizioni dalla riga t + 1 alla riga m − 1.
     • Scrivere una funzione int RigaTaglio(int a[][SIZE], int * somma) che, data una matrice a restituisce l’indice t della riga taglio, se esiste, altrimenti restituisce -1. Se la riga taglio esiste mette nella variabile somma il valore della somma dei valori dalla riga 0 alla riga t.
     • Scrivere un programma in C che:
       1. Genera una matrice 15x15 a valori interi random tra -17 e 173 tali che non ci siano elementi uguali sulla stessa riga.
       2. Stampa la matrice ben formattata sullo schermo
       3. Utilizza la funzione RigaTaglio per individuare l’eventuale riga taglio.
       4. Stampa le informazioni calcolate dalla funzione precedente. . NOTA: la stampa non deve essere effettuata all’interno della funzione, ma nel main.

• Laboratorio 17: Esercizi assegnati (Codice lab17_x): :
  Per i seguenti esercizi sulle stringhe utilizzare come modello i codici lunghezza.c, prefisso.c, copiastringhe.c,
  1. Cambiamo le parole
     Scrivere un programma che
     1. Data una stringa in input la restituisce modificando tutte le a in e.
     2. Data una stringa in input e un dato carattere, restituisce la stringa dove tutte le occorrenze del carattere scelto sono state cancellate.
     3. Data una stringa in input la restituisce con una in cui tutte le vocali sono scritte in maiuscolo.
     Non utilizzare le funzioni predefinite sulle stringhe. Le stringhe devono essere effettivamente modificate e non solo stampate sullo schermo.
  2. Un gioco enigmistico: il lucchetto
     Nel linguaggio enigmistico un lucchetto è un gioco caratterizzato dallo schema XY + YZ -> XZ. In pratica si trovano due parole w1 e w2 in cui l'ultima parte (un suffisso) di w1 è uguale alla prima parte (un prefisso) di w2. Eliminando le parti in comune e leggendo il restante si ottiene la terza parola w3 che si chiama "lucchetto".
     Per esempio:

      CANE/NERO = CARO; 
     
      VELA/LANA = VENA; 
     
      CRISTALLO/STALLONE = CRINE;
     
      RISCHIO/SCHIOCCO = RICCO,
     
      MAGGIO/GIOIA = MAGIA
     
      CARATO/ATOMI = CARMI
     
      CAST/TERME = CASERME
     
      MATCH/CHADOR = MATADOR. 
     

     • Scrivere una funzione int lungh( char s[]) che restituisce la lunghezza della stringa s;
     • Scrivere una funzione int suff_pref( char s[], char t[], int n) che restituisce 1 se il suffisso di lunghezza n della stringa s è uguale al prefisso di lunghezza n della stringa t e restituisce 0 in caso siano diversi. (Essenzialmente la stringa s deve essere controllata a partire dalla posizione lungh(s) - n).
     • Scrivere un programma che legge due stringhe e utilizzando la funzione precedente verifica se le due stringhe possono creare un lucchetto.
     • Il programma scrive un lucchetto tra le due parole (che ovviamente non deve necessariamente avere un senso come parola in italiano) .

• Laboratorio 18: Esercizi assegnati (Codice lab18_x): :
  
  1. Problema della classifica del campionato .
     Input:
     • matrice quadrata in cui righe e colonne corrispondono a delle squadre (di calcio?) e gli elementi m(i,j) a valori -1, 0 oppure 1 che corrispondono al fatto che la partita tra i e j è stata persa, pareggiata o vinta. (NOTA: gli elementi della diagonale non sono significativi ai fini dell'esercizio mentre le due parti sopra e sotto la diagonale potrebbero corrispondere alle partite di andata e di ritorno)
     • vettore di stringhe della stessa dimensione della matrice che contiene i nomi delle squadre.
     Scrivere un programma che produce in output la classifica delle squadre con i punteggi corrispondenti (ottenuti sommando per ogni partita : 0= perdita, 1= pareggio, 3=vincita). Utilizzare le strutture dati di supporto che si ritengono più adeguate.
     Utilizzare come base di partenza il programma provaCampionato.c visto a lezione.
  2. Anagrammi
     L’anagramma è una parola o frase che composta dalle lettere di un’altra parola o frase disposte in un ordine diverso. Per esempio:
     COLTA e TALCO sono anagrammi;
     ATTORE è un anagramma di TEATRO;
     CONTARE ha come anagrammi CARTONE, ARCONTE, CONTER, CORNATE;
     BIBLIOTECARIO è BEATO COI LIBRI;
     I GELATI DI MORE sono la DIETA MIGLIORE
     il MAESTRO DI CANTO è il TORMENTO DI CASA.
     Scrivere un programma che legge due stringhe (eventualmente contenenti degli spazi) e verifica se le due stringhe sono una l’anagramma dell’altra. Gli spazi bianchi vanno ignorati. Non è consentito utilizzare funzioni predefinite sulle stringhe.

• Laboratorio 19: Esercizi assegnati (Codice lab19_x): :
  
  1. Tratto da preappello A.A. 2023-24
     Data una matrice quadrata A di dimensione m × m, definisco MatriceSomme di A una matrice B tale che B(i, j) sia uguale alla somma degli elementi della riga i e della colonna j della matrice A, ∀i, j.
     1. Scrivere una funzione MatriceSomme(int A[][COL], int B[][COL]) che, data la matrice A calcola la corrispondente la MatriceSomme B definita come sopra.
     2. Scrivere una funzione: int Max1e2(int M[][COL], int *max1, int *x1, int* y1, int *max2, int* x2, int*y2) che, data la matrice calcola il valore pi`u grande max1 e le sue coordinate x1 e y1 e il secondo valore pi`u grande max2 e le sue coordinate x2 e y2. I due valori possono essere anche coincidenti (ovviamente le coordinate saranno diverse).
     3. Scrivere una funzione in C void Genera(int a[DIM][DIM]) che genera una matrice di DIM righe e DIM colonne a valori interi random tra −10 e 10 tale che in ogni colonna non ci siano elementi consecutivi uguali.
     4. Scrivere un programma in linguaggio C (funzione main) che:
        • Usando la funzione Genera, genera una matrice di dimensione 25x25 e stampa tale matrice sullo schermo.
        • Usando la funzione MatriceSomme, genera la nuova matrice e la stampa sullo schermo.
        • Utilizza la funzione Max1e2 sulla nuova matrice e stampa i risultati calcolati sullo schermo.
     5. Discutere la complessità degli algoritmi implementati in funzione alla dimensione della matrice.
  2. Tratto da preappello A.A. 2023-24
     Si scriva un programma C che richiede all’utente di inserire una sequenza di nomi di persona. La sequenza termina quando l’utente inserisce due volte consecutive lo stesso nome. Al termine dell’inserimento viene scritto sullo schermo il nome più lungo che è stato inserito.
     Non è consentito utilizzare funzioni predefinite sulle stringhe.
     Variante (+2 punti): Si aggiunge anche la possibilità di leggere i nomi da un file (in questo caso la terminazione avviene naturalmente quando finisce il file). Fornire anche il file di testo per provare il programma.

• Laboratorio 20: Esercizi assegnati (Codice lab20_x): :
  
  1. Varie su lista
     Aggiungere le seguenti funzioni al programma eseListaBase1.cpp :
     1. Cancellazione di TUTTE le occorrenze di un certo elemento nella lista.(Per provarlo generare una lista lunga e con pochi valori random).
        Nota: Fare attenzione al caso in cui dovranno essere eliminati "tanti" elementi iniziali.
     2. Ricerca di un elemento nella lista : restituisce eventualmente la posizione
     3. Inserimento in coda alla lista MA SOLO se l'elemento non è già presente
     4. Eliminazione di tutti gli elementi DUPLICATI di una lista. Alla fine ogni elemento deve essere presente al più una volta nella lista. (Per provarlo generare una lista lunga e con pochi valori random).

  2. Un gioco enigmistico: la cerniera
     Nel linguaggio enigmistico una cerniera `e un gioco che consiste nel trovare due parole o frasi che hanno alcune lettere, agli estremi opposti, uguali; la terza parola o frase si ottiene con la scomparsa delle parti uguali e con l’accostamento delle parti restanti. Per esempio:
           MANICO/STAMANI = COSTA;
           GLI OSTI/MAGLIO = STIMA;
           FLAUTO/GOLF = L AUTOGOL.
     Scrivere un programma che legge due stringhe (eventualmente contenenti degli spazi) e verifica se le due stringhe possono creare una cerniera. Gli spazi bianchi vanno ignorati. In caso affermativo, il programma scrive la cerniera formata dalle due parole (che ovviamente non deve necessariamente avere un senso come parola in italiano) .

  3. Problema della sorgente di montagna. (più difficile)
     Sia data una matrice quadrata di lato 20 contenente valori random tra 1 e 9 che rappresentano quote topografiche. Se una delle posizioni della matrice rappresenta una sorgente di acqua allora assumo che l'acqua coli e si diffonda nel terreno passando a posizioni adiacenti sulla stessa riga o colonna se tali posizioni hanno la stessa quota oppure quota inferiore.
     Si scriva un programma che:
     • Genera una matrice quadrata di lato 20 contenente valori random tra 1 e 9 e la stampa sullo schermo.
     • Riceve in input dall'utente una coppia di valori (i,j) che rappresenta posizione di una sorgente d'acqua.
     • Simula sulla matrice la diffusione dell'acqua generando una mappa dell'allagamento che è una matrice della stessa dimensione dove posizione della sorgente contiene il valore 2, le posizioni "allagate" contengono il valore 1 mentre le posizioni rimaste "asciutte" contengono il valore 0.
     • Stampa tale matrice sullo schermo.

• Laboratorio 21: Esercizi assegnati (Codice lab21_x): :
  
  1. Operazioni su Insiemi
     Scrivere un programma che utilizza le liste per rappresentare insiemi di interi e implementa, rispettivamente con due funzioni, le operazioni di unione e intersezione tra due insiemi. In particolare il programma dovrà inizializzare due insiemi (=liste) con valori immessi dall'utente (o generati in modo random), stamparli sullo schermo e poi creare la lista per l'insieme intersezione e per l'insieme unione (e stamparle sullo schermo).Utilizzare listebaseInsiemi.cpp :

• Laboratorio 22: Esercizi assegnati (Codice lab22_x): :
  
  1. Sia L una lista di interi (positivi e negativi).
     • Si scriva una funzione SuccNulla che prende in input una lista L e verifica se esiste una successione di nodi consecutivi la cui somma è nulla. Ad esempio nella lista L = 2 → 3 → 4 → −7 → 5 → −6 → 6 i nodi consecutivi 3 → 4 → −7 danno somma 0.
     • Si scriva una funzione CancellaSuccNulla che prende in input una lista L e cancella gli elementi di una successione nulla in L. Nell’esempio precedente la nuova lista diventa L = 2 → 5 → −6 → 6
     • Si discuta la complessità degli algoritmi utilizzati in funzione della lunghezza della lista L. (inserirlo alla fine del file .C come commento).
  2. Rotazioni di stringhe
     Data una stringa, s1 s2 s3 .... sn, chiamo rotazione di ordine 1, la stringa s2 s3 s4 ...sn s1, cioè la stringa letta a partire dala seconda posizione e in cui l'ultimo simbolo è quello che originariamente era il primo. In generale la rotazione di ordine k (k<=n) si ottiene cominciando a leggere dal k-esimo simbolo: sk .....sn s1 .....s(k-1).
     Scrivere un programma che legge una stringa senza spazi e scrive in ordine tutte le sue rotazioni. Ad esempio, se la stringa immessa fosse NATALE il programma dovrebbe scrivere in output:

     NATALE
     ATALEN
     TALENA
     ALENAT
     LENATA
     ENATAL
       

  3. Data una matrice M a valori interi, una posizione (i, j) si definisce DoppioRowCol se il valore M(i, j) compare anche in un’altra posizione h della riga i e in un’altra posizione k della colonna j, (h >=j e k >= i).
     • Scrivere una funzione int DoppioRowCol(int A[ROW][COL], int *pmax1, int *pmax2) che calcola e restituisce il numero delle posizioni DoppioRowCol della matrice; calcola inoltre i due valori distinti più grandi che si trovano in queste posizioni DoppioRowCol e ne passa il valore al main tramite i puntatori pmax1 e pmax2.
     • Scrivere una funzione che genera una matrice di interi a valori nell’intervallo [33, 66] in modo che in ogni riga non ci siano elementi consecutivi uguali.
     • Scrivere un programma in C (funzione main) che genera una matrice di interi random in [33, 66] di dimensione 25x15 e la stampa ben formattata sullo schermo. Poi, richiamando la funzione DoppioRowCol, calcola il numero delle posizioni DoppioRowCol e i due valori più grandi in tali posizioni. Poi stampa le informazioni calcolate.
     • Analizzare la complessità dell’algoritmo utilizzato nella funzione DoppioRowCol.

  4. Laboratorio 25: Esercizi assegnati (Codice lab25_x): :
     
     1. Sia data una lista di interi.
        1. Si implementi una funzione in C ListaMedie, che prende in input una lista di valori interi (data come un puntatore al suo primo nodo) A= a₁, a₂, .... ,a_n e un intero positivo k. Questa deve restituire una lista M=m₁,m₂,.....,m _n-k+1 tale che m_i = (a_i + a_i+1 + .... + a_i+k-1)/k.
        2. La lista M contiene valori float che vanno poi stampati con 2 cifre decimali. A questo scopo deve essere definito un tipo nodo opportuno e la corripospondente funzione StampaMedie per la stampa.
        3. Si inseriscano tali funzioni nel codice fornito ListaBase.cpp ListaBase.c rinominando il file come CognomeNomeLab25.c Si calcoli il costo computazionale della funzione definita (sarebbe auspicabile una funzione lineare!) rispetto alla lunghezza della lista in input. Inserire il costo computazionale come commento alla fine del file.
     2. Sia L una lista di interi.
        1. Si scriva una funzione EstraiSottolista che prende in input una lista L e due interi k1 e k2 e restituisce la sottosequenza di L composta dai nodi compresi tra il primo nodo, n1, contenente la chiave k1 ed il primo nodo, n2, contenente la chiave k2. Il nodo n2 non deve precedere n1. I nodi estremi sono compresi, ovvero n1 ed n2 devono far parte della sotto-lista di output. Al termine della funzione i nodi della sottolista estratta non faranno più parte di L. Se uno dei due nodi, n1 o n2, non esiste deve essere restituita la lista iniziale non modificata.
        2. Si inserisca la funzione EstraiSottolista nel codice ListaBase.cpp ListaBase.c . Il main dovrà chiedere all'utente i due valori k1 e k2 , eseguire EstraiSottolista e poi stampare in output la sottolista estratta e la lista originale modificata.
        3. Si discuta la complessità degli algoritmi utilizzati in funzione della lunghezza della lista L. (inserirlo allafine del file .C come commento).

           Versione Semplificata: Non prevedere il caso in cui i nodi n1 o n2 non esistono.