C invarianti di ciclo
Come dobbiamo ragionare per verificare che un algoritmo che adoperi un loop sia stato scritto in modo corretto?
L’espressione booleana tra parentesi che segue la parola riservata while è detta condizione di ingresso:
• se tale condizione risulta verificata il corpo del loop deve essere ripetuto
• allorché è falsa il controllo passa alla istruzione immediatamente successiva all’istruzione while.
Esempio: Supponiamo che dato un intero n si voglia calcolare il prodotto di tutti i numeri da uno fino ad n (anche detto Fattoriale di n e scritto come n!).
Avremo:
while(cond) i¬i+1
prodotto¬prodotto*i
La condizione di uscita dal loop è i=n e la condizione di ingresso , che è la negata della condizione di uscita, sarà: i¹n.
Avremo:
while(i¹n) i¬i+1
prodotto¬prodotto*i
C invarianti di ciclo
Invariante di ciclo
Serve a dimostrare la correttezza di un ciclo:
Inizializzazione: la condizione è vera all'inizio del ciclo
Conservazione: se la condizione è vera prima di una iterazione del ciclo, allora rimane vera al termine (quindi prima della successiva iterazione)
Conclusione: Quando il ciclo termina, l'invariante deve rappresentare la
“correttezza” dell'algoritmo
C invarianti di ciclo
Esempio:
il fattoriale: dato n intero calcolate n! = 1´2 ´ … ´ n
Le due variabili i e prodotto devono essere inizializzate prima dell’enunciato while.
Ovviamente prodotto deve essere inizializzato ad 1 ed anche i deve avere lo stesso valore.
Possiamo dire che al termine di ogni passo i è dato da 1 più il numero di passi effettuati nel loop e prodotto è il prodotto dei primi i numeri.
All’uscita definitiva dal loop i deve valere n e prodotto conterrà esattamente il prodotto dei primi n numeri.
L’invariante di loop è data da:
prodotto= prodotto dei primi i numeri
leggi(n) i
ß1
prodotto
ß1 while (i
£n):
prodotto
ßprodotto * i i
ßi + 1
stampa(fatt) (prodotto=1 ´ 2 ´ … ´ i) and (1 £ i £ n+1)
Invariante di ciclo
Algoritmo
Esempio
Definire un metodo statico che legga da consolle una sequenza di n interi avente almeno un elemento e ne scriva sullo schermo il massimo.
Risoluzione: Devo costruire un ciclo all'uscita del quale nella variabile max sia contenuto il massimo.
Per far ciò, al generico passo la variabile max deve contenere il massimo dei valori immessi fino a quel momento.
Assumendo che ciò sia vero per effetto dei passi precedenti e assumendo che la condizione (i<=n) sia vera e che quindi io debba eseguire il corpo del ciclo, che cosa devo fare nel corpo del ciclo?
1. leggere un nuovo intero: x;
2. se è maggiore di max sostituirlo a max,
altrimenti non far nulla: if(x > max) max = x;
Esempio
Inizializzazione.
Inizialmente, cioè prima di entrare nell'istruzione while, bisogna aver letto un intero, e tale intero è ovviamente il massimo:
int max = x;
In conclusione, il ciclo che risolve il problema è:
Leggi(x);
int max = x;
i=2;
while(i<=n) { leggi(x);
if(x > max) max = x;
i++;
}
Nell'esempio precedente l'invariante è: La variabile max contiene il
massimo dei valori immessi finora.
Come NON creare un ciclo
Se, nell'ideare un ciclo, si pensa subito al "primo passo" invece che al passo generico, ciò può indurre a scrivere programmi più
complicati e spesso errati.
Ad esempio, nel problema del massimo, partendo dal primo passo qualcuno potrebbe ragionare così:
poiché voglio ci sia almeno un elemento, faccio una lettura:
leggi(x);
int max = 0;
ora entro nel ciclo e faccio il primo passo:
poiché ho già fatto la lettura fuori dal ciclo, faccio prima il confronto e poi una nuova lettura:
while(...) {
if(x > max) max = x;
leggi(x);
...
Esempio
In questo modo, ad ogni passo si confronta con max il valore x letto nel passo precedente: questo è piuttosto innaturale, e condurrà nella migliore delle ipotesi ad un programma inutilmente complicato e difficile da capire (perché si deve ragionare su due passi alla volta), o più probabilmente ad un programma errato come il seguente:
PROGRAMMA ERRATO
leggi(x);
int max = 0;
while(…) {
if(x > max) max = x;
leggi(x);
}
C invarianti di ciclo
Problema dei polli e dei conigli di Leonardo Pisano detto Fibonacci – 1200
In una fattoria ci sono polli e conigli. Sapendo che sono state contate 260 zampe e 100 teste, determinare il numero di polli e di conigli.
• Il nostro scopo è quello di determinare il numero dei polli;
• il numero dei conigli sarà automaticamente determinato eseguendo la sottrazione teste – polli;
• la variabile polli può assumere un valore compreso tra 1 e teste.
Dal problema si evince ancora che :
Numero di zampe = 2 * polli + 4 * conigli
C invarianti di ciclo
Le precondizioni e le postcondizioni relative all’algoritmo sono:
PRE: Input : teste, zampe con teste e zampe (interi positivi) POST : 1) 0<= polli<=teste
2) conigli = teste - polli
3) 2 x polli + 4 x conigli = zampe
Risolvere il problema significa risolvere il sistema formato dalle equazioni 2) e 3) e vedere se ammette soluzioni intere.
Noi invece per poter usare un loop preferiamo prendere in considerazione ogni numero compreso tra 0 e teste (100 nel nostro problema) e verificare se soddisfa le due condizioni.
Per determinare il corpo del loop osserviamo che, per la 1), la variabile polli deve essere incrementata di uno ad ogni passo del ciclo, mentre la variabile conigli deve essere posta uguale a teste - polli.
C invarianti di ciclo
Dunque avremo:
while (condizione) polli ¬ polli +1 conigli ¬ teste-polli
Si dovrà uscire dal loop non appena la condizione 3) risulti verificata la sua negata rappresenta la condizione di ingresso al loop
Potremo quindi scrivere:
while (2* polli +4*conigli ¹ zampe) polli ¬ polli +1
conigli ¬ teste - polli
Poiché le grandezze variabili devono essere inizializzate prima del loop.
polli=0
conigli=teste
while (2* polli +4*conigli ¹ zampe) polli ¬ polli +1
conigli ¬ teste - polli
C invarianti di ciclo
In una fattoria ci sono polli e conigli. Sapendo che sono state contate 260 zampe e 100 teste, determinare il numero di polli e di conigli. Sappiamo che:
0 £ polli £ teste
conigli = teste - polli
zampe = 2 * polli + 4 * conigli
non tutte le coppie teste, zampe ammettono soluzioni intere
leggi(zampe, teste) polli ß 0
conigli ß teste - polli
while (2´polli + 4´conigli <> zampe) and (polli £ teste):
polli ß polli + 1
conigli ß teste - polli if (polli £ teste):
stampa(polli,conigli) else:
stampa(“non ci sono soluzioni intere”)
(polli £ teste) and (conigli = teste - polli)
Invariante di ciclo
Algoritmo
C invarianti di ciclo
main () {
int polli,conigli,teste,zampe;
printf("Inserire numero teste=\n");
scanf("%d",&teste);
printf("Inserire numero zampe=\n");
scanf("%d",&zampe);
polli=0;
conigli=teste;
while (((2*polli+4*conigli)!=zampe) && polli<=teste) {
polli=polli+1;
conigli=teste-polli;
}
if (polli<=teste)
printf("Polli= %d Conigli= %d \n",polli,conigli);
else
printf("Il problema non ammette soluzioni intere\n");
return 0;
}
Esercizi
1. Un padre ha 36 anni ed il figlio 8. Fra quanti anni l’età del padre sarà doppia di quella del figlio?
PRE : padre, figlio: interi in input
POST: il numero i di anni è intero tale che: padre + i = 2*( figlio + i)
2. La differenza tra i quadrati di due numeri consecutivi è 49. Determinare i due numeri
– caso particolare dell’esercizio 3 precedente
3. Determinare un numero naturale di due cifre sapendo che la differenza tra la seconda cifra e la prima è 6 e che se si invertono le cifre, si ottiene un numero che è 31/13 del numero da determinare
4. Ad una riunione scolastica partecipano N famiglie, alcune con 1 figlio ed altre con 2 figli. Se in totale si hanno M partecipanti, qual è la
composizione delle famiglie?
– Siano M e N dati di input e rispondere anche nel caso in cui non ci sono soluzioni.
14
Il modo più semplice per calcolare la radice quadrata di un numero a è quello di utilizzare un algoritmo molto antico, usato dai babilonesi, e riproposto da Erone, che consiste nell’utilizzare la formula ricorrente
Xs = __________
2
dove Xp è il valore precedente e Xs è quello successivo. Per poter
applicare questa formula è necessario assegnare un valore iniziale a Xp; poiché Xp appare anche al denominatore poniamo come valore iniziale Xp=1.
X
p+ a X
pVolendo calcolare la radice di 2, seguiamo i primi passi dell’algoritmo:
Xp=1 Xs=(1+2)/2=1,5
Poniamo ora Xp=1,5 Xs=(1,5+2/1,5)/2=1,416 Poniamo ora Xp=1,416 e così via
Calcolo della radice quadrata
15
Possiamo controllare la differenza tra Xs e Xp: se questa è minore di un numero piccolo prefissato (che indichiamo con Y), allora l’algoritmo ha termine.
Indicando con esegui la variabile booleana che rappresenta la sentinella possiamo scrivere un primo raffinamento
dell’algoritmo.
Leggi(a) Xp=1
esegui ¬ 1
while (esegui=1) Calcola xs
if abs(Xs-Xp)<Y esegui ¬ 0 xp=xs
stampa (xs)
Sentinella
16
#include <math.h>
// Calcola radice quadrata int main () {
const float eps=0.000001;
float a,xs,xp ; int esegui;
// precondizioni: a>=0 and eps>0
printf(" Calcolo della radice di a: a=\n”);
scanf(“%f”,&a);
xp=1.0;
esegui=1;
while (esegui) { xs=(xp+a/xp)/2;
if (fabs(xs-xp)<eps) esegui=0;
xp=xs;
}
//Postcondizioni: xs>0 and xp>0 and (xs-xp)<eps printf("Radice di a = %f\n”,xs);
return 0;
}
Leggi(a)
Xp=1Esegui ¬true while esegui
Calcola xs
if abs(Xs-Xp)<Y esegui ¬false xs=xp
stampa (xs)
Calcolo della radice quadrata
17
Xs (o Xp ) sono sempre positivi durante le varie iterazioni: possiamo ritenere che Xs>0 (Xp>0) sia un invariante di loop.
Andiamo a vedere di quanto varia il valore X contenuto all’indirizzo Xp ad ogni iterazione, se con DX indichiamo tale variazione si avrà:
(X+ DX) = (X + a/X)/2 2(X+ DX) = (X + a/X)
2DX = X + a/X – 2X 2|DX| = |X - a/X|
Si potrebbe anche scrivere:
x=1 While….
x=(x+a/x)/2;
Quale sarà la condizione di uscita dal loop? Lo possiamo ricavare dalla terza formula:
– |X-a/X| /2<Y
Calcolo della radice quadrata
18
Un’altra maniera di gestire il ciclo è la seguente:
#include <math.h>
// Calcola radice quadrata int main () {
const float eps=0.000001;
float a,x ;
// precondizioni: a>=0 and eps>0
printf(" Calcolo della radice di a: a=\n”);
scanf(“%f”,&a);
x=1.0;
while (fabs(x-a/x)/2>=eps) x=(x+a/x)/2;
//Postcondizioni: x>0 |x-a/x|<eps printf("Radice di a = \n”,x);
return 0;
}
Calcolo della radice quadrata
Esercizi
Supponiamo di dover prendere decisioni sull’acquisto di un’azione. Per fare questo l’agente di cambio decide sulla base dell’andamento giorno per giorno dell’azione stessa.
• Assegnato allora un intervallo di tempo in giorni, scriviamo il prezzo dell’azione giorno per giorno.
• Introduciamo un contatore che contiene il numero di giorni nei quali l’azione è aumentata rispetto al giorno precedente e un contatore nel quale registriamo i giorni nei quali è calata.
• Non registriamo i giorni in cui l’azione è rimasta invariata.
Scrivere un programma che, assegnato un certo numero N di giorni ed il prezzo dell’azione giorno per giorno, restituisca il numero totale dei giorni in cui l’azione è aumentata ed il numero totale dei giorni in cui l’azione è diminuita.
19
Successioni -> Il problema di Fibonacci in sintesi
• Quante coppie di conigli verranno prodotte in un anno, a partire da un’unica coppia, se ogni mese ciascuna coppia dà alla luce una nuova coppia che diventa produttiva a partire dal secondo mese?
1°) 1 = 1
2°) 1 + 1 = 2
3°) 1 + 2 = 3
4°) 2 + 3 = 5
5°) 3 + 5 = 8
6°) 5 + 8 = 13
7°) 8 + 13 = 21
Successione di Fibonacci
La successione di Fibonacci è una sequenza di numeri interi naturali definibile assegnando i valori dei due primi termini, F0:= 0 ed F1:= 1,
e chiedendo che per ogni successivo sia
Fn := Fn-1 + Fn-2.
Successione di Fibonacci
int main {
int f0 = 0;
int f1 = 1;
int temp;
int i,n;
printf(“inserisci n\n”);
scanf(“%d”,&n);
if (n == 0) {
printf(”%d ”,f0);
}else if (n == 1) { printf(”%d ”,f1);
}
else{
cout<<f1<<" ";
for (i = 2; i <= n; i++) { temp = f1;
f1 = f1 + f0;
f0 = temp;
printf(”%d ”,f1);
} }
return 0;
}
Successione di Fibonacci
void fibonacci (int n) { int f0 = 0;
int f1 = 1;
int temp;
int i;
if (n == 0) { cout<<f0;
}else if (n == 1) { cout<<f1;
}
else{
while (f1<n) { cout<<f1<<" ";
temp = f1;
f1 = f1 + f0;
f0 = temp;
} }
}
esercizio14.5.cpp
Esercizi
Si consideri la successione:
a1 = 1; a2 = 3; a3 = 4; e per ogni n>3 an = an-1 + 2*an-2 + an-3
Siano dati due array A e B di interi di N elementi. L’array A è ordinato in senso crescente con A[0]>(a3). Scrivere una procedura che inserisca in ogni elemento B[i] uno tra i due seguenti valori:
0 se l’elemento A[i] NON appartiene alla successione;
A[i] se l’elemento appartiene alla successione.
Esempio
A= 15 48 55 115 L’output sarà:
B= 0 48 0 0
Infatti, a4 = 11; a5 = 22; a6 = 48; a7 = 103; a8 = 221;
Successione di Fibonacci
void succ(int A[],int B[], int n) { int a1 = 1;
int a2 = 3;
int a3 = 4;
int an;
an = a3 + 2*a2 + a1;
for(int i=0;i<n;i++) { while (an<A[i]) {
a1=a2;
a2=a3;
a3=an;
an = a3 + 2*a2 + a1;
if(A[i]==an) B[i]=A[i];} else B[i]=0;
} }
esercizio14.6.cpp
Esercizi
Si consideri la successione:
a1 = 1; a2 = 3; a3 = 4; e per ogni n>3 an = an-1 + 2*an-2 + an-3
Siano dati due array A e B di interi di N elementi. L’array A è ordinato in senso crescente con A[0]>(a3). Scrivere una procedura che inserisca in ogni elemento B[i] uno tra i due seguenti valori:
0 se l’elemento appartiene alla successione;
la minima differenza in valore assoluto tra A[i] ed un elemento della successione altrimenti.
Esempio
A= 15 48 55 115 L’output sarà:
B= 4 0 7 12
Infatti, poiché a4 = 11; a5 = 22; a6 = 48; a7 = 103; a8 = 221;
si ha che:
Il valore A[0] = 15 è compreso tra a4 = 11 ed a5 = 22. La minima differenza è 4.
Il valore A[1] = 48 è pari ad a6 = 48.
Il valore A[2] = 55 è compreso tra a6 = 48 ed a7 = 103. La minima differenza è 7.
Il valore A[3] = 115 è compreso tra a7 = 103 ed a8 = 221. La minima differenza è 12.
