{n = numero righe, m = numero colonne}
for i:=1 to n do {IC1: 1<=i<=n+1,
c[(1..i-1),(1..m)]=a[(1..i-1),(1..m)]+b[(1..i-1),(1..m)]}
for j:=1 to m do {IC2: 1<=j<=m+1,
c[(i..i),(1..j-1)]=a[(i..i),(1..j-1)]+b[(i..i),(1..j-1)]}
c[i,j]=a[i,j]+b[i,j];
Ricordiamo che la posizione "standard" per il predicato che rappresenta
l'IC per un ciclo 'for' e` subito prima dell'esecuzione del corpo del ciclo
stesso, ovvero, in parole povere, l'IC deve esprimere una proprieta` che
e` vera PRIMA che il valore dell'indice corrente sia usato.
Prendiamo l'invariante del primo ciclo IC1. A parole, essa esprime "per ciascuna riga i della matrice c, andiamo a riempire tutte le sue caselle con la somma delle rispettive caselle di a e di b, dalla colonna 1 alla colonna m'. Quando i=1, l'invariante e` (basta sostituire nel primo predicato IC1 il valore 1 a 'i'):
c[(1..0),(1..m)]=a[(1..0),(1..m)]+b[(1..0),(1..m)]
ed esprime (siccome non ci sono righe da 1 a 0) che nessuna riga e` stata ancora riempita: infatti a i e` stato assegnato 1 ma i=1 non e` ancora stato usato perche' stiamo scrivendo l'IC per la posizione standard del 'for', e quindi il secondo 'for' non e` ancora stato eseguito. Quando i=2, l'invariante e`:
c[(1..1),(1..m)]=a[(1..1),(1..m)]+b[(1..1),(1..m)]
ed esprime che la prima riga (cioe` tutte le righe da 1 a 1, scritto con (1..1)) e` stata riempita (ricordiamo che il corpo del primo 'for' e` proprio il secondo 'for', il quale si occupa esattamente di riempire una riga, dato l'indice 'i' della riga stessa). Cosi', via via, si arriva a i=n, e l'invariante in questo caso sara':
c[(1..n-1),(1..m)]=a[(1..n-1),(1..m)]+b[(1..n-1),(1..m)]
ad esprimere che tutte le righe fino alla (n-1)-esima sono state riempite. Quando i=n+1 e` come se eseguissimo solo l'intestazione del 'for', che virtualmente provvede a fare il test e a uscire dal ciclo. Ancora una volta l'invariante esprime una proprieta` corretta:
c[(1..n),(1..m)]=a[(1..n),(1,m)]+b[(1..n),(1..m)]}
dicendo che tutte le righe da 1 a n della matrice sono state riempite. Consideriamo ora l'invariante del secondo ciclo IC2. Il secondo 'for' si occupa, data una riga 'i', di riempire tutte le caselle da (i,1) a (i,m). E` per questo che il parametro delle righe resta costante (notazione (i..i)) per tutte le j tra 1 e m. Abbiamo poi fatto un discorso analogo a quello per l'invariante IC1, considerando i casi j=1, j=2, j=m, j=m+1.
Un utile esercizio e` quello di provare a scrivere due altri predicati IC1' e IC2' per i due cicli, che valgono DOPO l'esecuzione dei rispettivi corpi, ovvero scrivere le invarianti che sono vere DOPO che l'indice corrente e` stato usato (IC1': dopo l'esecuzione del ciclo 'for' interno; IC2':dopo l'esecuzione dell'assegnamento). Siccome questo esercizio richiede un po' di pratica con gli invarianti, la soluzione verra` fornita piu' avanti, ma solo se richiesta, in una pagina a se'. Ribadiamo che comunque l'invariante da scrivere in un eventuale esercizio all'esame e` quella standard, ovvero quella studiata piu' sopra per esteso.
program ricorsivita;
var n:integer;
procedure scrivi_al_contr1(n:integer);
begin
if n>=0 then
begin
writeln(n);
scrivi_al_contr1(n-1);
end
end;
procedure scrivi_al_contr2(n:integer);
begin
if n<0 then writeln
else
begin
write(n);
scrivi_al_contr2(n-1);
end
end;
procedure scrivi_diritto1(n:integer);
begin
if n>=0 then
begin
scrivi_diritto1(n-1);
writeln(n);
end
end;
procedure scrivi_diritto2(n:integer);
begin
if n<0 then writeln
else
begin
scrivi_diritto2(n-1);
write(n);
end
end;
procedure scrivi_diritto3(n:integer);
begin
if n>=0 then
begin
scrivi_diritto3(n-1);
write(n);
end
end;
procedure chiama_sd3(n:integer);
begin
scrivi_diritto3(n);
writeln;
end;
begin {main}
writeln('inserisci il numero da stampare:');
readln(n);
chiama_sd3(n); {questa procedura chiama la 'scrivi_diritto3', che stampa
i numeri su una riga in ord cresc, e poi fa una 'writeln'
per mandare il cursore a capo}
end.
La prima procedura 'scrivi_al_contr1', dato 'n', stampa su video la sequenza di
numeri:
n
n-1
...
1
0
La seconda, 'scrivi_al_contr2', dato 'n', stampa a video la sequenza di numeri:
n n-1 ... 1 0
e va capo con il cursore (grazie alla 'writeln' che viene eseguita quando il parametro risulta essere <0, che e` il "caso base" di questa ricorsione). La terza, 'scrivi_diritto1', stampa a video la sequenza:
0
1
...
n-1
n
ed e` semplicemente come la 'scrivi_al_contr1', ma con la chiamata ricorsiva e la 'writeln(n)' scambiate, in modo da stampare la sequenza in ordine crescente. Il problema nasce se vogliamo ottenere la sequenza in ordine crescente con l'effetto della 'scrivi_al_contr2', ovvero con i numeri sulla stessa riga e una writeln alla FINE. Se modifichiamo la 'scrivi_al_contr2' in modo ingenuo, ottendo la 'scrivi_diritto2', non otteniamo l'effetto voluto, poiche' il 'writeln' del caso base verra` eseguito PRIMA della stampa dello 0 e non dopo la stampa di n.
Abbiamo visto che, infatti, l'avere la chiamata ricorsiva prima della 'writeln(n)' implica l'esecuzione della 'writeln(n)' al ritorno della chiamata ricorsiva, ovvero quando "stiamo risalendo" verso le chiamate ricorsive piu' esterne, fino alla prima chiamata della procedura (a lezione abbiamo simulato queste procedure a mano, avvalendoci dei record di attivazione, provate a rifarlo se non vi e` chiaro).
Una possibile soluzione al nostro problema e` allora la procedura 'chiama_sd3', che chiama, a sua volta, la procedura ricorsiva 'scrivi_diritto3' (la quale stampa i numeri su una riga in ordine crescente) e poi fa una 'writeln' per mandare il cursore a capo. Essa restituisce:
0 1 ... n-1 n
(prima istruzione di 'chiama_sd3'=chiamata a 'scrivi_diritto3'), e poi va a capo con il cursore (seconda istruzione di 'chiama_sd3'='writeln').
- Scrivere una procedura ricorsiva che, dato n>=1, calcoli e stampi a video le componenti della serie armonica 1/n, troncata all'n-esimo elemento (es. con n=5: 1, il valore di 1/2, il valore di 1/3, ... fino a 1/5).
- Scrivete una funzione ricorsiva che, dato n>=1, calcoli la somma della serie 1/2^n (leggere come: "1 fratto 2 alla n") troncata a n, e stamparne il risultato. Per n sufficientemente grande, la somma converge a...
- Date le dichiarazioni di record e array
type famiglia = record
nomepadre,nome: char
end;
const max=100;
type arrfam = array [1..max] of famiglia;
scrivere una procedura (o funzione, scegliete voi la piu' adatta) ricorsiva che,
dati un parametro 'nm' di tipo carattere rappresentante un nome,
e un intero 'a', ritrovi l'a-esimo antenato di 'nm' (con la convenzione che
a=1 richiede di trovare il padre di 'nm', a=2 il nonno, etc).
Ad esempio, se nell'array abbiamo |c.p|b.c|k.b|f.g|, e nm=p e a=2, l'output
deve essere 'b' (ovvero il padre del padre di p). Ovviamente questa
procedura/funzione dovra` essere opportunamente inserita in una unit che
permetta anche l'inserimento e la stampa dell'array. Inoltre, cercate di
prevedere tutti i possibili casi in cui la procedura/funzione potrebbe
dare errore e trattate questi casi di conseguenza.
Soluzioni (Non ancora presenti)