Fondamenti di Informatica

lesson 16

Sort 2012/05/17

Prof. Emiliano Casalicchio emiliano.casalicchio@uniroma2.it

Esami   Appelli ufficiali (Prova Scritta - Prova Pratica)

 11-13 Luglio (ore 9:00)  25-27 Luglio (ore 9:00)

  Regole

 Alla prova pratica si accede solo se si supera la prova scritta (ossia si prende la sufficienza = 18/30)

2

Appello straordinario

  Apello straordinario (per chi si deve laureare a luglio)

 18 Giugno - 21 Giugno (orario lezione, verb. a luglio)

  Regole

 Tutti possono partecipare all’appello staordinario  Chi partecipa all’appello straordinario potra’

partecipare solo ad 1 appello ordinario

3

Esercizi

  Dato l’andamento giornaliero dello spread degli ultimi 2 anni

  costruire la top 10 ordinata per valore assunto dallo spread e la relativa data

  Ordinare gli elementi dell’agenda (nome, cognome, numero di telefono) in ordine alfabetico cresente per cognome e nome

  Dato un sudoku completato, verificare che la soluzione sia corretta. Regole:

  matrice 9x9 divisa in sottomatrici 3x3   ogni sottomatrice deve contenere elementi da 1 a 9

senza ripetizioni   ogni riga deve contenere numeri da 1 a 9 senza

ripetizioni   ogni colonna deve contenere i numeri da 1 a 9 senza

ripetizioni 4

Esercizi: Spread

  Dato l’andamento giornaliero dello spread degli ultimi 2 anni si chiede di determinare

  la top 10 ordinata per valore assunto dallo spread   la top 10 ordinata per data   in entrambi I casi restituire sia il valore dello spread sia

la data

5

Analisi del problema: Spread

  rappresentazione dei dati

  (data,spread)   rappresentazione della data

 gg, mm, aaaa in struttura?  aaaammgg come numero?

  rappresentazione della collezione dei dati

 array di strutture? matrice 2xn? 2 array?   scegliamo una matrice 2xn   rappresentazione della data aaaammgg   operazioni

 sort + filter

6

Soluzione: spread.m

spreads=[234 233 220 238 257 245 257 259 300 320 ... 347 356 470 397 350 300 297 20110701 20110702 20110703 20110704 20110705 ... 20110706 20110707 20110708 20110709 20110710 ... 20110711 20110712 20110713 20110714 20110715 ... 20110716 20110717]; spreads_sorted=myBubbleSort(spreads,1,'des'); if length(spreads_sorted)>=10 top10(1,:)=spreads_sorted(1,1:10); top10(2,:)=spreads_sorted(2,1:10); else top10=spreads_sorted; end

7

myBubbleSort

function v = myBubbleSort( v, row ,order) %Sort the array v along the row specified in the input. %INPUT: a vector of numbers v % a row index (1 or 2) % order 'asc' ascending 'des' descending %OUTPUT: a vector v of number sorted in descending order for i=1:length(v)-1 scambio=false; for j=2:length(v)-i+1 switch order case 'des' if v(row,j-1)<v(row,j) x1=v(1,j); x2=v(2,j); v(1,j)=v(1,j-1); v(2,j)=v(2,j-1); v(1,j-1)=x1; v(2,j-1)=x2; scambio=true; end

8

myBubbleSort

case 'asc' if v(row,j-1)>v(row,j) x1=v(1,j); x2=v(2,j); v(1,j)=v(1,j-1); v(2,j)=v(2,j-1); v(1,j-1)=x1; v(2,j-1)=x2; scambio=true; end end end if ~scambio break; end end end

9

Esercizi

  Ordinare gli elementi di un’agenda (nome, cognome, numero di telefono) in ordine alfabetico cresente per cognome

10

Analisi del problema

  reppresentazione dell’agenda

 struct   operazioni

 sort su stringhe

11

confronto tra stringhe

>> s1='asfsae’; >> s2='werdf'; >> s1>s2 ??? Error using ==> gt Matrix dimensions must agree. >> s1(1:min(length(s1),length(s2)))>s2(1:min(length(s1),length(s2))) ans = 0 1 0 1 0 >> strcmp(s1,s2) ans = 0 12

confronto tra stringhe

s1= [ B o s s i ] s2= [ B i s i o ] se s1(1) < s2(1) allora s1 < s2 se s1(1) > s2(1) allora s1 > s2 altrimenti devo confrontare s1(2:end) s2(2:end)

13

Confronto tra stringhe

function r=gtStr(s1,s2) %compare s1 and s2 and return true if s1 > s2 % the output is a boolean r=false; l = min(length(s1),length(s2)); if s1(1)>s2(1) r=true; elseif s1(1)<s2(1) r=false; else if l>1 gtStr(s1(2:l),s2(2:l)); end end end

14

Funzione ricorsiva

Vedremo i dattagli la

prossima volta

Soluzione del problema

% Inizio Script %Ordinamento agenda clear; agenda=buildData('Agenda.xls'); agenda=mySortCognome(agenda); % Fine Script

15

mySortCognome

function v = mySortCognome(v) %Sort the array v along the row specified in the input. %INPUT: a struct vector containing strings %OUTPUT: a vector v of number sorted in descending order for i=1:length(v)-1 scambio=false; for j=2:length(v)-i+1 if gtStr(v(j-1).cognome,v(j).cognome) x=v(j); v(j)=v(j-1); v(j-1)=x; scambio=true; end end if ~scambio break; end end end 16

Esercizi

  Dato un sudoku completato, verificare che la soluzione sia corretta

  matrice 9x9 divisa in sottomatrici 3x3   ogni sottomatrice deve contenere elementi da 1 a 9

senza ripetizioni   ogni riga deve contenere numeri da 1 a 9 senza

ripetizioni   ogni colonna deve contenere i numeri da 1 a 9 senza

ripetizioni

17

Analisi del problema

  Input:

 matrice 9x9   regole Sudoku

  Output True or False   Operazioni (fold di fold)

 analisi righe: fold  analisi colonne: fold  analisi sottomatrici: fold

18

Sudoku.m

%Sudoku clc; clear; sudoku = ...; % MATRICE OMESSA PER MANCANZA DI SPAZIO. VEDI CODICE % if ~isempty(find(sudoku>9)) || ~isempty(find(sudoku<1)) %controllo se gli elementi del sudoku sono complresi da 1 a 9 fprintf(' Sudoku errato. \n Il sudoku contiene valori >9 o < 1'); elseif controlloRighe(sudoku) && ... controlloColonne(sudoku) && ... controlloSottomatrici(sudoku) fprintf(' Sudoku corretto '); else fprintf(' Sudoku errato. Ci sono duplicati non ammessi (righe, colonne sottomatrici)'); end

19

controlloRighe.m

function r = controlloRighe( s ) %Data una matrice s controlla che nelle righe %non ci siano elementi ripetuti. %INPUT: matrice s %OUTPUT: r=true se non ci sono ripetizioni. Altrimenti r=false r=true; for i=1:size(s,1) % scorro righe for j=1:size(s,2) % scorro colonne if length(find(s(i,:)==s(i,j)))>1 r=false; break; end end if r==false break; end end

20

controlloColonne.m

function r = controlloColonne( s ) %Data una matrice s controlla che nelle colonne %non ci siano elementi ripetuti. %INPUT: matrice s %OUTPUT: r=true se non ci sono ripetizioni. Altrimenti r=false r=true; for i=1:size(s,2) %scorro colonne for j=2:size(s,1) %scorro righe if length(find(s(:,i)==s(j,i)))>1 r=false; break; end end if r==false break; end end

21

controlloSottomatrici.m

function r = controlloSottomatrici(s) %Data una matrice s di dimensione 9x9 controlla che nelle sottomatrici %di dimensione 3x3 (mod 3) non ci siano elementi ripetuti. %INPUT: matrice s %OUTPUT: r=true se non ci sono ripetizioni. Altrimenti r=false r=true; if size(s,1)~=9 && size(s,2)~=9 r=false; else for i=1:3:size(s,1) for j=1:3:size(s,2) if ~controlloMatrice(s(i:i+2,j:j+2)) r = false; break; end if r == false break; end end end end 22

controlloMatrice.m

function r = controlloMatrice(m) r=true; for i=1:size(m,1) for j=1:size(m,2) if length(find(m==m(i,j)))>1 r=false; break; end if r == false break; end end end

23