--- Fondamenti di Informatica 674II 1 luglio 2015 - soluzioni --- Sia dato un vettore v che contiene elementi della forma { descrizione: , prezzo: , quantita: intero } Si scriva una funzione prange(v) che riceve in ingresso v e restituisce un vettore con il prezzo minimo e massimo tra gli elementi del vettore. SOLUZIONE: Il problema si risolve con una semplice scansione del vettore v function prange(v) { var i, l, h; /* minimo e massimo corrente */ /* caso in cui non esiste vettore */ if (v == null || v[0] == undefined) { return null; } l = h = v[0].prezzo; /* valore iniziale for (i = 1; i < v.length; i++) { if ( v[i].prezzo < l} { l = v[i].prezzo; /* aggiorna minimo */ } else if ( v[i].prezzo > h} { h = v[i].prezzo; /* aggiorna massimo */ } } return [l, h]; /* costruisce e ritorna un vettore con min e max */ } --------------------------------------------- Un albero binario con nodi nodi della forma { D: , Left, Right: } contiene Elementi con questa struttura { X: , Y: } ed e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha Left.D.X < D.X <= Right.D.X Scrivere una funzione ins(n, e) che riceve in ingresso un riferimento alla radice di un albero non vuoto e vi inserisce l'elemento e solo se l'albero non contiene alcun elemento con D.X == e.X SOLUZIONE: La funzione ins() puo` eseguire una ricerca sull'albero uscendo se si trova un elemento con la stessa chiave, ed effettua l'inserimento in caso contrario. function ins(n, e) { while (n.X != e.X) { if (e.X < n.D.X) { /* nel caso va a sinistra */ if (n.Left == null) { /* inserisce */ n.Left = { D: e, Left: null, Right: null}; } n = n.Left; } else { /* va a destra */ if (n.Right == null) { /* inserisce */ n.Right = { D: e, Left: null, Right: null}; } n = n.Right; } } } ------------------------------------------------------------- Un albero binario con nodi nodi della forma { D: , Left, Right: } contiene Elementi con questa struttura { X: , Y: } ed e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha Left.D.X < D.X <= Right.D.X Scrivere una funzione find_less(n, s) che riceve in ingresso un riferimento alla radice di un albero e restituisce il numero di elementi dell'albero per cui D.X < s SOLUZIONE: Dovendo contare gli elementi con la proprieta` richiesta, bisogna effettuare una scansione ordinata dell'albero terminando quando si incontra un sottoalbero con tutti elementi piu` grandi. Il modo piu` semplice e` chiamare in modo ricorsivo la funzione function find_less(n, s) { var ret = 0; if (n != null) { ret = find_less(n.Left, s); /* esplora sempre albero sinistro */ if (n.D.X < s) { /* conta anche nodo corrente e albero destro */ ret += 1 + find_less(n.Right, s); } } return ret; } ----------------------------------------------- Un albero binario con nodi nodi della forma { D: , Left, Right: } contiene Elementi con questa struttura { X: , Y: } ed e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha Left.D.X < D.X <= Right.D.X Scrivere una funzione get_closer(n, s) che riceve in ingresso un riferimento alla radice di un albero e restituisce, tra gli elementi con D.X < S, quello con il piu` grande D.X SOLUZIONE: Dovendo individuare l'elemento piu` grande tra quelli minori di S, bisogna effettuare una scansione ordinata dell'albero terminando quando si incontra un sottoalbero con tutti elementi >= S Il modo piu` semplice e` chiamare in modo ricorsivo la funzione function get_closer(n, s) { var tmp, ret; if (n == null) { return null; /* elemento non esistente */ } ret = get_closer(n.Left, s); /* esplora sempre albero sinistro */ if (n.D.X < s) { /* esplora anche nodo corrente e albero destro */ tmp = n.D.X; /* valore corrente */ if (ret == null || tmp > ret) { ret = tmp; /* nuovo candidato */ } tmp = get_closer(n.Right, s); if (tmp != null && (ret == null || tmp > ret)) { ret = tmp; /* nuovo candidato */ } } return ret; } ----------------------------------------------------------- Un albero binario contiene nodi nodi della forma { D: , Left, Right: } ed e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha Left.D < D <= Right.D Scrivere una funzione add2(n, x) che riceve in ingresso un riferimento alla radice di un albero non vuoto e vi inserisce DUE elementi, uno con valore x e uno con valore 2*x, rispettando l'ordinamento. SOLUZIONE: Il modo piu` semplice di risolvere il problema e` chiamare due volte la funzione di aggiunta di un elemento a un albero binario, sia detta add(n, x) function add2(n, x) { add(n, x); add(n, 2*x); } function add(n, x) { while (true) { if (x < n.D) { /* il nuovo elemento va a sinistra */ if (n.Left != null) { n = n.Left; } else { n.Left = { D: x, Left: null, Right: null} ; break; } } else { /* elemento va a destra */ if (n.Right != null) { n = n.Right; } else { n.Right = { D: x, Left: null, Right: null} ; break; } } } } -------------------------------------------------------- Sia data una lista circolare di elementi con la forma { D: , next: } Si scriva la funzione add1(e) che riceve un riferimento a un elemento della lista ed aggiunge, tra ogni coppia di elementi originali, un nuovo elemento il cui campo D e` la somma dei campi D degli elementi adiacenti. SOLUZIONE: Si identificano inizialmente i casi di lista vuota o con un solo elemento per cui non si puo` effettuare l'operazione (non esiste "coppia di elementi originali"), successivamente si scandisce la lista circolare con due riferimenti all'elemento corrente e al precedente, e terminando la scansione quando si raggiunge l'inizio della lista function add1(e) { var prev = e, cur; if (e == null || e.next == e) { /* lista vuota o 1 elemento */ return; } cur = e.next; do { /* inserisce nuovo elemento */ prev.next = { D: prev.D + cur.D, next: cur }; prev = cur; cur = cur.next; } while (cur != e); } ------------------------------------------------- Sia data una lista circolare di elementi con la forma { Nome: , next: } Si scriva la funzione twins(e) che riceve un riferimento a un elemento della lista e restituisce un vettore contenente tutti i nomi che sono presenti nella lista esattamente due volte. SOLUZIONE: In questo caso vogliamo verificare una proprieta` globale della lista quindi dobbiamo fare una prima passata in cui identifichiamo i nodi che appaiono due volte (usando una mappa m{} per tenere traccia degli elementi con nomi diversi), e una seconda passata in cui costruiamo il vettore v[] da restituire in uscita. function twins(e) { var cur = e, m = {} v = []; if (e == null) return v; do { m[e.Nome] = (m[e.Nome] == undefined) ? 1 : m[e.Nome] + 1; cur = cur.next; } while (cur != e); for (cur in m) { if (m[cur] == 2) { /* questo nome appare due volte */ v.push(cur); } } return v; } ---------------------------------------------------