Esercitazione 7

Procedure e Funzioni

Esercizio Scrivere un programma che memorizza in un array di elementi di tipo double le temperature relative al mese corrente e ne determina la temperatura massima, la temperatura minima e la temperatura media.

ALGORITMO

Scomponiamo il problema nei seguenti sottoproblemi più semplici:

scrivere una procedura leggitemperature che inizializza un array di double;scrivere una funzione massima che calcola il massimo elemento di un array di double;scrivere una funzione minima che calcola il minimo elemento di un array di double;scrivere una funzione media che calcola il valore medio di un array di double.

PROGRAMMA

#include <stdio.h>

/* procedura che inizializza un array generico di elementi di tipo doublecon i valori delle temperature inseriti dall’utente */

void leggitemperature (double temperature [ ], int dim) {

int i;for (i=0; i<dim; i++){

printf (“inserisci la temperatura del giorno %d” ”, i+1);scanf(“%lf”, &temperature[i]);

}} /* fine procedura leggitemperature */

/* procedura che calcola il maggiore di un array generico di double */

double massima (double arr [ ], int n) { int i;double max = arr [0];for (i=1; i<n; i++)

if (arr [i] > max) max = arr [i];

return max; }

/* procedura che calcola il minore di un array generico di double */

double minima (double arr [ ], int n) { int i;double min = arr [0];for (i=1; i<n; i++)

if (arr [i] < min) min = arr [i];

return min; }

/* procedura che calcola la media di un array generico di double */

double media (double arr [ ], int n) { int i;double media;

media = arr[0];for (i=1; i<n; i++)

media += arr[i];media /= n;

return media; }

/* funzione principale main */#define N 31main ( ) {

int n;double max, min, med;double temperature [N];

printf (“TEMPERATURE DEL MESE CORRENTE \n\n”);printf (“Inserisci il numero di giorni del mese corrente: ”);scanf(“%d”, &n);

leggitemperature (temperature, n); /* invocazione di procedura */max = massima (temperature, n); min = minima (temperature, n);med = media (temperature, n);

printf (“Massima= %lf, Minima=%lf, Media=%lf\n”, max, min, med);}

Esercizio

Scrivere una funzione che dato un array di elementi di tipo double contenente i valori delle temperature del mese corrente, restituisce il numero di giorni del mese in cui la temperatura è scesa sotto zero.

ALGORITMO

Scriviamo una funzione conta_giorni_sotto_zero che, dato un array arr di double e la sua dimensione dim, restituisce il numero di elementi dell’array che hanno valore strettamente minore di 0.

/* definizione della funzione conta_giorni_sotto_zero */

int conta_giorni_sotto_zero (double arr [ ], int dim){

int i;int giorni_contati = 0;

for (i=0; i<dim; i++){

if (arr [i] < 0)giorni_contati++;

}return (giorni_contati);

}

Esercizio

Scrivere una procedura che memorizza in un array i numeri naturali multipli di 3 compresi tra 0 e N (cioè 0+3+6+9+ ...) e ne restituisca la somma.

int somma_terzi_numeri (int arr[ ], int dim, int N){

int i, j, somma;i = 0; j = 0; somma = 0;

while ((i <= N) && (j<dim)) {arr[j]=i;somma +=arr[j];i+=3; j++;

}return somma;

}

Le Torri di HanoiQuello delle Torri di Hanoi è un gioco che si svolge con tre palettie alcuni dischi di diametro differente con un foro al centro in mododa poter essere infilati nei paletti.Inizialmente i dischi sono tutti impilati a piramide sul primo paletto.Il disco più grande è in basso, il più piccolo in alto.

SCOPO DEL GIOCO

Lo scopo del gioco è quello di trasferire i dischi dal paletto di sinistra a quello di destra, senza mai mettere un disco su un altro di dimensione più piccola.

REGOLE DEL GIOCO

È possibile spostare un solo disco alla volta;tutti i dischi devono essere sempre infilati nei paletti.

STRATEGIA

La strategia consiste nel considerare uno dei paletti come origine e un altro come destinazione. Il terzo paletto sarà utilizzato come deposito temporaneo.

ALGORITMO

Supponiamo di avere n dischi, numerati dal più piccolo al più grande. Inizialmente sono tutti impilati nel paletto di sinistra.Il problema di spostare n dischi sul paletto di destra può esseredescritto in modo ricorsivo così:

Spostare i primi n-1 dischi dal paletto di sinistra a quello di centro.Spostare il disco n-esimo (il più grande) sul paletto di destra.Spostare i rimanenti n-1 dischi dal paletto di centro a quello di destra.

In questo modo il problema può essere risolto per qualsiasi valoredi n>0 (n=0 è la condizione di stop della ricorsione).

PROGRAMMA

Per programmare questo gioco indichiamo

il primo paletto (quello di sinistra) con Lil secondo paletto (quello di centro) con Cil terzo paletto (quello di destra) con R

Definiamo la procedura ricorsiva transfer, che trasferisce n dischida un paletto all’altro.

void transfer (int n, char from, char to, char temp) {

/* n indica il numero di dischi che si vuole trasferire, from indica il paletto di origine, to indica il paletto di arrivo e temp indica il paletto che viene usato per la sosta temporanea */

if (n > 0) {/* sposta n-1 dischi dall’origine alla sosta temporanea */

transfer (n-1, from, temp, to);

/* sposta il disco n-esimo dall’origine alla destinazione */printf (“Sposta il disco %d da %c a %c\n”, n, from, to);

/* sposta n-1 dischi dalla sosta temporanea alla destinazione*/transfer (n-1, temp, to, from);

}return;

}

/* programma principale per il gioco delle TORRI DI HANOI *//* realizzato con una procedura ricorsiva */

#include <stdio.h>

void transfer (int n, char from, char to, char temp);

main ( ) {

int n;printf (“Benvenuto nelle TORRI DI HANOI\n\n”);printf (“Quanti dischi ? ”);scanf (“%d”, &n);

transfer (n, ‘L’, ‘R’, ‘C’);}

Eseguendo il programma con n=3 si otterrà il seguente output:

Benvenuto nelle TORRI DI HANOI

Quanti dischi ? 3Sposta il disco 1 da L a RSposta il disco 2 da L a CSposta il disco 1 da R a CSposta il disco 3 da L a RSposta il disco 1 da C a LSposta il disco 2 da C a RSposta il disco 1 da L a R

Esercizio

Scrivere una funzione ricorsiva che calcoli la somma degli interi

pari tra 2 e N

PROGRAMMA

int SommaPari (int N) { if (N<2) return 0;

else if (( N%2) == 0) return N + SommaPari (N-2); else return SommaPari (N-1);

}

ESERCIZIO

Si consideri la seguente funzione F la cui specifica è data in modo ricorsivo (si supponga N intero):

F(N) = restituisce 1 se N <= 0, -1+4*F(N-1) + F(N-2), altrimenti.

Si scriva la funzione C che realizzerebbe tale specifica

SOLUZIONE: int F(int N) {

if (N<=0) return 1else return -1+4*F(N-1) + F(N-2);

}

EsercizioScrivere una procedura ricorsiva che, dato un array di interi di lunghezza n, calcoli la somma dei suoi elementi.

Esempio

int a[1]; somma_ricorsiva(a, 1)=a[0];

int a[6]; somma_ricorsiva(a, 6)=somma_ricorsiva(a, 5) + a[5];

0 21 43 5

Soluzione 1

#include <stdio.h>#define DIM 10

int somma_ricorsiva (int a[ ], int dim) {if (dim == 1) return a[0];else return somma_ricorsiva (a, dim-1) + a[dim-1];

}

main ( ) {int sum;int mio_array [DIM];

inizializza_array (mio_array, DIM); /*supponiamo che questa procedura sia stata definita*/

sum = somma_ricorsiva (mio_array, DIM);}

Un’altra soluzione

Esempio

int a[1]; somma_ricorsiva(a, 0, 0)=a[0];

int a[6]; somma_ricorsiva(a, 0, 5)=a[0] + somma_ricorsiva(a, 1, 5);

0 21 43 5

inf supinf+1

Soluzione 2#include <stdio.h>#define DIM 10

int somma_ricorsiva (int a[ ], int inf, int sup) {if (inf == sup)

return a[inf];else

return a[inf] + somma_ricorsiva (a, inf+1, sup); }

main ( ) {int sum;int mio_array [DIM];

inizializza_array (mio_array, DIM); sum = somma_ricorsiva (mio_array, 0, DIM-1);

}

Inversione di una sequenza di caratteri

Scrivere un programma che legge una sequenza di caratteri terminata da \n in ingresso e la stampa invertita usando prima

una funzione iterativa void invertiInputIterativa (void)

e poi

una funzione ricorsiva void invertiInputRicorsiva (void).

Si usino le funzioni getchar e putchar.

#include <stdio.h>#define LUNGMAX 10

void invertiInputIterativa (void)/* Inverte una sequenza di caratteri letti in input. Versione iterativa */

{ char parola[LUNGMAX];int lung = 0;int i;char ch;

ch = getchar();while (ch != '\n' && lung < LUNGMAX){

/* lettura e memorizzazione in un array */parola[lung] = ch;lung++;ch = getchar();

}

for (i = lung-1; i >= 0; i--) /* stampa della sequenza invertita */putchar(parola[i]);

}

void invertiInputRicorsiva (void)/* Inverte una sequenza di caratteri letti in input. Versione ricorsiva */

{ char ch;

ch = getchar();if (ch != '\n') {invertiInputRicorsiva(); /* chiamata ricorsiva */putchar(ch); /* al ritorno dalla chiamata ricorsiva

} viene stampato il carattere letto */}

int main(void){ printf("Immetti una sequenza di caratteri (lunga al piu' %d)!\n", LUNGMAX);

invertiInputIterativa();

printf("\n Immetti una sequenza di caratteri (di lunghezza qualsiasi)!\n");invertiInputRicorsiva();putchar('\n');

}