Fondamenti di informatica per Biomedica - 18 maggio 2015

Esempi di domande aperte


-------------------------------------------------------------------
1. Un negozio memorizza informazioni sui suoi prodotti in un vettore,
   che contiene dati della forma seguente
      { nome: <stringa>, codice: <numero>, prezzo: <numero>,
             piano: <1,2,3>, ... } /* DATO */
   Il campo "piano" indica il piano (primo, secondo, terzo)
   del negozio dove l'articolo e` esposto.

   Scrivere le seguenti funzioni indicando prima l'algoritmo
   utilizzato e la complessita` delle operazioni. Si supponga
   che il parametro v sia sempre un vettore, anche se contiene 0 elementi.

   function ordina(v, f)
	ordina il vettore v mediante algoritmo merge sort.
        La funzione f(x, y) viene specificata dal chiamante,
        riceve in ingresso i riferimenti a due oggetti
        (elementi del vettore) e restituisce -1, 0 o 1 a seconda
        che x sia piu piccolo, uguale o maggiore di y secondo
        il criterio scelto per l'ordinamento

   function pn(a, b)
        questa funzione viene passata alla ordina() per ordinare
        gli elementi per prezzo crescente, a parita` di prezzo
        per nome crescente, e a parita` di nome per codice crescente

   function perpiano(v)
        versione ottimizzata della ordina() che mette in ordine
        il vettore per piano. La scelta della soluzione e` libera.
        Si puo` essere piu` efficienti del merge sort ?

   function p5(v)
        ritorna un vettore che contiene, per ogni fascia
        di prezzo ( i*10 <= i < (i+1)*10, con i intero >= 0)
        i primi 5 prodotti (se esistono) in ordine di nome.
        

		===== ESEMPIO DI SOLUZIONE ====

1' esercizio

La funzione ordina() implementa il classico algoritmo di merge sort,
che ha complessita` O(N log N). Per questo utilizziamo una funzione
ausiliaria ms(v, a, b, f) che ordina v tra gli indici a e b-1

    function ms(v, a, b1, f) {
        var m = b1 - a, a1, tmp= [], ia, ib;
	if (m <= 1) { return; }
        m = Math.floor(m/2);
        a1 = a + m + 1; /* end of first half */
        /* recursive calls */
        ms(v, a, a1, f);
        ms(v, a1, b1, f);
        /* merge in an aux vector */
        ia = a;
        ib = a1;
        while (ia < a1 || ib < b1) { /* leftover elements */
            if (ia < a1 && (ib >= b1 || f(v[ia], v[ib]) < 0) ) {
                /* prende da v[ia] */
                tmp.push(v[ia]);
                ia++;
	    } else {
		tmp.push(v[ib]);
		ib++;
	    }
	}
        /* now copy data back to v */
        for (ia = a; ia < b1; ia++) {
             v[ia] = tmp[ia - a];
        }
    }

    function ordina(v, f) {
        ms(v, 0, v.length, f);
    }

La funzione pn deve applicare in modo successivo il confronto
sui tre campi

    function pn(a, b) {
        if (a.prezzo < b.prezzo) {
            return -1;
        } else if (a.prezzo > b.prezzo) {
            return 1;
        } else if (a.nome < b.nome) { /* prezzo uguale */
            return -1;
        } else if (a.nome > b.nome) { /* prezzo uguale */
            return 1;
        } else if (a.codice < b.codice) { /* prezzo e nome uguale */
            return -1;
        } else if (a.codice > b.codice) { /* prezzo e nome uguale */
            return 1;
	} else {
	    return 0;
        }
    }

La funzione perpiano() puo` essere ottimizzata perche' ci sono solo
tre valori distinti, quinid si puo` partizionare il vettore in tre
blocchi e poi concatenarli, con una complessita` totale O(N)

    function perpiano(v) {
        var i, j, p1 = [], p2 = [], p3 = [];
	/* prima fase, split */
        for (i = 0; i < v.length; i++) {
            if (v[i].piano == 1) {
		p1.push(v[i]);
            } else if (v[i].piano == 2) {
		p2.push(v[i]);
	    } else {
		p3.push(v[i]);
	    }
        }
	/* seconda fase, merge */
        i = 0; /* indice in v */
        for (j=0; j < p1.length; j++) {
	    v[i++] = p1[j];
        }
        for (j=0; j < p2.length; j++) {
	    v[i++] = p2[j];
        }
        for (j=0; j < p3.length; j++) {
	    v[i++] = p3[j];
        }
    }

Il procedimento si puo` generalizzare per tutti i casi in cui abbiamo
un numero finito di classi.


La funzione p5() si implementa facilmente chiamando la funzione
ordina sfruttando una variante della funzione di ordinamento, che
considera la classe di prezzo invece che il prezzo esatto,
e successivamente facendo una scansione del vettore dei risultati
per determinare quali elementi da estrarre.

   funzione classediprezzo(x, y) {
        var cx = Math.floor(x.prezzo/10);
	var cy = Math.floor(y.prezzo/10);
	if (cx < cy) {
            return -1;
        } else if (cx > cy) {
            return 1;
        } else if (a.nome < b.nome) { /* prezzo uguale */
            return -1;
        } else if (a.nome > b.nome) { /* prezzo uguale */
            return 1;
	} else {
	    return 0;
	}
   }
   function p5(v) {
        var ris = [], prezzo, i, n;
        ordina(v, pn); /* funzioni definite in precedenza */
        prezzo = 0; /* fascia corrente */
        n = 0; /* elementi estratti nella fascia */
        for (i=0; i < v.length; i++) {
	    if (v[i].prezzo >= prezzo + 10) { /* inizio nuova fascia */
		prezzo = 10 * Math.floor(v[i].prezzo);
		n = 0;
	    }
	    if (n < 5) { /* preleva elemento corrente */
		ris.push(v[i]);
		n++;
	    }
	}
        return ris;
    }



        di prezzo ( i*10 <= i < (i+1)*10, con i intero >= 0)
        i primi 5 prodotti (se esistono) in ordine di nome.