Corso di Informatica 1 (IN110)

Gli esercizi

Testi e soluzioni di alcuni esercizi

È possibile scaricare un documento (in formato Adobe Acrobat PDF) con i testi e le soluzioni degli esercizi di esonero e di esame delle precedenti sessioni: Esercizi d'esameScarica il documento in formato PDF (aggiornato al 19/2/2003). Per visualizzare il documento o per stamparlo è necessario utilizzare il software Adobe Acrobat Reader™, disponibile gratuitamente su Internet sul sito della Adobe all'indirizzo http://get.adobe.com/reader/ (sono disponibili le versioni per tutte le principali piattaforme hardware/software).

È anche disponibile un breve documento con una introduzione sintetica alle caratteristiche principali del linguaggio C, Cenni sul linguaggio CScarica il documento in formato PDF 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 algoritmiScarica il documento in formato PDF.

È disponibile una raccolta di esercizi sulle liste e sui grafiScarica il documento informato PDF, 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":

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. In alternativa è possibile scaricare dalla rete Internet il compilatore LCC per Windows: http://www.cs.virginia.edu/~lcc-win32/.

È 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 xn 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:

U0 = x
U1 = y
Un+2 = Un+1 + Un

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 an-k/bnk.
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-bk/an-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 nxn è 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 8x8 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: b0 = a0, bi = bi-1 + ai se ai è pari, bi = bi-1 - ai se ai è 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 10x15, 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).
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.
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.
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 {x1, x2, ..., xn}. Letto in input un intero X (X > xi per ogni i=1,...,n) ripartire la lista L in k sotto-liste L1, L2, ..., Lk 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 (x1,y1), (x2,y2), ..., (xn,yn) tali che xi<yi per ogni i=1,...,n; ogni coppia (xi,yi) rappresenta un intervallo sulla retta. Riordinare gli elementi della lista in modo tale che x1 <= x2 <= ... <= xn. 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 xi=yi oppure xi>yi) 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è (Si,Si+1) ∈ E(G) per i=0, 1, ..., n-2).
Author: Marco Liverani - Last modified: Friday December 23, 2016 - URI: http://www.mat.uniroma3.it/users/liverani/IN110/esercizi.shtml