Homework 3

Esercizio 1:
Una rete wireless di N (=20) stazioni e' dispiegata in un terreno piano. Ogni stazione e' caratterizzata da un id univoco (da  0 ad N-1), da una posizione nel piano (x,y) e da un raggio trasmissivo R. Il raggio trasmissivo e' lo stesso per tutte le stazioni.

Due stazioni p e q sono in grado di comunicare tra loro se e solo se la loro distanza euclidea e' minore o uguale ad R. Se le stazioni p e q sono in grado di comunicare tra loro sono dette vicine.

Scrivere un programma che legga da tastiera le posizioni delle stazioni, il raggio di comunicazione R e l'id di una stazione e stampi i vicini di quella stazione in ordine di id crescente.

Note:

Il main del programma deve leggere da tastiera le posizioni delle stazioni, una riga per ogni stazione. La riga i-esima � relativa alla stazione con id i, e contiene le coordinate x ed y separate da uno spazio. 

Le informazioni di una stazione devono essere salvate in una struttura definite come segue:

typedef struct stazione{

	int id;
	double x,y;
}stazione;

Le strutture relative alle N stazioni devono essere salvate in un array.

Il raggio di comunicazione R e' intero.

Due staizoni p e q sono vicini se d(p,q) <= R.

L'output deve contenere gli id dei vicini della stazione richiesta stampati in ordine crescente, andando a capo dopo la stampa di ogni id.

Esempio:
3.67 9.33
6.86 6.75
6.67 7.28
7.24 7.89
0.23 1.23
8.91 7.32
6.67 3.59
9.20 0.51
1.93 5.14
3.21 7.57
0.13 5.64
4.82 9.71
4.81 6.94
6.04 9.00
3.26 5.04
0.29 8.04
9.80 8.34
5.00 9.98
3.00 9.38
0.56 4.57
4
18
La stazione con id 0 ha posizione 3.67, 9.33 mentre la stazione con id 15 ha posizione 0.29, 8.04. Il raggio trasmissivo � R=4, si richiedono i vicini della stazione con id 18.

L'output dovra' quindi essere:
0
9
11
12
13
15
17

Riassumendo quindi l'esecuzione corretta e':
3.67 9.33
6.86 6.75
6.67 7.28
7.24 7.89
0.23 1.23
8.91 7.32
6.67 3.59
9.20 0.51
1.93 5.14
3.21 7.57
0.13 5.64
4.82 9.71
4.81 6.94
6.04 9.00
3.26 5.04
0.29 8.04
9.80 8.34
5.00 9.98
3.00 9.38
0.56 4.57
4
18
0
9
11
12
13
15
17

Esercizio 2:
Si scriva un programma che prenda in input un albero binario di altezza al piu' 4 i cui nodi contengano chiavi intere, maggiori di zero, e stampi la visita in pre-ordine dell'albero.

Note:
L'altezza e' definita come numero di archi tra la radice e la foglia piu'� profonda, quindi l'albero ha al pi� 5 livelli, incluso quello della radice. 
L'albero deve essere rappresentato attraverso un array (i figli del nodo di indice i sono memorizzati in corrispondenza degli indici 2i e 2i+1). L'albero in input puo' non essere  completo. 
L'albero sara' passato al programma per livelli, con i valori dei nodi separati da spazi. I nodi non presenti sono rappresentati con uno 0.

Il programma deve stampare i valori ottenuti con la visita in pre-ordine andando a capo ad ogni valore.

La soluzione deve essere iterativa, soluzioni ricorsive saranno considerate errate.

Esempio:
Si consideri l'albero:
1
2 3
0 4 0 5
0 0 0 0 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

L'albero ha altezza minore o uguale a 4. Il nodo 1 ha come figlio sinistro 2 e come figlio destro 3, il nodo 5 non ha figlio sinistro ed ha solo il figlio destro 6, il nodo 4 non ha figli (foglia).

Il programma deve stampare la visita in pre-ordine:
1
2
4
3
5
6