• Non ci sono risultati.

Algoritmi e Strutture Dati

N/A
N/A
Protected

Academic year: 2021

Condividi "Algoritmi e Strutture Dati"

Copied!
5
0
0

Testo completo

(1)

Corso di Laurea Codice insegnamento Email docente Anno accademico

Laboratorio di

Algoritmi e Strutture Dati

Esercitazione su Ricorsione e Code di Piorità

Prof. Aniello Murano

Informatica 13917 murano@na.infn.it 2007/2008

Lezione numero: 4

Parole chiave: Ricorsione, Code a priorita

Facoltàdi Scienze Matematiche Fisiche Naturali 2

16/10/2008

Torri di Hanoi

Quello delle Torri di Hanoi è un gioco che si svolge con tre paletti e alcuni dischi di diametro differente con un foro al centro in modo da poter essere infilati nei paletti.

Inizialmente i dischi sono tutti impilati a piramide sul primo paletto. Il disco più grande è in basso, il più piccolo in alto.

(2)

16/10/2008

2

Facoltàdi Scienze Matematiche Fisiche Naturali 16/10/2008 3

Torri di Hanoi

Scopo del gioco:

Lo scopo del gioco è quello di trasferire i dischi dal paletto di sinistra a quello di destra, senza mai mettere un disco su un altro di dimensione più piccola.

Regole del gioco:

È possibile spostare un solo disco alla volta; tutti i dischi devono essere sempre infilati nei paletti.

Strategia:

La strategia consiste nel considerare uno dei paletti come origine e un altro come destinazione. Il terzo paletto sarà utilizzato come deposito temporaneo.

Facoltàdi Scienze Matematiche Fisiche Naturali 4

16/10/2008

Strategia

Supponiamo di avere n dischi, numerati dal più piccolo al più grande. Inizialmente sono tutti impilati nel paletto di sinistra.

Il problema di spostare n dischi sul paletto di destra può essere descritto in modo ricorsivo così:

Spostare i primi n-1 dischi dal paletto di sinistra a quello di centro.

Spostare il disco n-esimo (il più grande) sul paletto di destra.

Spostare i rimanenti n-1 dischi dal paletto di centro a quello di destra.

In questo modo il problema può essere risolto per qualsiasi valore di n>0 (n=0 è la condizione di stop della ricorsione).

(3)

Programma

Vogliamo un programma che ci dia la strategia da seguire dato il numero di dischi

il primo paletto (quello di sinistra) con Sorgente il secondo paletto (quello di centro) con Aux il terzo paletto (quello di destra) con Destinazione

Definiamo la procedura ricorsiva transfer, che trasferisce n dischi da un paletto all altro.

Facoltàdi Scienze Matematiche Fisiche Naturali 6

16/10/2008

Esercitazione su Heap (1)

Si consideri una coda di priorità per la gestione della coda di stampa di una rete implementata con una struttura dati heap H[MAX].

Si implementino le seguenti funzioni:

void Heapify(int H[MAX], int el); \\ el è un indice di H void BuildHeap(int H[MAX]);

void HeapSort(int H[MAX]);

int ricerca (int H[MAX], int el); \\ restituisce l indice del vettore in cui si trova l elemento el; e -1 se l elemento non è presente nel vettore

(4)

16/10/2008

4

Facoltàdi Scienze Matematiche Fisiche Naturali 16/10/2008 7

Esercitazione su Heap (2)

Si consideri una coda di priorità per la gestione della coda di stampa di una rete realizzata con una struttura dati heap H[MAX].

Sia heapsize la variabile che memorizza la dimensione dell heap Si implementi la funzioni

void annulla_lavoro(int H[MAX], int el),

che presi in input l heap e un lavoro el (intero) da eliminare provveda ad eliminare el dall heap.

Descrivere la complessità della funzione implementata.

L esercizio, completo di una breve documentazione (1 pagina), va consegnato via

mail al tutor entro 3 giorni lavorativi

(5)

Riferimenti

Documenti correlati

Si scriva una procedura Pascal, basata sulla ricerca binaria, per individuare in tempo O(log n) l’unico intero dell’intervallo 1..n+1 che non compare in V.... Si scriva

Esistono due classi di memoria: automatica e statica La classe di memoria automatica è relativa a quegli oggetti locali ad un blocco (funzione o programma) che viene liberata

E responsabilità del programmatore controllare che il numero ed il tipo degli argomenti passati ad una funzione corrisponda con quanto specificato nella dichiarazione della

L Insertion Sort è uno algoritmo di ordinamento molto efficiente per ordinare un piccolo numero di elementi. L idea di ordinamento è quella che potrebbe usare un persona

L’array A[p…r] viene “suddiviso” in due sotto- array “non vuoti” A[p… q] e A[q+1…r] in cui ogni elemento di A[p…q] è minore o uguale ad ogni elemento

Si noti che l ordine in cui i piatti sono tolti dallo stack è inversa all ordine in cui essi sono stati inseriti nello stack, visto che solo il top dello stack è accessibile..

Nella situazione iniziale, tutti gli elementi sono posti nello Stack H dove l elemento al Top è la testa (Head) della coda, mentre quello al Bottom rappresenta la fine

Scrivere in linguaggio C una funzione ricorsiva che preso in input L e un intero el, verifichi se esiste una occorrenza di el nella lista. Idea per la soluzione