In una scuola ci sono n allievi appartenenti ad m classi distinte, numerate da 1 ad m. Un sensore piazzato all'ingresso fornisce due dati: la classe (cioè l'intero che la identifica) di un allievo che attraversa l'ingresso e se l'allievo sta uscendo o entrando dall'edificio.
Ora, tenuto conto che in questa scuola ognuno è libero di entrare e uscire quando gli pare e piace, occorre definire un algoritmo che, osservando i dati forniti dal sensore, sia capace in ogni momento di rispondere alla domanda: "Gli allievi attualmente all'interno della scuola appartengono tutti alla stessa classe?".
Esiste una soluzione banale che fa uso di m variabili (contenenti interi da 1 a n), uno per classe e risponde in tempo O(m), ma si può fare di molto meglio: 1. Esiste una soluzione carina che usa O(log m) variabili e risponde in tempo O(log m)
2. Esiste una soluzione ancora più carina che usa O(1) variabili e risponde in tempo O(1)
Identificazione di intrusi in una scuola ideale
-
- Messaggi: 1
- Iscritto il: 26 giu 2008, 10:13