Gli esercizi

Testi e soluzioni di alcuni esercizi

È disponibile un breve documento con una introduzione sintetica alle caratteristiche principali del linguaggio C, Cenni sul linguaggio C ed una guida di riferimento alle funzioni di libreria del linguaggio C (a cura di Eric Huss).

Come supporto didattico alla progettazione di algoritmi è possibile scaricare una nota con degli appunti introduttivi sugli algoritmi (progettazione, complessità, pseudo-codifica, diagrammi di flusso e codifica in linguaggio C): Appunti introduttivi sulla progettazione degli algoritmi.

È disponibile una raccolta di esercizi sulle liste e sui grafi, utile per la preparazione della seconda prova d'esonero e delle prove scritte d'esame.

Esercizi svolti durante le esercitazioni in laboratorio e gli incontri di "tutorato"

Esercitazioni: 10/10/2024 (esercizi introduttivi elementari); 17/10/2024 (operazioni sugli array: intersezione, differenza, inversione); 24/10/2024 (verifica della simmetria di una stringa, frequenza degli elementi in un array, colonna di una matrice con il maggior numero di elementi dispari); 31/10/2024 (esercizi su vettori di caratteri e su matrici: array di numeri casuali, riconoscimento di stringhe, trasformazione di stringhe in caratteri maiuscoli); 7/11/2024 (funzioni per la lettura e la scrittura di dati su file di testo, esercizio per la generazione di un file di dati da visualizzare graficamente con GNUplot; esercizi su array); 21/11/2024 (esercizi su vettori e matrici: inserimento degli elementi di un vettore al centro di un altro vettore; percorso su una matrice di numeri interi); 5/12/2024 (esercizi sulle liste: concatenazione di liste, fusione di liste, eliminazione degli elementi dispari); 9/12/2024 (esercizi sulle liste: compressione e decompressione di liste con l'algoritmo RLE - Run Length Encoding; stampa di sottoliste la cui media sia minore della media tra il minimo e il massimo della lista); 19/12/2024 (costruzione di un "grafo intervallo", costruzione di un grafo completo bipartito, calcolo del grado entrante dei vertici di un grafo orientato);
Tutorato: Esercizi introduttivi (esercizi di pseudo-codifica e disegno di diagrammi di flusso di algoritmi risolutivi per problemi elementari); 14/10/2024 (esercizi elementari con strutture di controllo iterative); 21/10/2024 (esercizi sugli array e sulle matrici); 28/10/2024 (esercizi sugli array e sulle matrici); 4/11/2024 (eliminazione di elementi da un vettore; verifica delle parentesi in un'espressione aritmetica, verifica sulle righe di una matrice); 18/11/2024 (caratteri doppi in una stringa, sotto-sequenza di elementi in ordine crescente, sotto-matrice di somma massima); 25/11/2024 (costruire una lista, a partire da un'altra, con tutti gli elementi che non siano numeri primi; inversione di una lista; fusione di due liste ordinate; ordinamento di una lista); 2/12/2024 (esercizi sui grafi: dato v∈V(G), stampare tutti i vertici u a cui v è adiacente; eliminare gli spigoli entranti in un vertice v del grafo G; data una lista L costruire una lista L' con i soli elementi maggiori della media); 12/12/2024 (verifica che il sottografo indotto da un insieme di vertici sia completo; completamento di una lista ordinata; verifica che un sottoinsieme di vertici di G sia una copertura di vertici per G; verifica che una sequenza di vertici rappresenti un cammino effettivo sul grafo); 16/12/2024 (completamento di una lista; eliminazione spigoli da un grafo; modifica del verso degli spigoli di un grafo); 19/12/2024 (eliminazione spigoli da un grafo, modifica del verso degli spigoli, sottografo indotto completo).

Per compilare e rendere eseguibili i programmi codificati in linuaggio C si suggerisce l'uso dell'ottimo compilatore C command line GCC di GNU inserito nell'ambito delle principali distribuzioni del sistema operativo Linux e, per i sistemi operativi Microsoft Windows, nell'ambito del prodotto open source Cygwin o Dev-C++.

In alternativa è possibile utilizzare la piattaforma di sviluppo ed esecuzione di programmi software on-line Repl.it dove è possibile scrivere programmi in C ed altri linguaggi, compilarli ed eseguirli on-line, mediante un web browser. È necessario creare un account sulla piattaforma registrandosi gratuitamente.

È possibile collegarsi via Internet al server del laboratorio didattico, in emulazione di terminale alfanumerico attraverso il protocollo SSH, per effettuare esercizi di programmazione C sul server del laboratorio. Per maggiori informazioni in merito è possibile fare riferimento agli appunti per l'uso del laboratorio Documento in formato PDF .

Esercizi elementari

Sommatoria: Calcolare la somma di n numeri interi letti in input.
Media aritmetica: Calcolare la media aritmetica fra n numeri interi letti in input.
Funzione per lo scambio: Legge in input due numeri interi, li memorizza in due variabili e poi, richiamando la funzione scambia, inverte i valori delle due variabili.
Potenze: Legge in input un numero floating point (x) ed un numero intero (n) e calcola la potenza xⁿ utilizzando un algoritmo iterativo, un algoritmo ricorsivo e le funzioni esponenziale e logaritmo naturale.
Fattoriale: Legge in input un numero intero (n) e stampa in output il suo fattoriale (n! = n×(n-1)×(n-2)× ... ×1) utilizzando una funzione iterativa ed una ricorsiva.
Multipli: Legge in input tre numeri interi positivi: x, y e z. Stampa in output i primi x multipli di y, riportandone z su ogni riga.
Massimo e minimo: Letto in input un intero n>0 ed n numeri floating point, stampa in output il massimo e il minimo.
Test di primalità: Letto in input un intero n>1, stabilisce se il numero è primo oppure no.
Numeri di Fibonacci: Letti in input due numeri floating point x ed y e un intero n, calcola l'n-esimo valore della successione di Fibonacci, definita come segue:

U₀ = x
U₁ = y
U_n+2 = U_n+1 + U_n
Somma di potenze: Legge in input un intero n ed un floating point x>0 e calcola la somma delle potenze di x, da 0 ad n.
Somma di rapporti: Legge in input un intero n e due numeri floating point a e b e stampa in output la somma Σ_k=1,...,n a^n-k/b^nk.
Somma di rapporti (bis): Legge in input un intero n e due numeri floating point a e b e stampa in output la somma Σ_k=0,...,n a-b^k/a^n-k.
Grafici di funzione con GNUplot: Calcola le coordinate sul piano dei punti di una funzione in un intervallo e visualizza il grafico della funzione richiamando il programma GNUplot.

Esercizi su array e matrici

Lettura e stampa di array: Legge in input n numeri floating point, li memorizza in un array e li stampa in output in ordine inverso rispetto a quello di lettura.
Generazione casuale di array: Genera una sequenza casuale di n numeri interi, li memorizza in un array e li stampa.
Lettura e stampa di una matrice: Legge in input una matrice di n righe ed m colonne e la stampa.
Riga di somma massima in una matrice: Leggere in input una matrice di interi (n righe ed m colonne). Stampare l'indice della riga di somma massima.
Quadrato "magico": Generare una matrice quadrata di dimensione n di numeri interi casuali. Scrivere una funzione che restituisca 1 se la matrice è un quadrato magico e zero altrimenti. Una matrice n×n è un quadrato magico se la somma degli elementi su ogni riga, su ogni colonna e sulle due diagonali principali è costante.; (Primo esercizio della prova scritta di esame del 5 febbraio 1999 - a.a. 1998/99)
Cavalli e regine: Su una scacchiera (matrice quadrata di 8×8 elementi) sono disposti in modo casuale due cavalli neri, una regina nera ed n ≤ 16 pezzi bianchi. Scrivere una funzione che calcoli il numero di possibili mosse dei pezzi neri che consentono di mangiare un pezzo bianco.
Numeri primi: Stampa i numeri primi minori di n utilizzando il "Crivello di Eratostene".
Successione con pari e dispari: Leggere in input una sequenza A di numeri interi. Stampare in output la successione B calcolata secondo la seguente regola: b₀ = a₀, b_i = b_i-1 + a_i se a_i è pari, b_i = b_i-1 - a_i se a_i è dispari.; (Primo esercizio della prova di esonero del 4 aprile 2001 - a.a. 2000/2001)
Terne consecutive: Genera in modo casuale una matrice di numeri interi minori di 10. Stampa le colonne che contengono tre elementi consecutivi che abbiano valori successivi.
Prodotto di quaterne: Generare in modo casuale un array di numeri interi minori di 200. Stampare in output le quaterne consecutive il cui prodotto sia minore della media di tutti gli elementi del vettore.
Triangolo di Tartaglia: Letto in input un intero n stampa in output la n-esima riga del triangolo di Tartaglia.
Matrici incastrate: Generare in modo casuale una matrice A di ordine 10×15, con valori interi 0 e 1. Sia B la seguente matrice quadrata di ordine 3:; | 0 1 0 | B = | 1 1 1 | | 0 1 0 |; Verificare se in A è possibile collocare B in modo tale che nessun elemento di valore 1 di B si vada a sovrapporre ad un elemento di valore 1 in A. In caso affermativo stampare le coordinate di riga e di colonna in A in cui verrebbe collocato l'elemento B(0,0).; (Primo esercizio della prova di esame del 15 giugno 2001 - a.a. 2000/2001)
Classifica del campionato: Leggere in input una matrice di n×m numeri interi, ognuno dei quali può valere soltanto 0, 1 o 2. Ogni riga della matrice rappresenta i punti acquisiti dalle squadre di calcio nelle partite disputate nelle diverse giornate del campionato: 2 punti per le partite vinte, 1 punto per quelle pareggiate e 0 punti per le sconfitte. I risultati della giornata k-esima sono contenuti nelle righe della colonna di indice k. Per ogni giornata del campionato si stampi l'indice (il numero di riga corrispondente) della squadra capolista.
Scrittura su file: Letta in input una sequenza di numeri interi la memorizza in un array e la salva su un file.
Compressione RLE: Leggere in input una sequenza di numeri interi e memorizzarla in un array V. Stampare in output la stessa sequenza compressa con l'algoritmo RLE (Run Length Encoding).
Inserimento nella sequenza ordinata: Leggere in input una sequenza di n numeri interi e memorizzarla in un array A. Si supponga che la sequenza letta in input sia già ordinata in ordine crescente. Generare in modo casuale una seconda sequenza di m numeri interi ed inserire gli elementi generati nella posizione corretta nell'array A in modo che A continui ad essere ordinato, eventualmente spostando in avanti gli elementi già presenti per fare posto ai nuovi elementi da inserire. Stampare in output l'array A.; (Secondo esercizio della prova scritta di esonero del 4 aprile 2001 - a.a. 2000/2001)
Parole palindrome: Letta in input una parola verifica se è palindroma.
Selection sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Selection sort.
Insertion sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Insertion sort.
Bubble sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Bubble sort.
Quick sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Quick sort.
Merge sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Merge sort.
Heap sort: Ordina una sequenza di n numeri interi letti in input, memorizzati in un array, utilizzando l'algoritmo Heap sort.
Sottosequenze approssimate: Leggere in input 20 sequenze di numeri interi non negativi minori di 5, di lunghezza variabile, ma con al massimo 100 elementi. Leggere quindi in input due numeri interi h e k e generare in modo casuale un'altra sequenza S, composta da k interi non negativi minori di 5. Stampare in output le sequenze che contengono la sequenza S, a meno di h elementi al massimo.; (Primo esercizio della prova scritta di esame del 6 Luglio 2001 - a.a. 2000/2001)
Percorso sulla matrice: Leggere in input una matrice rettangolare A (100x10), composta da numeri 0 e 1. Verificare se esiste una sequenza di elementi di valore 1 adiacenti tali che si possa individuare un percorso sulla matrice dalla prima all'ultima riga, spostandosi sempre da un elemento di valore 1 ad un altro adiacente, senza mai tornare su righe già percorse in precedenza.; (Secondo esercizio della prova scritta di esame del 7 settembre 2001 - a.a. 2000/2001)
Matrici quadrate: Costruire in modo casuale una matrice M di numeri interi con n righe ed m colonne (n ed m forniti in input dall'utente). Stampare tutte le matrici quadrate contenute in M.; (Secondo esercizio della prova scritta di esame del 14 settembre 2001 - a.a. 2000/2001)
Sotto-array di somma massima: Leggere in input una sequenza A di n numeri floating point ed un numero intero k<n. Stampare in output la sequenza di k elementi contigui la cui somma sia massima.; (Primo esercizio della prova di esonero del 9 novembre 2001 - a.a. 2001/2002)
Somma con riporto: Leggere in input una matrice A di nxm numeri interi compresi tra 0 e 9. Ogni riga della matrice rappresenta un numero intero positivo costituito da m cifre, eventualmente riportando, a sinistra, degli zeri per numeri con meno di m cifre. Calcolare la somma dei numeri e riportarne le cifre (numeri compresi tra 0 e 9) su un vettore B. Stampare B.; (Secondo esercizio della prova di esonero del 9 novembre 2001 - a.a. 2001/2002)

Algoritmi su liste e grafi

Costruzione di una lista ordinata: Letta in input una sequenza di n numeri interi costruisce una lista ordinata in ordine crescente.
Eliminazione degli elementi dispari da una lista: Letta in input una sequenza di n numeri interi costruisce una lista. Elimina dalla lista tutti gli elementi dispari.
Somma di sotto liste: Letta in input una sequenza di numeri floating point la memorizza su una lista. Quindi stampa tutte le sotto-liste (prive di intersezione) in cui la somma degli elementi sia minore della media tra l'elemento massimo e minimo dell'intera lista.
Derivata di un polinomio con liste: Leggere in input un polinomio a coefficienti reali e memorizzarlo in una lista costituita da nodi con tre campi (grado, coefficiente, puntatore al seguente). Scrivere un programma che dopo aver costruito una seconda lista che rappresenta il polinomio derivato di quello fornito in input, ne stampi l'espressione sullo schermo.; (Primo esercizio della prova di esonero del 5 giugno 2001 - a.a. 2000/2001)
Trasformazione della matrice di adiacenza di un grafo nelle liste di adiacenza equivalenti: Letto in input un grafo G(V,E), lo memorizza utilizzando una matrice di adiacenza M; quindi costruisce le liste di adiacenza per la rappresentazione dello stesso grafo G.
Trasformazione delle liste di adiacenza di un grafo nella matrice di adiacenza equivalente: Letto in input un grafo G(V,E) lo memorizza utilizzando le liste di adiacenza; quindi costruisce la matrice di adiacenza equivalente per la rappresentazione dello stesso grafo G.
Ordinamento di una lista mediante bubble sort: Letta in input una sequenza di numeri interi, la memorizza in una lista; quindi ordina la lista utilizzando l'algoritmo di bubble sort.
Stringhe ben parentesizzate: Si consideri un linguaggio nel quale si dispone di tre paia di parentesi, utilizzate per delimitare parti di testo (come ad esempio le parentesi graffe e tonde nel linguaggio C). Si supponga che queste tre paia di parentesi siano le parentesi tonde "(" e ")", le parentesi quadre "[" e "]" e le parentesi graffe "{" e "}". Si scriva un programma che chiede in input una stringa, ne memorizza i singoli caratteri in una lista e verifica se la stringa digitata inizialmente è "ben parentesizzata".; (Secondo esercizio della prova di esonero del 5 giugno 2001 - a.a. 2000/2001)
Costruzione del grafo complementare: Letto in input un grafo lo rappresenta mediante liste di adiacenza. Quindi, senza passare attraverso una rappresentazione con matrici di adiacenza, costruisce le liste di adiacenza del grafo complementare G'.
Visita in ampiezza di un grafo: Algoritmo BFS (Breadth First Search) per la visita in ampiezza di un grafo generico espresso mediante liste di adiacenza.
Visita in profondità di un grafo: Algoritmo DFS (Depth First Search) per la visita in profondità di un grafo generico espresso mediante liste di adiacenza.
Foglie di un albero con radice: Letto in input un albero con radice (orientato) rappresentarlo mediante liste di adiacenza. Stampare in output le sue foglie.
Profondità di un albero con radice: Letto in input un albero con radice (orientato) rappresentarlo mediante liste di adiacenza. Stampare in output la sua profondità massima.
Grado dei vertici di un grafo: Letto in input un grafo orientato, rappresentarlo mediante liste di adiacenza. Stampare in output il grado entrante ed uscente di ogni vertice del grafo.
Flussi di denaro: I flussi di denaro tra le filiali di una banca sono rappresentati mediante un grafo orientato. I vertici del grafo rappresentano le diverse filiali e lo spigolo orientato v(i) --> v(j) indica che c'è un flusso dalla filiale v(i) alla filiale v(j). La quantità di denaro trasferito è rappresentata mediante numeri interi positivi associati agli spigoli del grafo. Dopo aver rappresentato il grafo con liste di adiacenza costituite da record con tre campi (il numero della filiale, il flusso trasferito verso tale filiale ed il puntatore all'elemento successivo), si stampi l'elenco delle filiali che al termine degli spostamenti di denaro hanno aumentato il proprio capitale.; (Secondo esercizio della prova di esame del 15 giugno 2001 - a.a. 2000/2001)
Minimum Spanning Tree: Algoritmo di Kruskal per la costruzione del minimo albero ricoprente di un grafo G=(V,E); ad ogni spigolo (u,v) di E è associato un peso positivo w(u,v).
Cammino minimo da sorgente singola: Codifica dell'algoritmo di Dijkstra per calcolare i cammini minimi per raggiungere ogni vertice del grafo G a partire dalla sorgente s. Il grafo G=(V,E) è connesso e orientato e ad ogni spigolo (u,v) di E è associato un peso non negativo w(u,v).
Partizione di una lista: Leggere una lista L di interi {x₁, x₂, ..., x_n}. Letto in input un intero X (X > x_i per ogni i=1,...,n) ripartire la lista L in k sotto-liste L₁, L₂, ..., L_k tali che la somma degli elementi di ogni sotto-lista sia minore o uguale ad X e che tale somma sia massimale (l'aggiunta di un elemento ulteriore ad ogni sotto-lista, tranne al più l'ultima, fa superare la soglia X). Stampare le sotto-liste generate.; (Primo esercizio della prova di esonero del 27 gennaio 1999 - a.a. 1998/99)
Eliminazione di intersezioni fra intervalli: Leggere una lista di coppie di numeri interi (x₁,y₁), (x₂,y₂), ..., (x_n,y_n) tali che x_i<y_i per ogni i=1,...,n; ogni coppia (x_i,y_i) rappresenta un intervallo sulla retta. Riordinare gli elementi della lista in modo tale che x₁ <= x₂ <= ... <= x_n. Costruire una nuova lista che rappresenti gli intervalli della prima lista, ma privi di intersezioni (fatta eccezione per gli estremi degli intervalli); gli eventuali intervalli nulli (tali che x_i=y_i oppure x_i>y_i) prodotti dalla rielaborazione degli intervalli originali devono essere eliminati.; (Secondo esercizio della prova di esonero del 27 gennaio 1999 - a.a. 1998/99)
Spese e mesi dell'anno: Riceviamo in input una sequenza di recordo che indicano l'importo di una certa spesa ed il periodo dell'anno in cui è stata compiuta (mese iniziale e mese finale). Dopo aver memorizzato tutte le informazioni lette in input in una struttura dati dinamica, calcolare l'importo delle spese per ogni mese dell'anno, senza fare uso di array o matrici. Stampare i mesi e l'importo della spesa relativa in ordine decrescente di spesa.; (Secondo esercizio della prova scritta di esame del 5 febbraio 1999 - a.a. 1998/99)
Sorgenti e pozzi di un grafo: Leggere in input un grafo orientato G = (V,E) e rappresentarlo mediante liste di adiacenza. Implementare una funzione che stampi tutti i vertici "sorgente" e tutti i vertici "pozzo" di G. Un vertice v è una sorgente se ha solo spigoli uscenti e nessuno spigolo entrante; è un pozzo se ha solo spigoli entranti e nessuno spigolo uscente.; (Primo esercizio della prova scritta di esame del 23 febbraio 1999 - a.a. 1998/99)
Eliminazione di un vertice: Leggere in input un grafo orientato G = (V,E) e rappresentarlo mediante una matrice di adiacenza. Dato un vertice v verificare che abbia un solo predecessore (in altri termini, che esista uno ed un solo vertice u di G tale che (u,v) sia uno spigolo di G). In tal caso costruire il grafo G' mediante liste di adiacenza, ottenuto da G collegando il predecessore di v a tutti i successori di v stesso e sconnettendo dal grafo il vertice v.; (Secondo esercizio della prova scritta di esame del 23 febbraio 1999 - a.a. 1998/99)
Costruzione di un heap: Letta in input una sequenza di numeri interi memorizzarla in una lista. Costruire un heap composto dagli elementi della lista, utilizzando come peso la frequenza di ognuno degli elementi. L'heap deve essere costruito facendo uso di un array o di una matrice. Stampare l'heap.; (Primo esercizio della prova scritta di esame del 7 settembre 2001 - a.a. 2000/2001)
Ciclo hamiltoniano: Leggere in input un grafo orientato G=(V,E) ed una sequenza S di vertici di G. Verificare se S è un ciclo hamiltoniano, ossia un ciclo semplice in G che consente di raggiungere tutti i vertici di G. Il grafo G deve essere rappresentato utilizzando la struttura dati delle liste di adiacenza, la sequenza S deve essere rappresentata mediante una lista.; (Primo esercizio della prova scritta di esame del 14 settembre 2001 - a.a. 2000/2001)
Verifica di un cammino su un grafo: Leggere in input un grafo G=(V,E) con n vertici (V = {0, 1, 2, 3, ..., n-1}) e rappresentarlo mediante liste di adiacenza; generare una sequenza di k numeri casuali minori di n e memorizzarla nel vettore S. Stampare le liste di adiacenza del grafo e la sequenza S. Verificare che gli elementi di S rappresentino un cammino su G (cioè (S_i,S_i+1) ∈ E(G) per i=0, 1, ..., n-2).

Corso IN110 Algoritmi e Strutture Dati