Silvia Rossi » 14.Algoritmi

C++ invarianti di ciclo

Come dobbiamo ragionare per verificare che un algoritmo che adoperi un loopsia 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)

|←|+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)

|←|+1
prodotto←prodotto*i

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 (segue)

Esempio:
il fattoriale: dato n intero calcolate n! = 1×2 x … x 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.

C++ invarianti di ciclo (segue)

L’invariante di loop è data da:

prodotto= prodotto dei primi i numeri

Algoritmo

leggi(n)
i ← 1
prodotto← 1
while (i ≤ n):

prodotto ← prodotto * i
i ← i + 1

stampa(fatt)

Invariente di ciclo

(prodotto=1 x 2 x … x i) and (1 ≤ i ≤ n+1)

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 cella max sia contenuto il massimo.

Per far ciò, al generico passo la cella max deve contenere il massimo dei valori immessi fino a quel momento.

1. 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: cin>>x;
2. se è maggiore di max sostituirlo a max,

altrimenti non far nulla: if(x > max) max = x;

Esempio (segue)

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 è:

cin>>x;
int max = x;
i=2;
while(i<=n) {

cin>>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:

cin>>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;
cin>>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

cin>>x;
int max = 0;
while(…) {

if(x > max) max = x;
cin>>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 (segue)

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 (segue)

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 (segue)

L’invariante di loop è data da:

(0 <= polli<=teste) and (conigli = teste – polli) and

(( 2*polli + 4*conigli ≠ zampe) or (2 polli + 4*conigli = zampe))

N.B. non tutte le coppie teste, zampe ammettono soluzioni intere.

Tale situazione si presenta quando il ciclo viene completamente eseguito senza che sia stata verificata la condizione 2 polli + 4 conigli = zampe.

In tal caso all’uscita dal ciclo si ha polli>teste; è questa la condizione da testare per verificare se ci sono soluzioni.

C++ invarianti di ciclo (segue)

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.

C++ invarianti di ciclo (segue)

Invariente di ciclo

(polli ≤ teste) and (conigli = teste – polli)

and ((2 x polli + 4 x conigli <> zampe) or (2 x polli + 4 x conigli = zampe)

Algoritmo

leggi(zampe, teste)
polli ← 0
conigli ← teste – polli
while (2 x polli + 4 x conigli <> zampe) and (polli ≤ teste):

polli ← polli + 1
conigli ← teste – polli

if (polli ≤ teste):

stampa(polli,conigli)

else:

stampa(“non ci sono soluzioni intere”)

C++ invarianti di ciclo (segue)

Si veda l'esercizio 14.1

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.

Sentinella

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 ←true
while esegui

Calcola xs
if abs(Xs-Xp)

esegui ← false <Y

xp=xs

stampa (xs)

Calcolo della radice quadrata

Leggi(a)
Xp=1
Esegui ←true
while esegui

Calcola xs
if abs(Xs-Xp)

esegui ← false <Y

xp=xs

stampa (xs)

Si veda l'esercizio 14.2

Calcolo della radice quadrata (segue)

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 (segue)

Un’altra maniera di gestire il ciclo è la seguente:

Si veda l'esercizio 14.3

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.

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 (segue)

Si veda l'esercizio 14.4

Successione di Fibonacci (segue)

Si veda l'esercizio14.5

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;

Successioni

Si veda l'esercizio14.6

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

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.

Esercizi

Si considerino le 2 successioni:
a1 = 1; a2 = 3; a3 = 4; e per ogni n>3:
an = an-1 + 2*an-2 + an-3

b1 = 2; b2 = 3; b3 = 4; e per ogni n>3:
bn = bn-1 + bn-2 + 2*bn-3

Sia dato un array A di dimensione N di interi. Gli elementi di A sono ordinati in senso crescente con A[0]>(a3,b3). Scrivere una funzione che restituisca TRUE se ogni elemento del vettore appartiene ad almeno una delle due successioni.

Esempio: N=4;
A=    22    165    659    2191

L’output sarà TRUE poiché il primo e l’ultimo elemento del vettore appartengono alla prima successione mentre il secondo ed il terzo appartengono alla seconda successione.