Programmazione Mod A - Cap 4 - prof. Burattini 1.

Programmazione Mod A - Cap 4 - prof. Burattini

1


2

Le istruzioni di selezione nidificate

Diremo che un’istruzione di selezione è nidificata se esiste almeno un’altra istruzione di selezione contenuta in essa.

Una tipica istruzione nidificata è composta da più comandi if …… poste l’una dentro l’altra. Per esempio:

if (a>b) istruzione 1;else if (a<b) istruzione 2; else istruzione 3;

Se a>b allora esegui istruzione 1 altrimenti (cioè a può essere minore o uguale a b ) se (a<b) esegui istruzione 2 altrimenti (cioè a è uguale a b ) esegui le istruzione 3

Si potrebbe obiettare che lo stesso scopo può essere raggiunto adoperando tre istruzioni ifposte l’una di seguito all’altra:if (a>b) istruzione 1;if (a<b) istruzione 2;if (a==b) istruzione 3;

Tuttavia in questo ultimo caso occorre effettuare sempre tre confronti tra a e b, mentre nel primo caso ne basteranno due se a<=b, uno soltanto se a>b .


3

A titolo esemplificativo riprendiamo la risoluzione dell’equazione di primo grado ax+b=0 Sappiamo che essa ammette la soluzione x =-b/a se a è diverso da 0, altrimenti dobbiamo controllare il valore di b; se anche b è nullo allora l’equazione è soddisfatta da qualsiasi valore di x; si dice che l’equazione è indeterminata; altrimenti l’equazione non ammette nessuna soluzione, si dice che l’equazione è impossibile.

Pseudocodice CODICE C++

if (a!=0) { x=-b/a; cout<<”soluzione x=”<<x<<endl; } else if (b==0) cout<<”equazione indeterminata”; else cout<<”equazione impossibile”;

if a 0 x-b/a stampa(x) else if b=0 stampa(“equazione indeterminata”) else stampa(“equazione impossibile”)


4

La nidificazione dell’istruzione if ……..else ………. è spesso fonte di errori; consideriamo il problema seguente:

Assegnati tre numeri riscriverli in modo ordinato.Ad esempio dati i tre numeri non ordinatinumero1=14 numero2=28 numero3=18al termine dell’algoritmo la variabile numero1 dovrà contenere ancora 14 in

numero2 ci sarà 18 ed in numero3 ci sarà 28.Si consideri il seguente algoritmo:

If (numero1>numero2 ) Scambia(numero1,numero2)else if (numero1>numero3) Scambia(numero1,numero3) else if (numero2>numero3) Scambia(numero2,numero3)

Applicando l’algoritmo alla nostra terna di numeri osserviamo che essendo numero1<numero2 dobbiamo seguire il primo else; poiché numero1<numero3 seguiamo il secondo else che scambia numero2 e numero3; alla fine abbiamo i tre numeri ordinati

numero1=14 numero2=18 numero3=28


5

L’ALGORITMO PRECEDENTE E’ ERRATO. Si consideri ad esempio la terna 7 1 5 come input essa sarà trasformata in 1 7 5 dal

nostro algoritmo.Le istruzioni precedenti non risolvono il problema per la semplice ragione che esse

implicano un solo scambio, mentre in genere ciò non è vero. Consideriamo, invece, le istruzioni seguenti :

if (Numero1>Numero2) Scambia (Numero1,Numero2);if (Numero1>Numero3) Scambia (Numero1,Numero3);if (Numero2>Numero3) Scambia (Numero2,Numero3);

Eseguiamo il testing dei cammini, determinando le precondizioni e le postcondizioni di ogni istruzione if (cond) ..….

Se Numero1<Numero2 il computer non esegue lo scambio tra i due numeri, se invece Numero1>Numero2 allora i due numeri vengono scambiati.

Se Numero1<=Numero3 possiamo dedurre che Numero1 è il valore più piccolo Se Numero1> Numero3 possiamo scambiarli in modo che l’affermazione sia soddisfatta.

Al termine dei primi due if in Numero1 si troverà il numero più piccolo dei tre.Lo stesso accade nel caso del terzo confronto Numero2<=Numero3.Al termine del terzo if in Numero2 ci sarà un valore minore o uguale a quello

contenuto in Numero3 per cui effettivamente lo stato finale al termine dei tre if sarà:

Numero1<=Numero2<=Numero3


6

Esaminiamo ora un esempio in cui il numero di istruzioni if ……. else …… nidificate sia maggiore.

Un negozio vende solo articoli aventi tutti uno stesso prezzo. Inoltre se si acquistano più di 10 pezzi si avrà uno sconto del 10%, se più di 25 lo sconto sarà del 15% per salire al 25% per chi acquista più di 50 pezzi.

Si vuole sapere, avendo acquistato n pezzi quanto si deve pagare.In questo caso è evidente che occorre esaminare varie alternative e quindi ricorrere

ad istruzioni if then else nidificate. Ricorrendo al metodo dei raffinamenti successivi cominciamo a considerare la prima

alternativa quella in cui non si ha diritto ad uno sconto:leggi(prezzo, pezzi)kpezzi*prezzoif(pezzi<=10) contokelse.. altri casi

Sappiamo che l’istruzione che segue l’else sarà eseguita solo se sono stati acquistati più di dieci pezzi ed è evidente che occorre procedere considerando i vari casi in ordine crescente rispetto al valore di pezzi, quindi else ..altri casi può essere sostituito conelse if(pezzi<=25) conto0.90*k

(postcond. Pezzi maggiore di 10 e non superiore a 25)else … casi in cui pezzi è maggiore di 25.


7

Avremo in definitiva il seguente algoritmo:

leggi(prezzo, pezzi)kpezzi*prezzoif(pezzi<=10) contok

(post. Pezzi minore di 10 )else

if(pezzi<=25) conto0.90*k (post: pezzi maggiore di 10 e non superiore a 25)

else if(pezzi<=50) conto0.85*k

(post: pezzi maggiore di 25 e non superiore a 50)else

pezzi 0.75*k (post: pezzi maggiore di 50)


8

Ricapitolando si può dire che se bisogna effettuare n test distinti (quattro nel nostro esempio), ad ognuno dei quali corrisponde una azione alternativa (un differente valore di conto), occorre adoperare n-1 else innestati secondo il seguente schema:

ALGORITMO if..else ifIf cond1

azione1elseif cond2

azione2else…………else if condn-1

azionen-1else

azione n


9

Esiste un particolare operatore, detto operatore condizionale, che rappresenta un’istruzione if … else …. estremamente compattata.

Supponiamo di voler inserire nella variabile intera x il più grande dei valori interi tra a e b:

if (a>b) x=a;

else x=b;Invece adoperando l’operatore condizionale ? scriveremo:

(a > b) ? x=a : x=b;


10

L’operatore ? ha la seguente forma:

(condizione ) ? istruzione1 : istruzione2;

prima del punto interrogativo c’è la condizione che può essere vera o falsa, mentre dopo si ha la situazione seguente:

se la condizione è vera, allora va eseguita istruzione1 ;se la condizione è falsa, allora va eseguita istruzione2 .

Un altro esempio è il seguente: assegnato un intero n determinare se è pari o dispari.

(n % 2==0) ? cout<<”pari” : cout<<”dispari”;

La semplicità dell’operatore condizionale non deve trarre in inganno: il suo uso è consigliato soltanto nei casi più semplici, in quelli più complessi diventa praticamente inutile perché rende il codice completamente illegibile.


11

Espressioni booleane composte.

Le espressioni booleane composte si ottengono dalle espressioni booleane semplici precedentemente introdotte (a<b, a!=0,etc) adoperando i seguenti operatori:

Nome Inglese connettivo logico in C++Negazione NOT A !(A)Congiunzione AND AB (A)&&(B)Disgiunzione OR AB (A)||(B)

La negazione è un operatore unario prefisso, la congiunzione e la disgiunzione sono due operatori binari infissi.

Il valore di verità delle espressioni booleane nell’ultima colonna dipende dal valore di verità di A e di B secondo la seguente tabella di verità:

A B A && B | A B A || B | A ! A

Vero Vero Vero | Vero Vero Vero | Vero Falso

Vero Falso Falso | Vero Falso Vero | Falso Vero

Falso Vero Falso | Falso Vero Vero |

Falso Falso Falso | Falso Falso Falso |


12

Supponiamo che a e b siano due numeri interi; allora l’istruzione

if ((a==0) && (b==0)) cout<<” a e b sono entrambi nulli”;

scrive ‘a e b sono entrambi nulli’ soltanto se è vero che sia il valore contenuto ina che quello contenuto in b sono nulli; l’istruzione

if ((a==0) || (b==0)) cout<<”almeno uno dei due numeri a e b è nullo”;

dà la scritta ‘almeno uno dei due numeri a e b è nullo’ soltanto se almeno unodei due numeri è uguale a 0.

È bene ricordare che le espressioni booleane semplici che compaiono in unaespressione composta devono essere racchiuse tra parentesi tonde e chel’operatore di negazione ha la precedenza sugli altri due.

Due espressioni logiche si dicono equivalenti se esse assumono sempre lo stessovalore di verità, qualunque sia il valore di verità delle espressioni logichesemplici che la compongono


13

Ricordiamo le leggi di De Morgan che risultano estremamente utili:(AB) è equivalente a AB(AB) è equivalente a AB

In C++ potremmo scrivere: ! ((A) &&(B) ) == !(A) ||! (B)! ((A) || (B) ) == !(A) && !(B)

Esercizio: Scrivere un programma che mostri la correttezza delle leggi di De Morgan

Un esempio è dato dalle seguenti istruzioni che permettono di scrivere tutti i numeri interi tra 1 e 100 che non sono divisibili per 10 (un numero è divisibile per 10 quando è divisibile per 2 e per 5) :i=0 i=0;while (i<100) while (i<100) { { i++; i++;

if ! ((i % 2==0) && (i % 5==0)) if ! (i % 2 ==0) || !(i % 5==0) cout<< i ; cout<< i;

} }


14

Si noti che l’espressione booleana (A1) && (A2) && …&&(An) è valutata nel seguente modo: appena si incontra una A che valuta a falso la computazione dell’espressione viene interrotta, le A successive non sono valutate e si ritorna il valore falso per l’intera espressione.

Analogamente per l’espressione A1 || A2 || … || An si ritorna il valore vero non appena si incontra una A che valuta a vero. In questo modo non solo si velocizza la computazione ma l’espressività del linguaggio ne risulta potenziata. Ad esempio si può scrivere:

if((a!=0 ) &&(b/a<c))…

Bisogna però fare attenzione: l’espressione ((b/a<c)&&(a!=0)) pur essendo logicamente

equivalente alla prima darebbe un errore a runtime se a fosse nullo perché cerca di dividere un numero per 0.


15

L’equazione di 2° grado

Problema

Assegnata la generica equazione di 2° grado

Ax2 + Bx + C = 0

dove A, B e C sono numeri reali

trovare le soluzioni.

A2

AC4BB 2 A2

AC4BB 2

Chiamiamo discriminante il valore della espressione

AC4B2


16

Input : A, B, C

Output:•Caso equazione non quadratica

•Se A=B=C=0 questa è una tautologia•Se A=B=0 e C<>0 questa non è una equazione•Se A=0 e B e C <>0 questa è una equazione lineare che ammette una

radice pari a -C/B.•Caso equazione quadratica degenere

•Se A<>0 e B e C=0 questa equazione ammette una soluzione pari a 0 •Se A e B <>0 e C=0 questa equazione ammette due soluzioni: una

pari a 0 e la seconda pari -B/A•Caso equazione quadratica con due radici

•Se A, B e C <> da 0 e >0 ammette due radici reali distinte•Se A, B e C <> da 0 e <0 ammette due radici immaginarie •Se A, B e C <> da 0 e =0 ammette due radici reali uguali e

coincidenti pari a -B/2A


17

Prima osservazione: se A=0 allora l’equazione non è quadratica.

Pseudo-codiceIntroduci A, B, CSe A=0 allora

MostraEqNonQuadr(B,C)altrimenti

gestisci l’equazione quadratica

Pseudo-codiceIntroduci A, B, CSe A=0 allora

MostraEqNonQuadr(B,C)altrimenti

Se C=0 alloraMostraRadiciDegenerate(A,B)

altrimentiMostraDueRadici(A,B,C)


18

Pseudo-Codice MostraEqNonQuadr

scrivi: ‘ equazione non quadratica ‘Se B=0 allora

NonEquazionealtrimenti scrivi ‘esiste una radice pari a ‘ -C/B

Pseudo-Codice NonEquazione

Se C=0 allora scrivi ‘tautologia’altrimenti scrivi ‘non è una equazione’

Pseudo-Codice MostraEqNonQuadr

scrivi: ‘ equazione non quadratica ‘Se B=0 allora

Se C=0 allora scrivi ‘tautologia’

altrimenti scrivi ‘non è una equazione’ altrimenti scrivi ‘esiste una radice pari a ‘ -C/B


19

Pseudo-Codice MostraRadiciDegeneriprecondizioni C=0 A<>0 B qualunque

Se B=0 allora scrivi ‘due radici degeneri’altrimenti scrivi ‘una radice degenere pari a 0 ’ scrivi ‘un’altra radice pari a ’, -B/A

Pseudo-Codice MostraDueRadiciprecondizioni A,C <>0 B qualunque

Discrim sqr(B) - 4*A*CSe Discrim >=0 allora

RadiciRealialtrimenti RadiciComplesse


20

Analizziamo i vari casi.

Il primo, caratterizzato da a=0, porta all’equazione di primo grado, equazione non quadratica, mentre gli altri due casi si distinguono dal valore di c, nullo per l’equazione quadratica degenere, diverso da zero nel caso dell’equazione con due radici.

Se il coefficiente a è nullo risolvi l’equazione non quadratica altrimenti se anche c è nullo l’equazione è degenere altrimenti è un’equazione con due radici


21

#include <iostream>#include <cmath>// Calcolo Equazione II gradousing namespace std;void NonQuadratica (double, double, double&);void QuadraticaDegenere (double, double, double&, double&);void Quadratica (double, double, double, double&, double&);int main () { double a,b,c,x1,x2; char ch='s'; while (ch!='n') { cout <<"Programma che calcola le radici delle equazioni

di secondo grado"<<endl; cout<<"Inserire i 3 coefficienti :"<<endl<<endl; cout<<"a = "; cin>>a; cout<<"b = "; cin>>b; cout<<"c = "; cin>>c; if (a==0) NonQuadratica(b,c,x1); else if (c==0) QuadraticaDegenere(a,b,x1,x2); else Quadratica(a,b,c,x1,x2); cout<<"Continuare (s/n)? "; cin>>ch; }}


22

void NonQuadratica (double b,double c,double &x1) { if (b==0) { if (c==0) cout <<"Questa è una equazione indeterminata."<<endl; else cout<< "Questa è un'equazione impossibile."<<endl; } else

{ cout<<"Equazione non quadratica che ammette

soluzione unica:"<<endl; x1= -c/b; cout<<"La soluzione è = "<<x1<<endl; }}


23

void QuadraticaDegenere (double a,double b,double& x1,

double& x2) { if (b==0) { cout<<"L`equazione ammette due radici reali e

coincidenti uguali a zero"<<endl; x1=0; x2=0; } else { x1=0; x2=-b/a; cout<<"L`equazione ha 2 soluzioni : x1=0 e

x2="<<x2<<endl; }}


24

void Quadratica (double a,double b,double c,double &x1,double &x2)

{ double delta; char segno='+'; delta= b*b - 4*a*c; if (delta>0) { cout<<"L`Equazione ammette due radici reali e

distinte."<<endl; x1= (-b - sqrt(delta)) / (2*a); x2= (-b + sqrt(delta)) / (2*a); cout<<"Le due soluzioni sono : \n"; cout<<"X1 = "<<x1<<endl; cout<<"X2 = "<<x2<<endl; }


25

else //delta <= 0 if (delta<0) { cout<<"L`Equazione ha radici complesse coniugate"<<endl; x1= -b/(2*a); x2= sqrt(-delta) / (2*a); cout<<"Le due soluzioni sono : \n"; if (x2<0) segno='-'; cout<<"X1 = "<<x1<<" "<<segno<<" "<<x2<<" i"<<endl; if (segno=='+') segno='-'; else segno='+'; cout<<"X2 = "<<x1<<" "<<segno<<" "<<x2<<" i"<<endl; } else { //delta=0 x1= -b / (2*a); x2=x1; cout<<"L`Equazione ha due radici reali e coincidenti

pari a "<<x1<<endl; }} eser4.1

D:\Documents and Settings\marina\Desktop\C++ lezioni\C++ lezioni mod A\Cap.4 C++\eser4.1.cpp


26

/* Sia assegnato un vettore di interi (max 255) VettIn.Porre all'inizio di V i valori di V pari e di seguito quelli dispari senzacambiare l'ordine-------------------------------------------------------------------------------------------------Esempio INPUT:VettIn = 6 5 7 2 4 9 14 5OUTPUT:VettIn = 6 2 4 14 5 7 9 5-------------------------------------------------------------------------------------------------------*/ PSEUDO CODICE

LeggiDati(Vett, n, k); OrdSubVet(Vett, n,k, j); StampaDati(Vett, n); system("PAUSE");}


27

// PROTOTIPIvoid StampaDati(int [],int);void LeggiDati(int [],int&, int&);void scambia(int& ,int&);void OrdSubVet(int [],int,int,int&);

// MAINint main() { int Vett[M], n, j=0, k; LeggiDati(Vett, n, k); OrdSubVet(Vett, n,k, j); StampaDati(Vett, n); system("PAUSE"); return EXIT_SUCCESS; }

// DEFINIZIONIvoid OrdSubVet(int V[], int N, int K, int &j) // ordina i numeri pari e dispari { int k; for(int i=1;i<N;i++) { if (V[j]%2 ==0) j++; else { if (V[i]%2 ==0) { k=i; while (k>j) { scambia(V[k],V[k-1]); k--; } j++; } } } }

paridispari


28

ESERCIZI.1) I compiti scritti sono valutati con il seguente criterio:A=ottimo tra 27-30B=buono tra 23-26C=sufficiente tra 19-22D= incerto tra 17-18E=insufficiente Scrivere un programma che, assegnato un certo voto compreso tra 1 e 30,

scriva la lettera corrispondente e viceversa, assegnata la lettera, stampi la scritta posta alla sua destra.

2) Rivedere il programma del MCD in modo che non accetti numeri negativi o nulli.

3) Calcolare in una frase qual è la vocale che occorre più volte.4)Scrivere un programma che simuli una calcolatrice per numeri razionali: si

assegnano due stringhe nella forma a/b che rappresentano i due numeri razionali ( per esempio 3/5 e 5/6 ). Il programma deve determinare i due numeri e poi, alla richiesta di una certa operazione ( +, -, *, : ) deve restituire il risultato sotto forma di frazione.

Se per esempio riceve in input : 3/5 5/6 *deve restituire 1/2


29

Istruzioni switch, break

L’istruzione switch offre un altro modo per implementare strutture di selezione con diverse alternative. Prima di mostrare la struttura dell’istruzione switch ricordiamo il tipo ordinale.

Tipo ordinale: quando è possibile definire il precedente (tranne il primo) ed il successivo (tranne l’ultimo) di ogni valore.

I tipi int, longint, char ad esempio sono ordinali.


30

Osservazioni:

-espressione: può essere una variabile od una espressione di tipo ordinale;

-la parola-chiave case deve essere seguita da una costante il cui valore Risultato1, Risultato2,….è coerente con l’espressione;

-istruzioni1, istruzioni2,… sono sequenze di istruzioni che non devono essere delimitate da parentesi graffe;

-la parola-chiave break è essenziale:

-una volta che il compilatore C++ incontra la parola case ed il Risultato voluto, esegue solo le istruzioni corrispondenti ignorando completamente i case seguenti ed il default;

-il caso default può essere omesso; esso rappresenta il caso in cui il Risultato di (espressione) non corrisponde a nessuno dei Risultati previsti ( è diverso da Risultato1,Risultato2, …. RisultatoN).

L’istruzione switch ha la seguente struttura:

switch (espressione) { case Risultato1: istruzioni1; break;

case Risultato2; istruzioni2; break;…………………..

case RisultatoN: istruzioniN; break;

default: istruzioni di default;}


31

ESEMPIO: Supponendo che in una scuola siano assegnati dei giudizi corrispondenti ai voti da 3 a 10 secondo lo schema successivo, scrivere l’istruzione switch relativa:

Switch (voto) { case 3: case 4: case 5: cout <<”Insufficiente”<<endl;

break; case 6: cout <<”Sufficiente”<<endl;

break; case 7: case 8 : cout <<”Buono”<<endl;

break case 9: cout <<”Ottimo”<<endl;

break case 10: cout <<”Eccellente”<<endl;

break default: cout <<”Voto errato”<<endl; }

da 3 a 5 insufficiente6 sufficiente

da 7 a 8 buono9 ottimo

10 eccellente


32

L’uso dell’istruzione switch corrisponde alla seguente istruzione if …. else… nidificata

if (espressione==Risultato1) {

istruzioni1; }else

if (espressione==Risultato2)else

……………………..else

if (espressione==RisultatoN) { istruzioniN; }

else {

istruzioni di default; }


33

ESERCIZI.a) Scrivere un programma che propone le tabelline per un bambino delle

elementari. I due fattori da moltiplicare sono generati in modo random ed il computer deve controllare che l’utente risponda esattamente. Quando risponde esattamente, il programma deve generare a caso una delle seguenti risposte:1) Bravo!! 2) Ottima risposta. 3) Continua così!! 4) Stai nettamente migliorando.

Nel caso di una risposta errata deve rispondere, sempre a caso, con una delle seguenti:

1) 1) Errato. Riprova. 2) Non è la risposta esatta. 3) Fai più attenzione. Riprova 4) Non arrenderti. Prova ancora.

b) Scrivere una procedura che date la base e l’altezza di un triangolo ne stampi l’area, una seconda che date la base e l’altezza di un rettangolo ne stampi l’area ed infine una terza che stampi l’area di un’ellisse dati i due assi.

c) Scrivere un main che legge due numeri reali ed un carattere: se il carattere è ‘T’ chiama la prima procedura, se il carattere è ‘R’ chiama la seconda, se è ‘E’ chiama la terza, se è ‘N’ esce dal ciclo inviando un messaggio di saluto, altrimenti stampa: ‘carattere errato’.


34

Il ciclo do…while .....

Nella prima parte abbiamo considerato i cicli while …… e for(…..).

In entrambi i casi, se la condizione di ingresso è falsa allorché viene valutata la prima volta, il corpo del ciclo non viene mai eseguito.

Allorché si è sicuri che il corpo del ciclo dovrà essere eseguito almeno una volta si può utilizzare l’istruzione do …. while :

do { corpo del ciclo } while (espressione booleana)

Con questa istruzione il sistema esegue una prima volta il corpo del ciclo, successivamente valuta l’espressione booleana e solo se questa è falsa esce dal ciclo, altrimenti esegue un altro passo


35

Esempio : dato un array A contenente n elementi si vuole verificare se la somma dei suoi

elementi è maggiore di un certo valore k.

sum=0i=0

do { sum=sum+A[i]; i++ } while ((i<n)||(sum<=k)) if (sum>k) cout<<”la somma è maggiore” else cout<<”la somma non è maggiore”

In definitiva utilizziamowhile ( ) ….. quando il corpo del ciclo può anche non essere mai eseguito;

do …. while ( ) quando il corpo del ciclo deve essere eseguito almeno una volta.


36

Invariante di loop

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 1- 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)

ii+1 prodottoprodotto*i

La condizione di uscita dal loop è i=n e la condizione di ingresso , che è la negata della condizione di uscita, sarà: in.

Avremo:while(in)



37

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:

i1 prodotto1while(in)


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 e 1<=i<=n;


38

Esempio ( 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 mentre 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 * conigliLe precondizioni e le postcondizioni relative all’algoritmo sono:PRE: Input : teste, zampe con teste e zampe interi positiviPOST : 1) 0<= polli<=teste 2) conigli = teste - polli 3) 2 x polli + 4 x conigli = zampeRisolvere 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 - conigli.


39

Dunque avremo:while (condizione)polli polli +1conigli teste-polli

Si dovrà uscire dal loop non appena la condizione 3) risulti verificata, dunque la sua negata rappresenta la condizione di ingresso al loop: ( 2* polli +4*conigli zampe)

Potremo quindi scrivere:while (2* polli +4*conigli zampe)polli polli +1

conigli teste - polliPoiché le grandezze variabili nel corpo del loop compaiono entrambe nella

condizione di ingresso esse devono essere inizializzate prima del loop.

Per la 1) polli dovrà quindi assumere il minimo valore possibile cioè 0 e di conseguenza conigli dovrà inizialmente essere uguale a teste, dando così:

polli=0conigli=testewhile (2* polli +4*conigli zampe)polli polli +1conigli teste - polli


40

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

Prima di mostrare l’algoritmo generale osserviamo che, per come era stato enunciato il problema , si era presupposto che esistesse esattamente una soluzione rappresentata da numeri interi; questo è vero nell’esempio proposto (teste= 100 e zampe= 260), ma non è vero in generale.

In altre parole, 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.


41

Leggi( teste, zampe)polli=0coniglitestewhile (2*polli – 4*conigli zampe) and ( polli <= teste) {

polli polli +1 conigli teste – polli} If ( polli <= teste)

Stampa( polli, conigli)Else

Stampa( messaggio)

ALGORITMO GENERALE PER RISOLVERE IL PROBLEMA DEI POLLI E DEI CONIGLI


42

#include <iostream>#include <cstdlib>using namespace std;main () { int polli,conigli,teste,zampe; cout<<"Inserire numero teste="; cin>>teste; cout<<"Inserire numero zampe="; cin>>zampe; polli=0; conigli=teste; while ((2*polli+4*conigli)!=zampe) && polli<=teste) { polli=polli+1; conigli=teste-polli; } if (polli<=teste) cout<<"Polli="<<polli<<"Conigli="<<conigli<<endl; else cout<<"Il problema non ammette soluzioni intere“<<endl; system(“pause”); }}

eser4.2



43

ESERCIZI

Risolvere i seguenti esercizi adoperando un loop come fatto nell’esempio precedente:

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: dovrà passare un numero i di anni: Padre + i = 2*( Figlio + i) 2) La differenza tra i quadrati di due numeri consecutivi è 49. Determinare i

due numeri.

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 43 famiglie, alcune con 1 figlio ed altre con 2 figli. Se in totale si hanno 156 partecipanti, qual è la composizione delle famiglie?


44

Un caso di studio: il calcolo della radice quadrata.

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.

Xp + a Xp

Volendo calcolare la radice di 2, seguiamo i primi passi dell’algoritmo: Xp=1 Xs=(1+2)/2=1,5Poniamo ora Xp=1,5 Xs=(1,5+2/1,5)/2=1,416Poniamo ora Xp=1,416 e così via


45

L’algoritmo di Erone di Alessandria (vissuto tra il I° e II° sec. d.C.) utilizza solo le quattro operazioni dell’aritmetica.

L’algoritmo si basa su considerazioni geometriche. Per calcolare la radice di un numero l costruiamo un quadrato di area l, il suo lato è proprio la radice di l.

Utilizziamo il metodo delle approssimazioni successive e partiamo da un rettangolo i cui lati misurano h e l/h, scegliamo h minore di l. L’area del rettangolo è

cioè è uguale all’area del quadrato che cerchiamo. I lati sono invece uno minore e uno maggiore del lato del quadrato.


46

Calcolando la media aritmetica delle misure dei due lati del

rettangolo, otteniamo dove h1 è maggiore di h.

Costruiamo un nuovo rettangolo i cui lati misurano h1 e


47

Anche in questo caso l’area del rettangolo è cioè uguale a

quella del quadrato, h1 è un valore approssimato per eccesso del

lato del quadrato, è un valore approssimato per difetto.

Però la media aritmetica delle due approssimazioni ha fornito un

valore h1 più vicino a l di quanto lo fosse h.

Calcolando di nuovo la media aritmetica delle misure dei due lati

del rettangolo, otteniamo dove h2 è maggiore di h1 e

sempre minore di l.


48

Si costruisce il rettangolo i cui lati misurano h2 e . Si otterranno

un valore approssimato per eccesso del lato del quadrato e un

valore approssimato per difetto. Il valore di h2 è più vicino a l di

quanto lo fosse h1.

Proseguendo per successive approssimazioni possiamo costruire

due successioni di numeri che approssimano, una per eccesso e

una per difetto, la radice quadrata di l.


49

passo1

Quadrato da costruire

l =400

h

10 40

passo2

25 16

passo3

20,5 19,5

………….

20 20

h


50

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=1Esegui truewhile esegui Calcola xs if abs(Xs-Xp)<Y esegui false xs=xpstampa (xs)


51

Programma in C++

Pseudo-Codice #include <iostream>#include <cstdlib>#include <cmath>using namespace std;// Calcola radice quadratamain () {const float eps=0.000001; float a,xs,xp ; bool esegui;// precondizioni: a>=0 and eps>0 cout << " Calcolo della radice di a: a="; cin >> a; xp=1.0; esegui=true; while (esegui) { xs=(xp+a/xp)/2; if (fabs(xs-xp)<eps) esegui=false; xp=xs; }//Postcondizioni: xs>0 and xp>0 and (xs-xp)<eps cout <<"Radice di "<< a <<"="<< xs <<endl; system(“pause”);}

Leggi(a)Xp=1Esegui truewhile esegui Calcola xs if abs(Xs-Xp)<Y esegui false xs=xpstampa (xs)

eser4.3



52

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

#include <iostream>#include <cstdlib>#include <cmath>using namespace std;// Calcola radice quadratamain () {const float eps=0.000001; float a,x ; // precondizioni: a>=0 and eps>0 cout << " Calcolo della radice di a: a="; cin >> a; x=1.0; while (fabs(x-a/x)/2>=eps) x=(x+a/x)/2;//Postcondizioni: x>0 |x-a/x|<eps cout <<"Radice di "<< a <<"="<< x <<endl; system(“pause”);}

eser4.4



53

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.


54

Categorie di problemi che possono essere risolti con l’uso di cicli

Esistono alcune tipologie di problemi già standardizzati per i quali è utile dividere i problemi in categorie in maniera tale che una volta individuato lo schema opportuno si dovrà soltanto adattare lo schema al caso particolare per poter scrivere l’algoritmo in pseudo-codice.

Per ogni categoria di problemi forniamo l’algoritmo in pseudo-codice, qualche indicazione sugli invarianti ed un esempio.

Ci serviamo del termine evento, per indicare una “istruzione che, una volta eseguita, cambia una parte dello stato del programma”, ad esempio una istruzione di assegnazione.

Come esercizio si consiglia di tradurre ogni esempio nel linguaggio C++.


55

Conteggio di una successione di eventiInvarianti:- ValoreEvento = “il valore di ValoreEvento è quello associato all’ultimo valore introdotto

della sequenza”,- ContaEventi = “Numero di Eventi conteggiati nella sequenza.

ContaEventi = 0Ottieni ValoreEvento

while (ValoreEvento rappresenta un evento da contare ) ContaEventi ContaEventi + 1 ottieni ValoreEventoUtilizzando la struttura do …. while ..... si ottiene l’algoritmo seguente da adoperare solo

se si è certi che la successione di eventi non è vuotaContaeventi= 0 do

ottieni ValoreEvento If (ValoreEvento rappresenta un evento da contare ) ContaEventi ContaEventi + 1 while (ValoreEvento rappresenta un evento da contare)

Esempio: trovare quante volte occorre ricalcolare la variabile x nell’esempio precedente del calcolo della radice quadrata. Basta inserire nell’algoritmo i due enunciati relativi a contaeventi. Qui l’evento in questione è l’enunciato: x=(x+a/x)/2, ValoreEvento è dato dai successivi valori di x, a partire dal valore iniziale uguale ad 1.


56

Conteggio di eventi selezionati.

ContaEventi 0while(ci sono eventi da processare ) ottieni ValoreEvento If (ValoreEvento soddisfa la proprietà) ContaEventi ContaEventi + 1

Invarianti:- ValoreEvento = “il valore di ValoreEvento è quello associato all’ultimo

valore della sequenza introdotto”,- ContaEventi = “Numero di Eventi significativi conteggiati nella sequenza.

ESEMPIO Dato un array disordinato di N interi contarne i numeri positivi.

Contatore0;Passo0;while Passo<N

if A[passo]>0 THEN ContatoreContatore+1 passopasso+1Stampa(Contatore)

Qui l’evento è rappresentato da passo, ValoreEvento da A[passo]


57

Accumulazione di eventi

Per accumulazione intendiamo un processo per cui il precedente valore di una variabile viene combinato con il valore di un nuovo evento; tale combinazione dei valori ( esempio tipico somma o prodotto ) avviene in una variabile detta variabile d’accumulazione.

ACCUMULAZIONE SOMMASomma 0while (ci sono eventi da processare ) introduci ValoreEvento Somma=Somma+ValoreEvento

Invarianti:- ValoreEvento = “il valore di ValoreEvento è quello associato all’ultimo valore introdotto della sequenza ”,-Somma = “Somma di tutti gli Eventi - il cui valore è stato assegnato”.

ESEMPIO Sommare tutti gli elementi di un array di N interi.

Somma=0i=0while ( i<N)

Somma Somma+ A[i] ii+1Mostra ( Somma)


58

Accumulazione di eventi selezionati.

A questa categoria appartengono quei problemi in cui partecipano all’accumulazione solo eventi che soddisfano una prefissata proprietà

ACCUMULAZIONE SOMMASomma 0while(ci sono eventi da processare ) introduci ValoreEvento if (ValoreEvento soddisfa la proprietà) Somma Somma+ValoreEvento

ESEMPIO 4.4Assegnati 5 numeri da tastiera sommare solo i numeri positiviSomma 0;Passo 0;while Passo<5

PassoPasso+1 Leggi(Numero) if Numero>0 THEN Somma Somma+Numero

ii+1 stampa( Somma)

Invarianti:-ValoreEvento = “il valore di ValoreEvento è quello associato all’ultimo valore introdotto della sequenza”,-Somma = “Somma degli Eventi significativi della sequenza.


59

Tecnica dell’evento Sentinella.

Accade spesso di processare una sequenza di eventi finché non si verifica un dato evento. Questo rappresenta un evento terminale: il loop termina dopo che esso è stato inserito.

Diremo che un evento è un Evento Sentinella se è un evento che produce la terminazione di un loop.

Ottieni ValoreEventowhile( ci sono eventi da processare andValoreEvento non è un evento sentinella) elabora ValoreEvento Ottieni ValoreEvento

Invarianti:-ValoreEvento = “il valore di ValoreEvento è quello associato all’ultimo valore introdotto della sequenza”,-Tutti gli eventi eccetto l’ultimo, sono stati processati

L’algoritmo dell’evento sentinella si adopera ogni volta che si devono elaborare tutti gli elementi di un array contenente N elementi. Qui valore evento è il valore dell’indice del generico elemento dell’array, che quindi va inizializzato a zero, il valore di sentinella è N (ma si potrebbe inizializzare l’indice a N-1 con sentinella –1).


60

Algoritmo di skipping

Viene adoperato allorché si vuole cercare il primo degli eventi di una successione che soddisfa una determinata proprietà:Ottieni ValoreEvento while ValoreEvento non soddisfa la proprietà

Ottieni Valore evento

Esempio:leggi(c)while c!=”” leggi(c)

Salta tutti i blank e si arresta sul primo carattere diverso da blank (spazio vuoto).

Naturalmente l’algoritmo funziona solo se si è sicuri che prima o poi apparirà un evento con la proprietà cercata.


61

Algoritmo ‘esiste’

Algoritmo per stabilire se in una successione di eventi esiste almeno un valore avente una data proprietà:

trovato falseOttieni ValoreEvento while ci sono eventi da processare and (not trovato)

if ValoreEvento soddisfa la proprietà trovato true else

ottieni ValoreEvento

Al termine del ciclo la variabile booleana trovato sarà True se un tale elemento

esiste False altrimenti.


62

Algoritmo ‘’Tutti’’

Questo algoritmo serve per stabilire se tutti i valori della successione di eventi godono di una prefissata proprietà:

ok=trueottieni ValoreEvento while ci sono ancora eventi and ok

if l’elemento non soddisfa la proprietà okfalse else

ottieni ValoreEvento

Semplicemente si cerca se esiste un elemento che non abbia la proprietà, invertendo i valori assegnati alla variabile booleana


63

ESERCIZI.1) Utilizzando i costrutti while , do..while e for, scrivere un programma che

stampi la tabella seguente: x x+3 x+7 x+11 3 6 10 14 6 9 13 17 9 12 16 20 12 15 19 23 15 18 22 26

2) Si scriva un programma che riceva da input una serie di interi non nulli e stampi su video il valore minimo, il valore massimo e la somma dei valori negativi.

3) Dato un array di N elementi scrivere una funzione che restituisce il più piccolo indice, se esiste, cui corrisponde un numero primo, zero altrimenti.

4) Dato un array di N elementi, scrivere una funzione che restituisca true se tutti gli elementi sono pari.


64

Cicli nidificati

Quando un ciclo racchiude al suo interno un altro ciclo, diciamo

di avere due cicli nidificati (nested loops). Quando il

programma viene lanciato, viene eseguito prima il ciclo più

esterno e dopo quello più interno. Ovviamente, termina prima

il loop interno e dopo quello esterno. Se un problema richiede,

per la sua soluzione, almeno due cicli nidificati, conviene

progettare prima il loop esterno e dopo quello interno.


65

Esempio Assegnato un numero intero N, compreso tra 1 e 20, rappresentare sullo schermo

un quadrato di asterischi. Per risolvere il problema dobbiamo usare due cicli nidificati; quello più esterno

fissa la riga, quello più interno la colonna.Il loop esterno lascia la stampa della linea di asterischi al ciclo interno ed al

termine di esso va a capo. Il ciclo interno stampa N asterischi.Per esempio, per N=4 si ha:****************Primo raffinamento.for ( i=0; i < N; i++ ) stampa una linea con N asterischi vai a capo

L’esempio 1 può essere facilmente completato per scrivere un programmino nel linguaggio C++ ( attenzione alle parentesi graffe! ).

Secondo raffinamento.for ( i=0; i < N; i++ ) for ( k=0; k < N; k++ ) cout<<’*’; cout<<endl;


66

Quali modifiche vanno apportate al programma precedente per rappresentare il triangolo seguente?

**********

Proponiamo un primo raffinamento:for ( i=0; i < N; i++ ) stampa una linea con i+1 asterischi vai a capo

***

*******

****

************

Esercizio.Scrivere un programma completo che, assegnato un numero intero N, disegni le seguenti figure (negli esempi N=4 ):


67

Esempio Stampare i valori comuni a due vettori V1 e V2 di lunghezza, rispettivamente N1

ed N2.Il ciclo esterno legge ogni singolo elemento di V1, si tratta dunque di un for. Nel ciclo interno, il generico l’elemento V1[i] viene confrontato con ogni

elemento di V2; se l’elemento di V1[i] viene trovato in V2, allora • si stampa l’elemento• si esce dal ciclo interno relativo a V2.

Si tratta dunque di un caso particolare dell’algoritmo ‘’ esiste’’, dove la proprietà da verificare è se il generico elemento V2[j] del vettore V2 è uguale a V1[i]

In definitiva, possiamo scrivere:for ( i=0; i < N1; i++ )k0 ; trovatofalse;while (k<N2) and not trovato

if (V1[i]=V2[k])stampa(V1[i]);trovatotrue;

elsek=k+1


68

Esercizi.

1) Scrivere il programma completo relativo all’esempio 2. In seguito variare il programma in modo tale da inserire in un nuovo vettore V di lunghezza N da determinare, dato dall’intersezione di V1 e V2. Il programma dovrà stampare alla fine il vettore V.

2) Apportare al programma opportune modifiche nel caso in cui i due vettori V1 e V2 siano:• uno ordinato in ordine crescente e l’altro no;• ambedue ordinati in ordine crescente.

Si consiglia di strutturare ogni programma in procedure e funzioni ( servendosi anche delle procedure contenute nella libreria sugli array ).

Programmazione Mod A - Cap 4 - prof. Burattini 1.

Documents

Transcript of Programmazione Mod A - Cap 4 - prof. Burattini 1.