ESERCIZI (RICORSIONE) - di-srv.unisa.it · array di n interi di interi positivi, dia in output TRUE...
12
ESERCIZI (RICORSIONE)
Transcript of ESERCIZI (RICORSIONE) - di-srv.unisa.it · array di n interi di interi positivi, dia in output TRUE...
ESERCIZI (RICORSIONE)
Esercizi
• Scrivere una funzione ricorsiva (in C) che calcoli la sommadegli elementi di un array A[1..n] di n interi.
• Soluzione:
Algoritmo ricorsivo
(Caso Base) Se l’array e vuoto (n=0) allora la somma deisuoi elementi e zero
(Passo generico) Se l’array [a1, . . . , an] non e vuoto allora lasomma dei suoi elementi e data da an piu la somma deglielementi di [a1, . . . , an−1].
Esercizi
• Scrivere una funzione ricorsiva (in C) che calcoli la sommadegli elementi di un array A[1..n] di n ≥ 1 interi.
• Soluzione:
int somma(int A[]; int n)
{
if (n=0) return 0
else return A[n] + somma(a, n-1)
end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamatericorsive.
Esercizi
• Scrivere un algoritmo ricorsivo per il calcolo del minimo in unarray A[1..n] di n interi positivi.
• Soluzione:Algoritmo ricorsivo
(Caso Base) Se l’array non e vuoto e ha un solo elemento a,allora a e il minimo elemento.
(Passo generico) Se l’array contiene [a1, . . . , an] e ha piu diun elemento, calcola il minimo degli elementi di[a1, . . . , an−1], sia min tale minimo.
Se an < min allora minimo = an, altrimenti minimo = min.
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi positivi, dia in output l’elemento minimo dellalista.
• Soluzione:
int minimo(int A[], int n)
if (n > 0) if [a[n] < minimo(a, n-1)) return A[n]
else return minimo(a, n-1)
end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamatericorsive.
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi di interi positivi, dia in output TRUE se 10 eun elemento della lista, FALSE altrimenti.
• Soluzione:Algoritmo ricorsivo
(Caso Base) Se l’array e vuoto allora 10 non e un elementodella lista
(Caso Base) Se l’array [a1, . . . , an] non e vuoto e a1 = 10,allora 10 e un elemento della lista.
(Passo generico) Se l’array [a1, . . . , an] non e vuoto ea1 6= 10, 10 e un elemento dell’array se e solo se 10 e unelemento di [a2, . . . , an].
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi di interi positivi, dia in output TRUE se 10 eun elemento della lista, FALSE altrimenti.
• Soluzione:
Boolean cerca10(int A[], int n):
begin
if (n=0) return FALSE
else if (A[n]=10) return TRUE
else return cerca10(L^.prossimo)
end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamatericorsive.Simulare su A = [2, 10, 7, 5], fornendo la sequenza delle chiamatericorsive.
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi di interi positivi, dia in output TRUE se tuttigli elementi sono maggiori di 10, FALSE altrimenti.
• Soluzione:Algoritmo ricorsivo
(Caso Base) Se l’array e vuoto allora tutti gli elementi dellalista sono maggiori di 10.
(Caso Base) Se l’array non e vuoto e se il primo elemento adell’array e minore o uguale a 10, allora non tutti gli elementidella lista sono maggiori di 10.
(Passo generico) Se l’array [a1, . . . , an] non e vuoto e sea1 > 10, tutti gli elementi della lista sono maggiori di 10 se esolo se tutti gli elementi della lista [a2, . . . , an] sono maggioridi 10.
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi di interi positivi, dia in output TRUE se tuttigli elementi sono maggiori di 10, FALSE altrimenti.
• Soluzione:
boolean tutti(int A[], int n)
if (n=0) return TRUE
else if (A[n] <= 10 ) return FALSE
else return tutti(A, n-1)
end
Esercizi
• Scrivere una funzione ricorsiva (in C) POT (n) per il calcolodei numeri F (n) definiti dalle seguenti relazioni:
F (1) = 2F (n) = 2F (n − 1) n ≥ 2
Soluzione:
int POT(int n)
{
if (n = 1) then return 2
else return 2*POT(n-1)
}
Esercizi
• Scrivere una funzione ricorsiva (in C) TIME (n) per il calcolodei numeri T (n) definiti dalle seguenti relazioni:
T (0) = 0, T (1) = 1T (n) = 2T (n − 2) + 5 n ≥ 2
Soluzione:
int TIME(int n)
{
if ( n = 0 ) return 0
else if (n = 1 ) return 1
else return 2 * TIME(n-2) + 5
}
Esercizi
• Scrivere una funzione ricorsiva (in C) che, avendo in input unarray di n interi non negativi, dia in output il numero deglielementi positivi della lista.
• Scrivere una funzione ricorsiva (in C) TIME (n) per il calcolodei numeri T (n) definiti dalle seguenti relazioni:
T (0) = 0, T (1) = 1T (n) = 2T (n − 2) + T (n − 1) n ≥ 2
