Matlab/Octave - Esercitazione 3 - Politecnico di...

Salvo Daniele Valente

Dipartimento di Elettronica e Informazione

Politecnico di Milano - DEI Dipartimento di Elettronica e Informazione

Facoltà di Ingegneria IndustrialeLaurea in Ingegneria Energetica, Meccanica e dei Trasporti

1

Matlab/Octave - Esercitazione 3

Informatica B - Esercitazione 11 del 17/12/2010

‣programmazione ricorsiva




Consigli utili

2

MATLAB/Octave - Esercitazione 4


‣ Studiare il materiale didattico di lezione e di esercitazione per essere consapevoli degli strumenti disponibili di Matlab/Octave e di come vanno usati.

‣ E’ fondamentale frequentare i laboratori (per tutta la loro durata) non solo in vista della prova d’esame, ma per acquisire la conoscenza che servirà nel futuro lavorativo.

‣ Consultare libri e/o appunti durante l’esame è permesso ma comporta una perdita di tempo, che può essere evitata preparandosi adeguatamente . Conoscere MOLTO bene la sintassi delle istruzioni del linguaggio Matlab/Octave evita di fare errori e fa risparmiare tempo.

‣ Esercitarsi direttamente sul computer agevola la comprensione delle soluzioni. Chi non possiede un PC può utilizzare le aule informatiche ed i PC del Politecnico.

‣ Maggiore è il numero di funzioni predefinite di Matlab/Octave che si conosce, più la quantità di codice da scrivere si riduce: Matlab/ Octave mettono a disposizione funzioni per ogni applicazione.

‣ Per risolvere gli esercizi bisogna avere chiara in mente la procedura da adottare. La scrittura del codice è una conseguenza. Procedere per tentativi senza la preliminare organizzazione della risoluzione non aiuta, anzi, peggiora le cose.

‣ Pensare ai passi della soluzione, scriverli (su carta/ al PC), e poi occuparsi del codice e della sua scrittura

‣ Gli esercizi che vengono spiegati ad esercitazione DEVONO essere rifatti in prima persona studiando la soluzione e cercando di rifarli non utilizzando le slides ma unicamente l’help di Matlab/Octave.

‣ Se qualcosa della soluzione contenuta nelle slides non vi sembra corretta consultate quelle presenti sul sito. Queste vengono periodicamente riviste e corrette.




Esercizio 1

3


Scrivere un programma che:dato un numero N calcola la somma dei primi N numeri pari positivi in maniera ricorsiva.

La somma dei primi N numeri pari è la: SN = 2*1 + 2*2 + 2*3 + … + 2*i + … + 2*(N-1) + 2*N.





Esercizio 1 - Soluzione

4

Analizzando la formula della somma dei primi N numeri pari:

Notiamo che:‣ se N =1, SN = 2, (CASO BASE)‣ se N >1, SN = 2*N + SN-1 (PASSO INDUTTIVO)

(somma dell’N-esimo numero pari + la sommatoria dei primi N-1 numeri pari.)

SN = 2*1 + 2*2 + 2*3 + … + 2*i + … + 2*(N-1) + 2*N

Il passo induttivo richiama il valore della somma effettuato al passo precedente e lo incrementa con il nuovo valore: 2*N.Il problemi con struttura di questo tipo sono facilmente risolvibili con una programmazione ricorsiva.

La programmazione ricorsiva prevede la creazione, o il semplice utilizzo, di funzioni che richiamano se stesse al loro interno.







5

La funzione che calcola la somma dei primi N numeri pari, dunque, sarà:

function somma = sommaPari(N) if (N==1) somma = 2;else somma = 2*N + sommaPari(N-1);end

‣CASO BASE

‣PASSO INDUTTIVO

N = input('inserire il valore N: '); if (N==1) S = 2;else S = 2*N + sommaPari(N-1);end disp(['La somma dei primi N numeri pari è: ', num2str(S)]);

Lo script principale, analogamente, sarà:







6

Esercizio 1 - Codice completo

function somma = sommaPari(N) if (N==1) somma = 2;else somma = 2*N + sommaPari(N-1);end

%% Script principale%

N = input('inserire il valore N: '); if (N==1) S = 2;else S = 2*N + sommaPari(N-1);end disp(['La somma dei primi N numeri pari è: ', num2str(S)]);






Esercizio 2

7

Si progetti la funzione ricorsiva che svolge il compito seguente:-siano dati due vettori V1 e V2, rispettivamente di dimensioni N1 e N2 (con 1 N2 N1);

-la funzione restituisce 1 se tutti gli elementi del vettore V2 si trovano nel vettore V1 nell’ordine inverso rispetto a quello in cui essi figurano in V2, ma non necessariamente in posizioni immediatamente consecutive;

-se questo non si verifica, la funzione restituisce valore 0.

Esempio:V1 = [a c d e b] V2 = [b e a] il programma restituisce 1;V1 = [a c d e b] V2 = [e f a] il programma restituisce 0;







8



V1 = [a c d e b] V2 = [b e a]

[a c d e b] [b e a]

[c d e b] [b e]

[d e b] [b e]

[e b] [b e]

[b] [b]

[] []

V1 = [a c d e b] V2 = [e f a]

[a c d e b] [e f a]

[c d e b] [e f]

[d e b] [e f]

[e b] [e f]

[b] [e f]

[] [e f]

Esempio esito positivo: Esempio esito negativo:





9



Caso base:‣ (con esito positivo): se il vettore V2 è vuoto, termina con esito positivo 1 (un vettore

vuoto, senza elementi, è senz’altro contenuto in qualsiasi altro vettore).

‣ (con esito negativo): se il vettore V1 è vuoto (e il vettore V2 non è anch’esso vuoto) termina con esito negativo 0 (un vettore non vuoto, che contiene almeno un elemento, non può essere contenuto in un vettore vuoto).

Passo induttivo:‣ se l’elemento iniziale di V1 è uguale a quello finale di V2 elimina l’elemento iniziale di V1

e quello finale di V2.

‣ se l’elemento iniziale di V1 è diverso da quello finale di V2 (ovvero altrimenti) elimina soltanto l’elemento iniziale di V1.

[] []

[] [e f]

[a c d e b] [b e a]

[c d e b] [e f]





10



Chiamata ricorsiva:‣ ricorri sui due vettori V1 e V2 accorciati in uno dei due modi indicati nel passo

induttivo.

Condizione di terminazione:‣ nel passo induttivo almeno uno dei due vettori V1 o V2 viene sempre accorciato (se

non tutti e due) e quindi dopo un numero finito di passi almeno uno dei due vettori deve essere vuoto; l’algoritmo termina sulla base (positiva o negativa) quando almeno uno dei due vettori è vuoto; la terminazione della ricorsione è dunque sempre garantita.





11



function r = contieneInverso(v1,v2) if (isempty(v2)) r = 1; else if (isempty(v1)) r = 0; else if (v1(1) == v2(end)) r = contieneInverso(v1(2:end),v2(1:end-1)); else r = contieneInverso(v1(2:end),v2(1:end)); end endend

‣ caso base positivo

‣ caso base negativo

‣ passo induttivo positivo‣ passo induttivo

negativo





12



V1 = input('inserire il valore vettore V1: ');V2 = input('inserire il valore vettore V2: '); r = contieneInverso(V1,V2); if (r) disp(['tutti gli elementi di V2 sono contenuti in ordine inverso in V2']);else disp(['gli elementi di V2 non sono contenuti in ordine inverso in V1']);end

Script principale:





13

Esercizio 2 - Codice completoMATLAB/Octave - Esercitazione 4



V1 = input('inserire il valore vettore V1: ');V2 = input('inserire il valore vettore V2: '); r = contieneInverso(V1,V2); if (r) disp(['tutti gli elementi di V2 sono contenuti in ordine inverso in V2']);else disp(['gli elementi di V2 non sono contenuti in ordine inverso in V1']);end

function r = contieneInverso(v1,v2) if (isempty(v2)) r = 1; else if (isempty(v1)) r = 0; else if (v1(1) == v2(end)) r = contieneInverso(v1(2:end),v2(1:end-1)); else r = contieneInverso(v1(2:end),v2(1:end)); end endend




Esercizio 3

14



Scrivere un programma che stampi a video tutte le possibili N! permutazioni degli elementi di un vettore di N interi.

>> permuta([1 2 3])>> 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1





15



Il problema proposto si presta in modo naturale ad una formulazione ricorsiva.

Il vettore è lungo N e inizialmente dobbiamo costruire le permutazioni di N elementi.Per generare tutte le possibili permutazioni di N elementi:1.si tiene fisso un elemento del vettore (vedremo che per la scrittura del codice sarà più

comodo mantenere l’ultimo) e si calcolano le permutazioni dei restanti N-1 elementi.

2.si scambia l’ultimo degli N elementi da permutare con il penultimo e si ripete il passo 1

1 2 3V1 = 3 1 2

3 2 1

P =

elemento fisso permutazioni dei restanti N-1 elementi

1 3 2V1 = 3 1 2

3 2 1

2 1 3

2 3 2

P =

1 2 3V =

vettore d’ingresso





16



3.Scambiare il l’ultimo degli N elementi elemento con il terzultimo e si ripete il passo 1

3 2 1V1 = 3 2 1

3 1 2

2 3 1

2 1 3

1 2 3

1 3 2

P =

Se il vettore considerato non contiene elementi numerici, il calcolo delle loro permutazioni può essere ricondotto al caso visto precedentemente considerando le permutazioni dei loro indici.

1 2 3V1 =

3 2 1

3 1 2

2 3 1

2 1 3

1 2 3

1 3 2

P = a b cV = c a b

c b a

b a c

b c a

a c b

a b c

V1(P) =





17



Definisco la funzione permuta che sarà chiamata ricorsivamente.

function P = permuta(V)

n = length(V); % ottengo la lunghezza del vettore in input

if n <= 1 % CASO BASE: se il vettore è vuoto o contiene un solo elemento, restituisco P = V; % in uscita il vettore stesso. return % ed esco dalla funzioneend q = permuta(1:n-1); % PASSO INDUTTIVO: chiamata ricorsiva della funzionem = size(q,1);P = zeros(n*m,n); % inizializzazione della matrice contenente le permutazioni% STEP 1

P(1:m,:) = [n * ones(m,1) q];% n * ones(m,1) il primo elemento delle prime m righe di P è l’ultimo% indice di V (ovvero n)% [n * ones(m,1) q] affianco all’ultimo indice le permutazioni dei restanti n-1 elementi (contenute in q)

a b cV =





18



Definisco la funzione permuta che sarà chiamata ricorsivamente.

% STEP 2-3

for i = n-1:-1:1 % procedo a ritroso tra gli indici di V t = q; t(t == i) = n; P((n-i)*m+1:(n-i+1)*m,:) = [i*ones(m,1) t];end

i = 2

3 2 1

3 1 2

2 3 1

2 1 3

0 0 0

0 0 0

P = 3 1

1 3

q =

2 1

1 1

t =

i = 1

3 2 1

3 1 2

2 3 1

2 1 3

1 3 2

1 2 3

P = 3 1

1 3

q =

t = 3 2

2 3





19



Sostituisco gli elementi di V all’interno di P in posizione degli indici corrispondenti.

P = V(P);

3 2 1

3 1 2

2 3 1

2 1 3

1 2 3

1 3 2

P = a b cV = c a b

c b a

b a c

b c a

a c b

a b c

V1(P) =





20




V = ['a' 'b' 'c' 'd' 'e']; P = permuta(V)

function P = permuta(V) n = length(V); if n <= 1 P = V; returnend q = permuta(1:n-1);m = size(q,1);P = zeros(n*m,n);P(1:m,:) = [n * ones(m,1) q]; for i = n-1:-1:1 t = q; t(t == i) = n; P((n-i)*m+1:(n-i+1)*m,:) = [i*ones(m,1) t]; end P = V(P);




Esercizio 4

21



Scrivere un programma che legga le prime N parole presenti in file di testo e controlli se le parole lette sono palindrome o meno.Lo script dovrà:-leggere una singola parola dal file,-controllare se è palindroma,-scrivere un file di testo che contenga solo le parole palindrome e le righe in cui queste si trovano nel file d’origine.





22



Per capire se una parola è palidroma si procede ricorsivamente come segue:

Caso base:‣ (con esito positivo): se il vettore che contiene la parola è vuoto o è formato da un solo

carattere, il controllo termina con esito positivo;‣ (con esito negativo): se la prima e l’ultima lettera del vettore sono diverse tra loro,

termina con esito negativo.

Passo induttivo:‣ controllo se le restanti lettere del vettore (esclusa la prima l’ultima) formano a loro volta

una parola palindroma.





23



Analizziamo la funzione che controlla se una parola è palindroma o meno:

function esito = palindroma_check(parola) if (isempty(parola) || length(parola)==1) esito = 1;elseif (parola(1)==parola(end)) esito = palindroma_check(parola(2:end-1));else esito = 0;end

‣ caso base con esito positivo

‣ caso base con esito negativo

‣ passo induttivo

isempty(V) restituisce 1 se V è un vettore vuoto, 0 altrimenti.





24



Analizziamo ora lo script principale.

Definisco il numero di parole da controllare (lo si può anche chiedere in input) e:‣ apro il file di origine in lettura‣ apro il file di destinazione in scrittura

N = 1000; fid_in = fopen('dizionario.txt', 'r');fid_out = fopen('solo_palindrome.txt', 'wt')

Successivamente dovrò leggere ciclicamente una parola dal file d’origine dizionario.txt, controllare se è palindroma o meno e scriverla nel file di destinazione solo_palindrome.txt in caso di esito positivo.





25



for ii = 1:N A = textscan(fid_in, '%s', 1); parola = char(A{1, 1}) esito = palindroma_check(parola); if (esito) fprintf(fid_out, '%s\t%i\n', parola, ii); endend

Successivamente dovrò leggere ciclicamente una parola dal file d’origine dizionario.txt, controllare se è palindroma o meno e scriverla nel file di destinazione solo_palindrome.txt in caso di esito positivo.

textscan(fid, ‘format’, N) legge i dati dal file fid applicando il convertitore di formato ‘format’ (%s, %c, %d, etc...) N volte.Nel nostro caso, volendo leggere una sola parola, quindi una sola stringa, N=1.





26



Chiudo i file aperti e (facoltativo) visualizzo il file di destinazione .

fclose(fid_in);fclose(fid_out); open solo_palindrome.txt





27




N = 1000; fid_in = fopen('dizionario.txt', 'r');fid_out = fopen('solo_palindrome.txt', 'wt'); for ii = 1:N A = textscan(fid_in, '%s', 1); parola = char(A{1, 1}); esito = palindroma_check(parola); if (esito) fprintf(fid_out, '%s\t%i\n', parola, ii); endendfclose(fid_in);fclose(fid_out); open solo_palindrome.txt

function esito = palindroma_check(parola) if (isempty(parola) || length(parola)==1) esito = 1;elseif (parola(1)==parola(end)) esito = palindroma_check(parola(2:end-1));else esito = 0;end




Esercizio 5

28

Problema della Torre di Hanoi.Si consideri una tavoletta con tre pioli ed un certo numero di dischetti di diametro diverso infilati sullo stesso piolo in ordine di diametro decrescente, col dischetto più piccolo posto in cima.

L’obiettivo del gioco è ricomporre la stessa configurazione di dischetti su di un piolo diverso, spostando un disco alla volta da un piolo all’altro, con la restrizione che un dischetto non può mai essere appoggiato su di un altro di diametro inferiore.







29

Supponiamo di voler spostare la pila di tre dischi dal piolo 1 al piolo 3. Per farlo, occorre seguire i passaggi mostrati in figura.

Per spostare i dischetti dal piolo 1 al piolo 3, si usa il piolo 2 come supporto intermedio.- la pila con i due dischetti più piccoli è

stata spostata dal piolo 1 al piolo 2 (passaggi 1-3);

- si è spostato il piolo più grande dal piolo 1 al piolo 3 (passaggio 4);

- la pila formata dai due dischetti più piccoli è stata nuovamente spostata dal piolo 2 al piolo 3 (passaggio 5-7).







30

Formalizzando i passaggi possiamo dire che per spostare una pila di k dischetti da un piolo origine ad uno destinazione, si usa un terzo piolo come supporto intermedio.

spostare k dischetti da origine a destinazione:

‣spostare k-1 elementi da origine a supporto;

‣spostare il disco più grande da origine a destinazione;

‣spostare k-1 elementi da supporto a destinazione

Chiamiamo l’insieme dei tre passaggi:

Lo spostamento di k-1 elementi non è immediato ma prevede dei sottopassaggi. Questo accade se k-1 > 1. Se , invece la pila di dischi da spostare è formata da un solo disco (k-1 == 1), lo spostamento è diretto e non prevede sottopassaggi.

hanoi(k, origine, destinazione, supporto)







31

L’elenco di spostamenti precedenti si espande in:

spostare k dischetti da origine a destinazione:










hanoi(k-1, origine,...supporto, destinazione)

hanoi(k-1, supporto,...destinazione, origine)

}

}Si noti che i passaggi intermedi aggiuntivi (in verde) possono essere ricondotti alle tre operazioni base invertendo: nel primo caso destinazione con supporto; nel secondo caso origine con supporto.La serie di passaggi può essere ulteriormente espansa finché i passaggi intermedi prevedono lo spostamento di un solo disco.







32

Seguendo questa logica, il tutto può essere riassunto nella forma:

hanoi(k, origine, destinazione, supporto)

‣hanoi(k-1, origine, supporto, destinazione)‣spostare il disco più grande da origine a destinazione;‣hanoi(k-1, supporto, destinazione, origine)

La risoluzione della torre di Hanoi sarebbe estremamente complessa se non si potesse utilizzare la ricorsione.Grazie alla possibilità di richiamare una funzione all’interno della funzione stessa, la soluzione diventa estremamente semplice.function [] = hanoi(k, origine, destinazione, supporto) if (k<=0) return;else if (k > 1) hanoi(k-1, origine, supporto, destinazione); end fprintf('sposta un disco dal piolo %d al piolo %d\n',... origine, destinazione); if (k > 1) hanoi(k-1, supporto, destinazione, origine); endend



Matlab/Octave - Esercitazione 3 - Politecnico di...

Documents

Transcript of Matlab/Octave - Esercitazione 3 - Politecnico di...