Gli esercizi

Esercizi di esonero e di esame

È 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: ESAMI.PDF (in preparazione). Per leggere il documento o per stamparlo su carta è necessario utilizzare il software Adobe Acrobat Reader, disponibile gratuitamente su Internet sul sito della Adobe all'indirizzo http://www.adobe.com/products/acrobat/alternate.html (sono disponibili le versioni per tutte le principali piattaforme hardware/software).

Esercizi introduttivi elementari

La seguente lista di esercizi di programmazione dati dal Prof. Liverani per il corso IN1, costituisce un ottimo banco di prova per chi intende esercitarsi nella programmazione in java.

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 SUM_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 SUM_k=0,...,n a-b^k/a^n-k.

Algoritmi 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 100 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-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)

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)

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 quot;[" 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 e' "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).

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)