====== Esercitazione 7 ======
Esercizi su funzioni e procedure ricorsive e stdio.h
Gli esercizi sono tanti ma arrivate almeno fino al numero 10 (compreso).
Quando si ha a che fare con array in funzioni o procedure
ricorsive, si possono usare due metodi:
*il primo utilizza l'aritmetica dei puntatori per aggiornare ogni volta l'inizio dell'array,
*il secondo invece si porta dietro un indice per tenere traccia della posizione raggiunta.
Ad ogni modo e' sempre necessario portarsi dietro la dimensione (residua o totale, a seconda del caso).
Ricordate che oltre alla funzione o procedura indicata
dall'esercizio, si richiede che scriviate anche un main che usi
tale funzione e ne dimostri **ogni** funzionalita'.
Inoltre, se con l'esercizio viene fornita la firma della
funzione/procedura da scrivere, si richiede che la soluzione
rispetti questa firma in ogni dettaglio.
Ricordate infine che una procedura e' una funzione con tipo di
ritorno void.
=== Esercizio 1 ===
Scrivere una funzione **ricorsiva** potenza che riceva due interi,
base e esponente e ritorni il valore della base elevata alla
potenza esponente.
int potenza(int base, int esponente);
=== Esercizio 2 ===
Scrivere una funzione **ricorsiva** fattoriale che riceva un intero
e ritorni il fattoriale di quel valore.
int fattoriale(int val);
=== Esercizio 3 ===
Scrivere una procedura **ricorsiva** che riceva un array a lo
stampi a video.
Scrivere la procedura con i due metodi:
*con l'aritmetica dei puntatori
void stampa1 (int vet[], int dim);
*con un indice
void stampa2 (int vet[], int i, int dim);
=== Esercizio 4 ===
Modificare le procedure **ricorsive** dell'esercizio precedente per
stampare l'array in senso inverso.
void stampaInverso1 (int vet[], int dim);
void stampaInverso2 (int vet[], int i, int dim);
=== Esercizio 5 su stdio.h ===
Utilizzare la libreria stdio.h per creare un file misure che contenga 150 numeri interi
nell'intervallo (0,20] generati casualmente con la funzione rand(). I numeri devono essere scritti uno
per linea separati da '\n'.
=== Esercizio 6 su stdio.h ===
Utilizzare il file misure generato nell'esercizio precedente e calcolare il numero di valori generati
che ricadono nei 10 intervalli
(0, 2] (2,4] ..... (18,20]
stampare il numero dei valori per ciascun intervallo sullo standard output.
Suggerimento: progettare un ciclo che scorra gli intervalli e per ogni intervallo scorrere il file per trovare il numero dei valori che ricadano nell'intervallo preso in considerazione.
=== Esercizio 7 su stdio.h ===
Modificare l' esercizio precedente facendo stampare il numero dei valori per ogni intervallo in fondo al file con i dati.
=== Esercizio 8 ===
Scrivere una funzione che calcoli ricorsivamente il numero di
elementi pari di un array passato.
=== Esercizio 9 ===
Scrivere una funzione **ricorsiva** che controlli che l'array di caratteri
passato per argomento sia palindromo.
=== Esercizio 10 ===
Scrivere una funzione **ricorsiva** che azzeri tutti gli elementi
pari e ritorni il minimo elemento
di un array passato. Fare attenzione a memorizzare il valore di ritorno **prima** di modificarlo.
=== Esercizio 11 ===
Scrivere una funzione che chieda un valore N all'utente e
quindi calcoli ricorsivamente l'N-esimo termine della successione
di Fibonacci.
F(n) = F(n-1) + F(n-2)
=== Esercizio 12 ===
Scrivere una procedura ricorsiva che inverte la porzione di un
array individuata dagli indici from e to.
void inverti(int v[], int from, int to);
=== Esercizio 13 ===
La funzione di Ackermann e' una delle piu' semplici funzioni
totalmente computabili a non essere ricorsiva primitiva.
http://it.wikipedia.org/wiki/Funzione_di_Ackermann
In pratica, la funzione cresce piu' velocemente di qualsiasi
funzione ricorsiva primitiva (compreso qualsiasi esponenziale).
La funzione e' definita ricorsivamente per casi (sui naturali):
*A(m,n) = n+1 (se m=0)
* A(m,n) = A(m-1,1) (se m>0 e n=0)
*A(m,n) = A(m-1, A(m, n-1)) (se m>0 e n>0)
Scrivere una funzione che calcoli la funzione di Ackermann.
unsigned long Ackermann(unsigned long m, unsigned long n);
Quanto vale Ackermann(3,10)? Quanto vale Ackermann(4,1)?
Quanto tempo ci mette a calcolare questi valori?
Avvertenza: non andate oltre questi limiti (soprattutto su m) o
l'esecuzione
potrebbe non terminare in tempo per il fine settimana...
=== Esercizio 14 ===
Scrivere una procedura ricorsiva che riceva un array di
caratteri e stampi la prima meta' su una riga e la seconda meta'
sulla riga sottostante.
Se l'array ha un numero dispari di elementi, la lettera centrale
dovra' essere stampata su una riga a parte, tra la prima meta' e
la seconda meta'.
void stampaSuDueRighe(char vet[], int dim)
=== Esercizio 15 ===
Riuscite a scrivere la funzione fibonacci ottimizzando
(riducendo al minimo) il numero di chiamate ricorsive?
*Suggerimento 1: Per verificare quante chiamate vengono eseguite,
usate una variabile globale che viene incrementata ad ogni
chiamata.
*Suggerimento 2: potete sfruttare il fatto che per calcolate F(n-1)
dovete sapere F(n-2)?
*Suggerimento 3: una funzione in C non puo' ritornare piu' di un
valore ma se riceve dei puntatori puo' modificare i valori delle
variabili originali.
=== Esercizio 16 ===
Scrivere una funzione che ricevuto un array di interi, calcoli
e stampi ricorsivamente tutte le permutazioni dell'array.