Il problema dell ordinamento

Il problema dell’ordinamento

Il problema dell’ordinamento

• Dati n elementi sui quali si possa considerare un relazione d’ordine totale (ogni coppia di elementi è confrontabile) costruire la permutazione ordinata, vale a dire trovare una disposizione degli elementi in modo tale che si abbia:

a₁< a₂< a₃< …. < a_n

• Problema analogo è quello di considerare gli elementi ordinati in ordine decrescente.

(Capitolo 3)

Il problema dell’ordinamento

• Vedremo metodi diversi e ne calcoleremo la complessità.

• I metodi di ordinamento saranno:

-ordinamento scansione (o selezione diretta) - bubblesort

- ordinamento per inserimento - ordinamenti ricorsivi

-quicksort - mergesort

• La complessità varia da O(n²) a O(n····log2n)

Ordinamento per scansione

• Analisi.

• Vogliamo mettere gli elementi nell’ordine:

a₁< a₂< a₃< …. < a_n

• Osserviamo che:

a₁è il minimo tra gli elementi {a₁, a₂, … a_n} a₂è il minimo tra gli elementi {a₂, a₃, … a_n} . . .

a_n-1è il minimo tra gli elementi {a_n-1, a_n} a_nè al suo posto.

Ordinamento per scansione

• Progetto.

• Cerchiamo un modo per avere al primo posto il minimo tra tutti, al secondo posto il minimo tra a₂ e i rimanenti, al posto (n-1)-esimo il minimo tra a_n-1e a_n.

• Avremo una struttura iterativa che “mette a posto” gli elementi da 1 a n-1, dove “mettere a posto” significa:

mettere al posto i-esimo l’elemento minimo tra a_ie gli elementi rimanenti.

Ordinamento per scansione

mentre ci sono elementi da ordinare eseguire mettere all’i-esimo posto il minimo

degli elementi {a_i, a_i+1, …., a_n} //finementre

• La struttura iterativa “mentre ci sono elementi da ordinare” sarà un ciclo del tipo:

per i da 1 a n-1 eseguire

Ordinamento per scansione

• Cerchiamo un modo per: trovare il minimo.

• Abbiamo due strategie:

• I. considerare gli elementi

a_i e a_k con k = i+1, …, n e scambiarli se non sono nell’ordine

• II. calcolare il valore e la posizione del minimo ed eseguire un solo scambio tra a_ie il minimo trovato.

Ordinamento per scansione

• Come si effettua lo scambio del valore tra due variabili?

• Consideriamo due variabili x e y, vogliamo scambiare il loro contenuto:

prima dopo

x y x y

7 5 5 7

Ordinamento per scansione

• Non possiamo fare subito l’assegnazione x=y altrimenti x e y avrebbero lo stesso valore.

Dobbiamo utilizzare una variabile di supporto, s, dello stesso tipo di x e y, per depositare temporaneamente uno dei due valori:

1) s=x; x y

2) x=y;

3) y=s;

s

• Uno scambio si fa con 3 assegnazioni

7 5 7 7 5

Ordinamento per scansione

//ordinamento per scansione con scambio per i da 1 a n-1 eseguire

//mettere in a_iil minimo tra a_i , a_i+1 , …, a_n per k da i+1 a n eseguire

se a[i] > a[k]

allora //scambiare a_i con a_k s ← a[i]

a[i] ← a[k]

a[k] ← s //finese

//fineper

//fineper //ciclo esterno

Ordinamento per scansione

• Calcoliamo la complessità dell’algoritmo per scansione.

• L’operazione fondamentale eseguita nella struttura iterativa è il confronto: questo viene eseguito sempre, mentre lo scambio viene eseguito solo nel caso vero.

• Quanti confronti vengono eseguiti?

• Il ciclo esterno varia da 1 a n-1, il ciclo interno varia da i a n: i non è fisso e quindi il calcolo esatto è un po’ più laborioso.

Ordinamento per scansione

n° iterazione elementi n° confronti i=1 (a₁, a₂) (a₁, a₃) … (a₁, a_n) n-1 i=2 (a₂, a₃) … (a₂, a_n) n-2

…… …….

i=n-1 (a_n-1, a_n) 1

Sommiamo i confronti:

1 + 2 + 3 + …. + n-2 + n-1= n·(n-1)/2

Ordinamento per scansione

• Un modo facile per ricordare la somma (uno dei due numeri interi n o n-1 è pari) è:

(il primo + l’ultimo) ×××× (metà del numero di elementi presenti nella formula)

• Si può dimostrare la formula per induzione (progressione aritmetica).

• Verifichiamo ad esempio per n=7:

1 + 2 + 3 + 4 + 5 + 6 = (1 + 6) ××× 6/2 = 7 ×× ××× 3 =

= 21

Ordinamento per scansione

• Caso peggiore.

• All’interno dell’iterazione si fanno tutti i confronti e tutti gli scambi.

• Dati: vettore è ordinato in ordine inverso a = (8, 6, 5, 3, -2 -7)

n(n-1)/2 confronti + 3n(n-1)/2 assegnazioni Quindi O(n²/ 2).

Ordinamento per scansione

• Caso favorevole.

• Si fanno tutti i confronti e nessuno scambio

• Dati: vettore già ordinato a = (2, 4, 5, 8, 20, 34, 51) n(n-1)/2 confronti + 0 assegnazioni Quindi Ω(n²/2)

Ordinamento per scansione

• L’algoritmo di ordinamento lineare con scambio ha complessità:

• O(n²/2) nel caso peggiore (limitazione superiore)

• Ω(n²/2) nel caso favorevole (limitazione inferiore)

• Pertanto

Θ(n²/ 2)

Ordinamento per scansione

• Se vogliamo ordinare l’array tenendo conto del valore del minimo e della sua posizione, dobbiamo avere una variabile min, per memorizzare il valore minimo, e un indice imin per memorizzare la posizione.

• Possiamo anche utilizzare la sola variabile imin e accedere al valore del minimo tramite a[imin].

• Con questa seconda scelta si fanno meno assegnazioni.

• Esercizio: verificare l’affermazione.

Ordinamento per scansione

//ordinamento per scansione con minimo per i da 1 a n-1 eseguire

//mettere in a_iil minimo tra a_i , a_i+1 , …, a_n imin← i

per k da i+1 a n eseguire se a[imin] > a[k]

allora imin← k //finese

//fineper

Ordinamento per scansione

//dopo il ciclo interno si deve mettere a_imin // al posto di a_i: scambiare a_i con a_imin s ← a[i]

a[i] ← a[imin]

a[imin] ← s

//fineper //ciclo esterno

Ordinamento per scansione

• Caso peggiore.

• All’interno dell’iterazione il confronto dovrà essere sempre vero. In realtà ciò non si verifica per tutte le iterazioni, perché con lo scambio si ordina anche la seconda parte dell’array.

• Dati: vettore è ordinato in ordine inverso confronti: n (n-1) / 2

assegnazioni:

4(n-1) (ciclo esterno) + n(n-1)/2 (al più nel ciclo interno)

Ordinamento per scansione

• Caso favorevole.

• Si fanno tutti i confronti e solo le assegnazioni del ciclo esterno.

• Dati: vettore già ordinato

confronti: n (n-1) / 2

assegnazioni: 4(n-1) (solo nel ciclo esterno)

Ordinamento per scansione

• Le operazioni dei due algoritmi hanno un costo diverso: uno scambio richiede tre assegnazioni; lo scambio è una operazione

“costosa”.

• Confrontiamo le due versioni:

• Il numero di confronti nei due algoritmi è uguale ed è sempre:

n(n-1) / 2

(un confronto è “più costoso” di una assegnazione)

Ordinamento per scansione

• Varia il numero di assegnazioni:

nel caso favorevole si ha:

0 (scambio) 4(n-1) (minimo) nel caso peggiore si ha:

3(n-1)n /2 (scambio) (n-1)n / 2 + 4(n-1) (minimo)

• Verificare che per n>4

3(n-1)n /2 > (n-1)n / 2 + 4(n-1)

Ordinamento bubblesort

• Si eseguono confronti tra elementi successivi:

(a₁, a₂) (a₂, a₃) (a₃, a₄) … (a_n-1, a_n) e se gli elementi non sono nell’ordine allora si scambiano. Con questa tecnica la componente con valore più grande va in fondo (al posto di a_n):

(9, 2, 8, 10, 1, 4) diventa (2, 8, 9, 1, 4, 10)

• Si ricomincia dell’inizio, dalla coppia (a₁, a₂), e si “mette a posto” a_n-1, poi a_n-2, … , infine a₂.

Ordinamento bubblesort

• Si può partire dalla fine del vettore, iniziando il confronto dalla coppia (a_n-1, a_n) e andare indietro. Con questa tecnica la componente con valore più piccola va al posto di a₁:

(9, 2, 8, 10, 1, 4) diventa (1, 9, 2, 8,10, 4)

• In questo caso si ricomincia nuovamente dalla coppia (a_n-1, a_n) e si mette in ordine a₂, poi a₃si continua fino ad a_n-1.

Ordinamento bubblesort

• Progetto.

• Consideriamo la prima versione: si inizia sempre dalla coppia (a₁, a₂); l’indice del ciclo che esegue i confronti è l’indice della prima componente della coppia. Alla prima iterazione varia da 1 a n-1 (si mette in ordine a_n), nella seconda iterazione l’indice varia da 1 a n-2 (si mette in ordine a_n-1); nella terza iterazione l’indice varia da 1 a n-3 (si mette in ordine a_n-2);

ecc. nell’ultima iterazione l’indice varia da 1 a n-(n-1)=1 (si mette in ordine a₂); con l’ultimo confronto è in ordine anche a₁.

Ordinamento bubblesort

//ordinamento bubblesort: prima versione per i da 1 a n-1 eseguire

per k da 1 a n-i eseguire se a[k] > a[k+1]

allora //scambiare a_k con a_k+1 s ← a[k]

a[k] ← a[k+1]

a[k+1] ← s //finese

//fineper //fineper

Ordinamento bubblesort

• Quanti confronti?

n° iterazione elementi n° confronti

i=1 (a₁, a₂) (a₂, a₃) … (a_n-1, a_n) n-1 i=2 (a₁, a₂) … (a_n-2, a_n-1) n-2

…… …….

i=n-1 (a₁, a₂) 1

Ordinamento bubblesort

• I confronti vengono sempre eseguiti: se il confronto risulta vero si esegue lo scambio, se risulta falso non si esegue lo scambio.

• Sommiamo i confronti:

1 + 2 + 3 + …. + n-2 + n-1= n·(n-1)/2 (come per l’ordinamento per scansione)

Ordinamento bubblesort

• Quante assegnazioni?

• Caso favorevole.

0 assegnazioni (già ordinato)

• Caso peggiore.

3·n·(n-1)/2 (ordine inverso)

• Pertanto anche il bubblesort è Θ(n²/ 2).

Confronto tra i vari metodi di ordinamento

• Consideriamo il seguente array e vediamo come si muovono gli elementi (alla prima iterazione).

a = ( 40, 20, 1, 7, 10, 0) n=6 1) lineare con scambio

40 20 1 7 10 0 scambio 40, 20 20 40 1 7 10 0 scambio 20, 1 1 40 20 7 10 0 scambio 1, 0 0 40 20 7 10 1

Confronto tra i vari metodi di ordinamento

2) lineare con minimo 40 20 1 7 10 0

imin 1 2 3 6 scambio 40, 0

0 20 1 7 10 40 3) bubblesort (massimo in fondo)

40 20 1 7 10 0 scambio 40, 20 20 40 1 7 10 0 scambio 40, 1 20 1 40 7 10 0 scambio 40, 7 20 1 7 40 10 0 scambio 40, 10 20 1 7 10 40 0 scambio 40, 0

20 1 7 10 0 40

Confronto tra i vari metodi di ordinamento

4) bubblesort (minimo in testa)

40 20 1 7 10 0 scambio 0, 10 20 40 1 7 0 10 scambio 0, 7 20 1 40 0 7 10 scambio 0, 40 20 1 0 40 7 10 scambio 0, 1 20 0 1 40 7 10 scambio 0, 20

0 20 1 40 7 10

Varianti del bubblesort

• Osserviamo che nel bubblesort si confronta una componente con la successiva, a_kcon a_k+1; pertanto, se non ci sono scambi significa che l’array è ordinato.

• Esempio.

a= (2, 4, 5, 8, 21, 34, 58, 90)

• Le coppie considerate sono:

(2, 4) (4, 5) (5, 8) (8, 21) (21, 34) (34, 58) (58, 90)

Varianti del bubblesort

• Infatti, per la proprietà transitiva della relazione d’ordine < si ha che:

se a_k< a_k+1 e a_k+1< a_k+2 allora a_k< a_k+2

• Esercizio1. Costruire una variante di bubblesort che tenga conto che se non si fanno scambi l’array è ordinato.

Suggerimento. Utilizzare una variabile logica ordinato da inizializzare a falso e da inserire nel predicato del ciclo esterno: se non ci sono scambi ordinato deve essere vero.

Varianti del bubblesort

• Esercizio2.

• Costruire una variante che tenga conto della posizione dell’ultimo scambio.

• Esempio.

a = ( 3, 1, 2, 5, 7, 8, 9, 12, 34, 35) Nel ciclo interno si effettuano gli scambi:

(3, 1) diventa (1, 3) (3, 2) diventa (2, 3)

i successivi confronti: (3, 5), (5, 7), (7, 9) , ecc.

non comportano altri scambi.

Varianti del bubblesort

• Memorizzando la posizione dell’ultimo scambio non si “guarda” più la parte di array già ordinato.

• Suggerimento. Chiamare: inizio e fine gli estremi degli indici che limitano la parte di array da ordinare, sc una variabile che memorizza la posizione dell’ultimo scambio;

inizializzare sc con il valore di inizio.

• Quando inizio = fine significa che l’array è ordinato.

Complessità delle varianti del bubblesort

• Per entrambe queste varianti la complessità nel caso favorevole è inferiore a quella del caso senza la variante.

• Infatti, se si fornisce un array già ordinato, dopo la prima iterazione il ciclo termina

• nel primo caso con ordinato=vero

• nel secondo caso con inizio=fine

• Pertanto il caso favorevole è Ω(n).

• Il caso peggiore è sempre O(n²/2).

Esercizio

• Si calcoli la complessità dell’algoritmo seguente, considerando i casi a>b, a=b, a<b;

specificando il numero di assegnazioni e di confronti nei tre casi.

• Si supponga n>0.

• Quale sarebbe il valore di a e b se si stampassero a e b alla fine della struttura iterativa “mentre”?

Esercizio

Algoritmo

definizione variabili a, b, n, i, k intero continua logico acquisire valori per a, b, n

continua ← vero i ← 0

mentre i ≠ n e continua eseguire i ← i+1

se a < b

allora a ← a-1

Esercizio

altrimenti se a == b allora

per k da 1 a n eseguire a ← a+1 b ← b+1 //fineper

altrimenti continua ← falso //finese

//finese //finementre

Costanti

L’uso delle costanti

• Questo programma effettua un cambio di valuta

• Un utente potrebbe chiedersi quale sia il significato del numero 0.71 usato nel programma, ma anche se questo valore non varierà nel tempo.

int main(){//cambio valuta double dollaro = 2.35;

double euro = dollaro * 0.71;

cout<<dollaro<<" dollari =

"<<euro

<<" euro \n"; }

L’uso delle costanti

• Così come si usano nomi simbolici descrittivi per le variabili, è opportuno assegnare nomi simbolici anche alle costanti utilizzate nei programmi.

• Si hanno dei vantaggi:

1. si aumenta la leggibilità

2. si evitano molte sostituzioni, se il valore della costante deve cambiare

3. non lo si confonde con altri valori.

L’uso delle costanti

1. Aumenta la leggibilità: chiunque usi il nostro programma capisce che 0.71 è il fattore di conversione

int main(){

const double EURO_DOLLARO = 0.71;

double dollaro = 2.35;

double euro = dollaro*EURO_DOLLARO;

cout<<dollaro<<" dollari =

"<<euro

<<" euro \n"; }

L’uso delle costanti

2. Si evitano molte sostituzioni: il valore può cambiare e lo dobbiamo cambiare in ogni istruzione in cui viene usato:

int main(){

const double EURO_DOLLARO = 0.90;

double dollaro1 = 2.35;

double euro1 = dollaro1*EURO_DOLLARO;

double dollaro2 = 3.45;

double euro2 = dollaro2*EURO_DOLLARO;

//cout<<. . . }

L’uso delle costanti

3. Si può confondere con altri valori:

int main(){

const double EURO_DOLLARO = 0.75;

double dollaro1 = 2.35;

double euro1 = dollaro1*EURO_DOLLARO;

double costocaffe = 0.90;

// cout<<. . . }

Definizione di costante

• Sintassi.

(par 13.4.1)

const nometipo NOME_COSTANTE = espressione;

• NOME_COSTANTE è il nome che vogliamo dare alla costante.

• Spesso il nome delle costanti viene scritto usando tutte le lettere maiuscole (es. EURO_DOLLARO componendo due nomi con la sottolineatura); ci si deve ricordare che il linguaggio distingue le maiuscole dalle minuscole.

Definizione di costante

• Le costanti sono identificate dalla parola chiave const.

• In fase di definizione si deve specificare il tipo della costante e le si attribuisce un

(espressione): tale valore non

• Il tentativo di modificare il valore della costante, dopo l’inizializzazione, produce un errore (semantico) durante la compilazione.

Definizione di costante

• Un uso frequente delle costanti si ha nella definizione degli array: quando si definisce un array si deve sempre indicare, tramite una costante, il numero massimo delle componenti:

il compilatore riserva in memoria uno spazio per quel numero di componenti. Per aumentare la leggibilità, permettere facili sostituzioni e non confondere con altri valori si può definire l’array nel modo seguente:

const int dim = 100;

double a[dim];

Matrici: array a due dimensioni

Matrici

• Vogliamo rappresentare informazioni omogenee (dello stesso tipo) ma descritte da una coppia di indici:

a_ik i = 1, 2, …, n k = 1, 2, … , m matrice A di n righe e m colonne:

a₁₁ a₁₂ … a_1m A = ………….

a_n1 a_n2 …. a_nm

Matrici

• Molti problemi matematici fanno uso di matrici; uno dei problemi più frequenti è la risoluzione di un sistema lineare di n equazioni in n incognite (estensione del sistema 2×××2 che rappresenta il determinare il × punto di intersezione di due rette del piano) e che si può rappresentare algebricamente come prodotto “matrice ×××× vettore”:

A x = b

Matrici

• Definizione delle matrici in C++.

• Una matrice è un array di array:

int a[5][4];

il primo (5) è l’indice delle righe, il secondo (4) è l’indice delle colonne.

• Poiché la matrice è un array l’indice che descrive le righe (e le colonne) assume valori a partire da 0 fino a dimmax-1; quindi la matrice avrà 5 righe, numerate da 0 a 4, e 4 colonne, numerate da 0 a 3.

Matrici

• La matrice a ha le seguenti componenti:

a[0][0] . . . a[0][3]

a[1][0] . . . a[1][3]

. . .

a[4][0] . . . a[4][3]

• Dopo aver scelto le dimensioni massime per righe e colonne, la matrice può avere n righe ed m colonne, con n ed m compatibili (nell’esempio compatibili con 5 e 4 ).

Matrici

• Per accedere ad un elemento di un array bidimensionale si devono indicare entrambi gli indici:

a[2][1] = 67;

e tali indici devono essere compatibili con la dimensioni dell’array.

• Per acquisire gli elementi di una matrice e per stamparli si deve usare una struttura iterativa per le n righe ed un’altra per le m colonne: gli elementi vengono letti e scritti uno alla volta.

Matrici

//lettura di una matrice i=0,1,.., n-1 k=0, 1, …,m-1 cin>>n>>m; //n<=5, m<=4 for(i=0; i<n; i++)

for(k=0; k<m; k++) cin>>a[i][k];

//lettura di una matrice i=1, 2,...n k=1, 2, …, m cin>>n>>m; //n<=4, m<=3 for(i=1; i<=n; i++)

for(k=1; k<=m; k++) cin>>a[i][k];

Matrici

• Se n=m la matrice si dice quadrata.

• Gli elementi con indice uguale individuano un array che si chiama diagonale della matrice:

diagA = [a₁₁, a₂₂, …, a_nn]

• Se due matrici A e B hanno lo stesso numero di righe e colonne si può costruire la matrice somma C:

C=A+B c_ik= a_ik+ b_ik

Matrici

• Date due matrici A (n ××× p) e B (p ×× ×× m) se il × numero di colonne di A è uguale al numero di righe di B allora si può definire la matrice C = A ×××× B prodotto “righe ××× colonne”:×

p

c_ik=

∑

• Consideriamo solo matrici quadrate, quelle maggiormente usate nella matematica.

Matrici

• Una matrice quadrata A possiede n²elementi, quindi difficilmente gli algoritmi su matrici avranno una complessità inferiore a O(n²).

• L’algoritmo per costruire la somma di due matrici è Θ(n²).

• L’algoritmo per costruire il prodotto di matrici, applicando la definizione, è Θ(n³); ne esistono di complessità O(n^α) con 2< α < 3.

Matrici

• L’algoritmo per risolvere il sistema lineare Ax=b (data la matrice A e il vettore b determinare il vettore x) noto come “regola di Cramer” ha complessità O(n!).

• Esistono “metodi diretti” con i quali si trasforma la matrice in una equivalente, per il problema di risolvere il sistema lineare, e che richiedono O(n³) operazioni e “metodi iterativi” che “approssimano” la soluzione in O(n²) operazioni.

Matrici

• L’identità del prodotto tra matrici si chiama matrice identica e viene indicata con I; è una matrice con 1 sulla diagonale e 0 altrove.

• Esercizio. Scrivere un algoritmo per costruire la matrice identica che esegua solo (n² + n) assegnazioni.

• Non eseguire l’ovvio controllo:

se i ≠ k

allora ….0 altrimenti … 1

che porterebbe a n²assegnazioni + n² confronti

Matrici

• Il prodotto tra matrici non è commutativo:

A ××× B ≠ B ×× ×× A ×

fatta eccezione del caso in cui una delle due sia la matrice I oppure che le due matrici siano uguali.

• La matrice costruita a partire dalla matrice A scambiando le righe con le colonne si chiama matrice trasposta di A, e si indica con A^T:

a^T_ik= a_ki

Matrici

• Una matrice si dice simmetrica se:

a_ik= a_ki ∀∀∀∀ i, k

• Se A = A^T allora A è simmetrica.

• Due matrici A e B sono uguali se:

a_ik= b_ik ∀∀ i, k∀∀

Matrici

• Esercizio.

• Scrivere un algoritmo (efficiente) per verificare se due matrici sono uguali.

• Scrivere un algoritmo (efficiente) per verificare se una matrice è simmetrica.

• Suggerimento: se una proprietà deve essere verificata per ogni elemento, essa è falsa se esiste un solo elemento che non la verifica.

Matrici

• Esercizi per imparare ad usare gli indici delle matrici.

1) date due matrici A(n ××× m) e B(p ×× ××× q) verificare se B è contenuta in A

1 2 3 5 0 -1

A = 4 0 -1 7 B =

3 2 1 4 2 1

B è contenuta invece B1= 1 2 non è contenuta

3 2

Matrici

2) Dato un cruciverba A(n××××m), matrice di caratteri, e una parola P composta da q caratteri verificare se la parola P sta nel cruciverba per righe o per colonne.

Suggerimento. Verificare che le dimensioni siano compatibili, cercare la prima componente di P se è presente in A ed eseguire la verifica solo se la lunghezza della parola non supera il numero di righe o di colonne che restano da verificare.

Matrici

3) Dati n numeri a₁, a₂, a₃, …, a_n determinare quanti sono minori a₁, quanti minori di a₂, di a₃, … e in quali posizioni si trovano (per ogni i si deve poter memorizzare un array di indici) e quali sono (per ogni i si deve poter memorizzare un array di valori) .

Array di stringhe

• Per gestire un array di stringhe, poiché le stringhe sono a loro volta degli array, si deve utilizzare una matrice.

• Esempio. Vogliamo memorizzare i nomi degli studenti di questo corso.

• Supponiamo che la stringa che rappresenta il nome e cognome sia memorizzabile in 30 caratteri e che il numero totale degli studenti non superi 190.

Array di stringhe

• Andiamo a definire un array di caratteri dove la prima componente rappresenta il

di studenti e la seconda rappresenta la stringa nome_cognome:

char corsoIEIEN[190][31];

• La componente i-esima corsoIEIEN[i]

rappresenta il nome_cognome dell’i-esimo studente.

Array di stringhe

• Per acquisire gli elementi dell’array si deve utilizzare una struttura iterativa, mentre la stringa viene acquisita come unità:

for(i=0; i<190; i++){

cin>>corsoIEIEN[i];

cout<<corsoIEIEN[i]<<endl;

}

Array di stringhe

• Esercizio.

• Acquisire e stampare dei nomi di persona e successivamente metterli in ordine alfabetico.

Stampare quindi l’elenco ordinato.

• Utilizzare uno dei metodi di ordinamento visti ricordando che il confronto tra stringhe si effettua con la funzione strcmp:

strcmp(corsoIEIEN[i], corsoIEIEN[k]) e che la funzione restituisce un valore positivo,

negativo o nullo.

• Per le assegnazioni usare strcpy.

Rappresentazione dell’informazione

numerica

Rappresentazione dell’informazione numerica

• Esistono vari tipi di numerazione.

• Primitiva: sequenza di simboli tutti uguali;

numerazione nei dadi, carte da gioco, …

• Additiva: ogni simbolo ha un valore fisso; si esegue una somma dei valori per determinare il numero; numerazione dei romani, greci, egiziani,…

Rappresentazione dell’informazione numerica

• Posizionale: le cifre che compongono la sequenza di simboli che rappresentano il numero hanno un valore che varia con la posizione, si esegue poi la somma; è la numerazione attuale.

• Nella rappresentazione posizionale il numero viene scritto con una notazione del tipo seguente:

N = c_nc_n-1

… c

… c

Rappresentazione dell’informazione numerica

• Il valore di ogni cifra è:

cifra ×

× × b ×

dove b è la base del sistema di numerazione (con b ≠ 0,1) e p è la posizione della cifra.

• Esempio.

3 300 0.03 unità centinaia centesimi

Rappresentazione dell’informazione numerica

• Il valore del numero N viene dalla somma:

N = c_nbⁿ+ c_n-1b^n-1+ … + c₀b⁰+

+ c_-1b^-1+ …. + c_-mb^-m

• con c_k= 0, 1, 2, …, b-1

• N si ottiene quindi sommando i valori c_kb^k.

• Formula di rappresentazione dei numeri (per i numeri con infinite cifre dopo la virgola, si ha una serie) (Capitolo 7).

Rappresentazione dell’informazione numerica

• Si possono considerare varie basi.

• b=10 sistema decimale c_k= 0, 1, 2,.., 9

• b=2 sistema binario c_k= 0, 1

• b=8 sistema ottale c_k= 0, 1, 2,.., 7

• b=16 sistema esadecimale

c_k= 0, 1, 2,.., 9, A, B, C, D, E, F

• b=60 sistema sessagesimale: si usa per misurare il tempo; non si usano 60 simboli diversi, ma i simboli sono scritti in decimale con due cifre: 00, 01, 02, … 57, 58, 59.

Rappresentazione dell’informazione numerica

• Cifre delle basi 2, 10, 8 , 16

b=2 b=10 b=8 b=16 4 bit

0 0 0 0 0000

1 1 1 1 0001

2 2 2 0010

3 3 3 0011

4 4 4 0100

5 5 5 0101

6 6 6 0110

7 7 7 0111

8 8 1000

Rappresentazione dell’informazione numerica

b=2 b=10 b=8 b=16 4bit

9 9 1001

(10) A 1010 (11) B 1011 (12) C 1100 (13) D 1101 (14) E 1110 (15) F 1111

• Per scrivere in base 2 i numeri della base 16 = 2⁴ occorrono 4 bit.

Cambi di base

• Passaggio da base b a base 10.

• Il numero è scritto con le cifre della base b: si rappresentano le cifre nella base 10 e si fanno i calcoli in base 10.

• Esempio. b=2

a) 110₂= 1××××2² + 1××××2¹ + 0××××2⁰ = 4 + 2 = 6₁₀ b) 11₂= 1×××2× ¹ + 1×××2× ⁰ = 2 + 1 = 3₁₀ c) 1100₂= 1××××2³ + 1××××2² + 0××××2¹+ 0×××2× ⁰ =

= 8 + 4 = 12₁₀

Cambi di base

• Le regole per la base 10 valgono anche nelle altre basi:

- spostare la virgola a destra o aggiungere uno zero destra vuole dire “moltiplicare” per la base: b) → a) e a) → c)

- spostare la virgola a sinistra o togliere uno zero sinistra vuole dire “dividere” per la base:

a) → b) e c) → a) .

Cambi di base

• Esempio. b=7

152₇= 1 ××××7²+ 5 ×××7× ¹+ 2 ××××7⁰

= 49 + 35+ 2 = 86₁₀

25₇ = 2 ×××7× ¹+ 5 ××××7⁰ = 14 + 5 = 19₁₀

• Esempio. b=5

444₅= 4 ×××5× ²+ 4 ××××5¹+ 4 ××××5⁰=

= 4 ××××25 + 20 + 4 = 100 + 24 = 12410

Cambi di base

• Esempio. b=8

20.4₈= 2 ××××8¹+ 0 ××××8⁰ + 4 ××××8^-1 =

= 16 + 0 + 4/8 = 16.5₁₀

• Esempio. b=16

AF.C₁₆= 10 ×××16× ¹+ 15 ××××16⁰+ 12 ×××16× ^-1=

= 160 + 15 + 12/16 =

= 175 + 3/4 = 175.75₁₀

Cambi di base

• Esempio. b=16

30B.A₁₆= 3 ××××16²+ 0××××16¹+ 11××××16⁰+ 10 ×××16× ^-1

= 3 ××××256 + 0 + 11 + 10/16 =

= 768 + 11 + 0.625 =

= 779.625₁₀

• Si scrivono le cifre del numero nella base 10 (che per b<10 coincidono con quelle della base 10) e anche la base b (in base 10) e si fanno i calcoli in base 10.

Cambi di base

• Passaggio da base 10 a base b.

• Se sapessimo fare con disinvoltura i conti nella base b potremmo scrivere le cifre in base b ed eseguire i conti in base b in maniera analoga.

• Per poter fare sempre i conti in base 10 usiamo la seguente regola: consideriamo il numero suddiviso nella sua parte intera e parte frazionaria

PI . PF = c_nc_n-1… c₀ . c_-1 c_-2 … c_-m

Cambi di base

• PI : si divide PI e i successivi quozienti per la base e si prendono i resti

• PF : si moltiplica PF e le successive parti frazionarie per la base si prendono le parti intere.

• Sia N₁₀= c₃ c₂ c₁ c₀ . c_-1 c_-2c_-3 in base b; noi vogliamo trovare le cifre c_k.

PI = c₃b³+ c₂b²+ c₁b¹+ c₀b⁰=

= b (c₃b²+ c₂b¹+ c₁ b⁰) + c₀ // b⁰=1 dividendo per b si ottiene:

c₃b²+ c₂b¹+ c₁ quoziente e c₀ è il resto

Cambi di base

si prosegue con il quoziente trovato:

c₃b²+ c₂b¹+ c₁ = b (c₃b¹+ c₂) + c₁ dividendo per b c₁ è il resto c₃b + c₂= b (c₃) + c₂ c₂ è il resto c₃= b·0 + c3 c₃ è il resto

(quoziente = 0 perché c₃< b)

• Abbiamo estratto nell’ordine c₀, c₁, c₂, c₃ che andranno scritti:

c₃c₂c₁c₀.

Cambi di base

PF = c_-1b^-1+ c_-2b^-2+ c_-3b^-3 = (finita)

= b^-1(c_-1 + c_-2b^-1+ c_-3b^-2) moltiplicando per b si ottiene:

b·b^-1(c_-1 + c_-2b^-1+ c_-3b^-2) =

= c_-1 + c_-2b^-1+ c_-3b^-2 c_-1 è la parte intera

c_-2b^-1+ c_-3b^-2 la parte frazionaria

Cambi di base

si prosegue con la parte frazionaria trovata:

c_-2b^-1+ c_-3b^-2 = b^-1(c_-2 + c_-3b^-1) c_-2 è la parte intera moltiplicando per b

b· c-3b^-1 = c-3 c_-3 è la parte intera

• Abbiamo estratto nell’ordine c_-1, c_-2, c_-3 che andranno scritti:

. c_-1c_-2c_-3

Cambi di base

• Esempi.

227₁₀= ? ₂ 1 1 1 0 0 0 1 1 ₂

resti

227 2

113 1 56 1

28 0

14 0

7 0

3 1

1 1

0 1

Verifica: 2⁷+ 2⁶+ 2⁵+ 2¹+ 2⁰= = 128 + 64 + 32 + 2 + 1 = = 227

Cambi di base

68 0 34 0

17 0

8 1

4 0

2 0

1 0

0 1

Verifica: 2⁷+ 2³ = = 128 + 8 = 136

Cambi di base

1.0 1

la parte frazionaria è 0 Verifica: 1 /2 + 1 /4 = 3 / 4 = = 0.75

Cambi di base

1.6 : 0.6 ××× 2 × 1 1.2 : 0.2 ××× 2 × 1 0.4 : 0.4 ××× 2 0×

0.8 …. le parti frazionarie si ripetono: c’è un periodo: 0110 Verifica: 1 / 4 + 1 /8 + 1 / 64 + … = = ? il numero è approssimato

Cambi di base

0.4 : 0.4 ×××× 2 0 0.8 : 0.8 ×××× 2 0 1.6 : 0.6 ×××× 2 1

1.2 : 0.2 ×××× 2 1 0.4 …. periodo è 0011

0.1 è periodico in base 2

Numeri frazionari

periodici

Numeri frazionari periodici

• Abbiamo visto che 0.1₁₀ = 0.0 0011₂

• Consideriamo un numero razionale:

p/q con p e q naturali e primi fra loro e q≠0 Eseguendo la divisione

p : q = …

si può ottenere una rappresentazione finita oppure infinita e periodica della parte frazionaria.

a) Se i fattori primi di q sono solo quelli della base, allora la rappresentazione è finita.

Numeri frazionari periodici

b) Se tra i fattori primi di q ci sono fattori diversi dai fattori della base, allora la rappresentazione è infinita e periodica.

• Vediamo per la base b = 10 = 2····5

• Caso a) q = 2^k· 5^h

sia n = max(h, k); allora si può scrivere p m con m naturale q = 10ⁿ m = c_sc_s-1…. c₁c₀

Numeri frazionari periodici

• Spostando la virgola di n posti verso sinistra a partire da c₀si trova la rappresentazione finita, perché finito è il numero di cifre di m.

• Esempio.

31 / 20 = 31 / (2²· 5 ) = (31 · 5)/ (2²· 5²) =

= 155 / 10² = 1.55

7 / 25 = 7 / 5² = (7 · 2²)/ (2²· 5²) =

= 28 / 10² = 0.28

Numeri frazionari periodici

• Caso b) q = a^k· b^h con a e b anche diversi da 2 e 5; ne segue che non si potrà scrivere q come potenza di 10.

Quando si esegue la divisione:

p = q k₁+ k₂ 0 ≤ k2< q

se le cifre di p sono terminate si “abbassa lo 0”

e si prosegue con la divisione. Il resto k₂, variando in un intervallo limitato, ad un certo punto si ripete: si ha pertanto il periodo.

Numeri frazionari periodici

• Esempio.

10 / 3 10 : 3 = 3. 3 3 3 …..

10

1 1 ….. periodo 5 / 7 5 : 7 = 0.714285 714……

50 10

30 20

60 40

5 ….. periodo

Numeri frazionari periodici

• Un numero periodico in base 10 (ci sono fattori diversi da 2 e 5) è anche periodico in base 2.

• Un numero non periodico in base 10 può essere periodico in base 2 (ad esempio 0.1, 0.4).

• I numeri irrazionali, i reali che non si possono scrivere come quoziente di due interi, hanno una rappresentazione infinita e non periodica.

Passaggi 2   2  

• 2ⁿ→2 : si espandono le cifre della base 2ⁿ in gruppi di n bit 16 = 2⁴→ 2

• 2 →2ⁿ : si raggruppano le cifre della base 2 n a n 2 = 2 → 2⁴

• Esempio.

A91.2₁₆ = ? ₂ = ? ₈

A 9 1 . 2 base 16

1010 1001 0001 . 0010 base 2

5 2 2 1 . 1 base 8

Passaggi 2   2  

• Esempio.

2E0.FC₁₆ = ? ₂ = ? ₈

2 E 0 . F C base 16

0010 1110 0000 . 1111 1100 base 2

1 3 4 0 . 7 7 base 8

Operazioni in base 2

Operazioni in base 2

• Addizione.

0 + 0 = 0 1 + 0 = 0 + 1 = 1 1 + 1 = 1(riporto) 0

Esempio.

1 5 + 5 2¹ 0

1 1 1 1 + 1 0 1 1 0 ¹1 ¹0 ¹0

Operazioni in base 2

• Sottrazione.

0 - 0 = 0 1 - 0 = 1 0 - 1 = 1(prestito)0 - 1 = 1 Esempio.

2¹0 - 5 1 5

1¹ 0¹ 1¹ 0¹ 0 - 0 1 0 1 0 1 1 1 1

Esercizio

• Esercizio.

• Risolvere l’equazione 231_x= 45₁₀

vale a dire: determinare la base x in modo da soddisfare l’uguaglianza.

• Soluzione. Utilizzando la formula di rappresentazione dei numeri abbiamo:

2 ⋅⋅⋅⋅ x²+ 3 ⋅⋅⋅⋅ x¹+ 1 = 45

2x²+ 3x - 44 = 0 x₁= -11/2 x₂=4 Pertanto la soluzione è: x = 4.

Verifica: 2 ⋅⋅⋅⋅ 16 + 3 ⋅⋅⋅⋅ 4 + 1 = 32 + 12 + 1 = 45

Esercizio

• Esercizio.

• Un matematico incontra un extraterrestre e gli pone il problema di trovare le soluzioni della seguente equazione:

x²- 13x + 36 = 0

L’extraterrestre dice che le soluzioni sono: 5 e 6.

Quante dita ha l’extraterrestre?

Esercizio

• Soluzione.

• La base 10 corrisponde al numero delle nostre dita. Per l’extraterrestre i numeri 1, 13, 36 sono nella base b che corrisponde al numero delle sue dita.

Poiché la risposta è 5 e 6, che sono anche numeri della base 10, ricordando

x²– s x + p = 0 s = 11 e p = 30 si ha:

13_b= 11₁₀ 36_b= 30₁₀ e pertanto b=8.

Soluzione esercizio

Soluzione esercizio

• Caso n = 0 .

i = 0, quindi il predicato “mentre i ≠ 0 …” è falso: il ciclo non viene eseguito.

• Caso n < 0 .

se a < b il ciclo non termina: a diminuisce e quindi rimane minore di b

se a = b il ciclo non termina: entrambi crescono di 1

se a > b il ciclo termina: continua diventa falso.

Soluzione esercizio

• Caso n > 0 .

• Caso a < b .

Viene eseguita l’istruzione a ← a-1, quindi è ancora a < b; il ciclo termina quando i = n; il numero di operazioni è:

2t_a + (n+1) t_p + nt_a + nt_c + nt_a ⇒⇒⇒⇒ c·n

continua← i← a<b a← i←

b non varia, a diventa a-n

Soluzione esercizio

• Caso a > b .

Viene eseguita l’istruzione continua ← falso, quindi il ciclo termina; il numero di operazioni è:

2t_a + t_p + t_a + t_c + t_c + t_a+ t_p⇒⇒⇒⇒ costante

continua← i← a<b a = b continua←

i←

b non varia, a non varia

Soluzione esercizio

• Caso a = b.

Vengono eseguite le istruzioni a←a+1 e b←b+1; il ciclo interno viene eseguito n volte e il ciclo esterno termina quando i = n; il numero di operazioni è:

2t_a + (n+1) t_p + nt_a + nt_c + n t_c + n(n+1) t_p+

continua← i← a<b a=b i←

+ 2 n²t_a ⇒⇒ c·n⇒⇒ ²

a←

b←

a diventa a + n² , b diventa b + n²