Diapositiva 1

1.
2.
3.
4.
5.
6.
7.
8.
Esercizi su code
Date due code in ingresso a valori interi in ordine crescente, scrivere una
funzione che restituisca una terza coda che contenga i valori delle due
code disposti in ordine crescente.
Scrivere una funzione che inverta l’ordine dei valori di una pila. La
funzione deve modificare la pila in ingresso e non crearne una nuova.
Scrivere una funzione che inverta l’ordine dei valori di una coda. La
funzione deve modificare la coda in ingresso e non crearne una nuova.
Scrivere una funzione ricorsiva che inverte l’ordine degli elementi di una
coda.
Dati n elementi e dato un intero k, il problema di Josephus consiste
nell’eliminare a ogni passo il k-esimo elemento (partendo ogni volta
dall’ultimo elemento eliminato). Scrivere una funzione che, presi in
ingresso n, k, e l’array di elementi, restituisca l’unico elemento che rimane
nella coda in ingresso al termine del processo. Utilizzare una coda.
I numeri di Fibonacci sono definiti come segue: f(0) = 0, f(1) = 1, f(k) =
f(k-1)+f(k-2) quando k > 1. Scrivere una funzione che, dato un intero n,
stampi a video la serie di Fibonacci f(0), f(1), …, f(n). Utilizzare una coda.
Scrivere la funzione pop per estrarre l’elemento in cima a una pila.
Implementare la pila facendo uso di una coda.
Scrivere la funzione delete per estrarre l’elemento in testa alla coda.
Implementare la coda facendo uso di due pile.
NOTA: scrivere sempre pre e post condizione di ogni funzione
Definizione di coda
struct nodo_coda
{
tipo_elemento el;
struct nodo_coda *next;
};
struct coda
{
struct nodo_coda *head;
struct nodo_coda *tail;
int size;
};
dove tipo_elemento codifica il tipo di ogni elemento della pila.
Esercizio 1
Date due code in ingresso a valori interi in
ordine crescente, scrivere una funzione
che restituisca una terza coda che
contenga i valori delle due code disposti in
ordine crescente.
Pre condizioni:
La funzione prende in ingresso due code a valori
interi disposti in ordine crescente
Post condizioni:
La funzione restituisce una terza coda contenente
i valori delle due code disposti in ordine crescente
Svolgimento
coda *unisci_code(coda *c1, coda *c2)
{
/* coda “unione” */
struct coda *c = crea_coda();
while(!coda_vuota(c1) && !coda_vuota(c2))
{
if (front(c1) <= front(c2)) add(c, remove(c1));
else add(c, remove(c2));
}
while(!coda_vuota(c1)) add(c, remove(c1));
while(!coda_vuota(c2)) add(c, remove(c2));
}
return c;
Esercizio 2
Scrivere una funzione che inverta l’ordine
dei valori di una pila. La funzione deve
modificare la pila in ingresso e non
crearne una nuova.
Pre condizioni:
la funzione prende in ingresso una pila p
Post condizioni:
L’ordine dei valori contenuti nella pila in ingresso
viene invertito
Svolgimento
void inverti_pila(struct pila *p)
{
/* coda */
struct coda *c = crea_coda();
}
while(!pila_vuota(p))
{
tipo_elemento e = pop(p);
add(c, e);
}
while(!coda_vuota(c))
{
tipo_elemento e = remove(c);
push(p, e);
}
Esercizio 4
Scrivere una funzione ricorsiva che
inverte l’ordine degli elementi di una coda.
Pre condizioni:
la funzione prende in ingresso una coda c
Post condizioni:
L’ordine dei valori contenuti nella coda in ingresso
viene invertito
Svolgimento
void inverti_coda(struct coda *c)
{
tipo_elemento e;
/* caso base: coda vuota */
if (coda_vuota(c)) return;
/* elimina la testa della coda */
e = remove(c);
/* chiamata ricorsiva */
inverti_coda(c);
}
/* aggiunge l’elemento in coda */
add(c, e);
Esercizio 5
Dati n elementi e dato un intero k, il problema di
Josephus consiste nell’eliminare a ogni passo il k-esimo
elemento (partendo ogni volta dall’ultimo elemento
eliminato). Scrivere una funzione che, presi in ingresso
n, k, e l’array di elementi, restituisca l’unico elemento
che rimane “vivo” in ingresso al termine del processo.
Utilizzare una coda.
http://en.wikipedia.org/wiki/Josephus_problem
Pre condizioni:
la funzione prende in ingresso un intero n, un intero k e un array di
elementi (supponiamo che n > 0)
Post condizioni:
L’ultimo elemento che rimane “vivo” nella coda
Svolgimento
int Josephus(int *elementi, int n, int k)
{
struct coda *c = crea_coda();
tipo_elemento salvo = -1;
int i;
/* inserisce gli elementi nella coda */
for (i = 0; i < n; i++) add(c, elementi[i]);
while(!coda_vuota(c))
{
/* rimette in coda i primi k-1 */
for (i = 0; i < k-1; i++) add(c, remove(c));
/* elimina il k-esimo elemento */
salvo = remove(c);
}
/* restituisce l’ultimo elemento rimasto in coda */
return salvo;
}