Algoritmo con complessità O(logn)
In un esercizio è richiesto di scrivere un algoritmo in pseudo-codice che abbia come limite superiore logn.
Trovare una soluzione con costo O(n) è facile, ma O(logn) non mi viene in mente nulla (sarà l'ora!).
Potete aiutarmi a capire come risolverlo? Di seguito il testo:
Siano date n monete d'oro, tutte dello stesso peso tranne una contraffatta che pesa meno, ed una bilancia con due piatti. Disegnare un algoritmo per individuare la moneta contraffatta in al più logn pesate.
Leggendo la consegna immagino che le monete siano gli indici 1..n di un array A[1..n], dove l'indice i dell'array corrisponde al peso A. Pensavo di simulare il problema con un ciclo for da 1 a n/2, dove confronto i valori A e A[n-i] degli array (con i != n-i), e se uno è minore dell'altro la moneta i o n-i è la più leggera, ma strutturato in questo modo l'algoritmo è O(n).
Vi ringrazio anticipatamente dell'aiuto
Trovare una soluzione con costo O(n) è facile, ma O(logn) non mi viene in mente nulla (sarà l'ora!).
Potete aiutarmi a capire come risolverlo? Di seguito il testo:
Siano date n monete d'oro, tutte dello stesso peso tranne una contraffatta che pesa meno, ed una bilancia con due piatti. Disegnare un algoritmo per individuare la moneta contraffatta in al più logn pesate.
Leggendo la consegna immagino che le monete siano gli indici 1..n di un array A[1..n], dove l'indice i dell'array corrisponde al peso A. Pensavo di simulare il problema con un ciclo for da 1 a n/2, dove confronto i valori A e A[n-i] degli array (con i != n-i), e se uno è minore dell'altro la moneta i o n-i è la più leggera, ma strutturato in questo modo l'algoritmo è O(n).
Vi ringrazio anticipatamente dell'aiuto
Risposte
Credo che con il termine "pesate" indichi "confronti". Devi scrivere un algoritmo che faccia O(log n) confronti, dove un confronto è
Quindi il trucco è calcolare il peso di sottoinsiemi di monete e confrontarli tra loro. Ti conviene prima trovare un procedimento a parole, e solo dopo trasformarlo in algoritmo. E magari all'inizio limitati al caso n pari, per poi generalizzare in seguito.
if (qualcosa < qualcos'altro) {
...
} else {
...
}Quindi il trucco è calcolare il peso di sottoinsiemi di monete e confrontarli tra loro. Ti conviene prima trovare un procedimento a parole, e solo dopo trasformarlo in algoritmo. E magari all'inizio limitati al caso n pari, per poi generalizzare in seguito.
Si tratta di un classico esempio di divide-et-impera.
Se tu hai che le monete sono tutte uguali tranne una allora se tu dividi un due gruppetti allora sai che uno dei due gruppetti deve pesare meno dell'altro. A questo punto hai il problema che n potrebbe non essere divisibile per due.
Con un giochetto puoi comunque fare in modo di dividere \(\displaystyle n \) in 3 blocchetti (di cui uno più piccolo degli altri due) e confrontarli in una sola pesata. Il calcolo della complessità è una applicazione del master method (penso si chiami metodo dell'esperto in italiano) e la pesata, indipendentemente da quante monete ci metti sopra, dovrebbe essere di complessità costante (una implementazione sul computer usando array avrebbe invece una complessità lineare e a quel punto però potresti usare un semplice algoritmo di ricerca).
Se tu hai che le monete sono tutte uguali tranne una allora se tu dividi un due gruppetti allora sai che uno dei due gruppetti deve pesare meno dell'altro. A questo punto hai il problema che n potrebbe non essere divisibile per due.
Con un giochetto puoi comunque fare in modo di dividere \(\displaystyle n \) in 3 blocchetti (di cui uno più piccolo degli altri due) e confrontarli in una sola pesata. Il calcolo della complessità è una applicazione del master method (penso si chiami metodo dell'esperto in italiano) e la pesata, indipendentemente da quante monete ci metti sopra, dovrebbe essere di complessità costante (una implementazione sul computer usando array avrebbe invece una complessità lineare e a quel punto però potresti usare un semplice algoritmo di ricerca).
Innanzitutto vi ringrazio delle risposte.
Poi volevo chiedere: Come strutturo la visita? Perché non penso che le monete siano ordinate in uno specifico modo, quindi come posso applicare il divide-et-impera? Se la moneta più leggera sarà l'ultima che visito, la complessità salirebbe comunque a n o no?
Poi volevo chiedere: Come strutturo la visita? Perché non penso che le monete siano ordinate in uno specifico modo, quindi come posso applicare il divide-et-impera? Se la moneta più leggera sarà l'ultima che visito, la complessità salirebbe comunque a n o no?
Le monete sono memorizzate in un vettore v di interi, v[ i] è il peso della moneta i.
Pesi la prima metà del vettore e la seconda metà:
Queste contano come due pesate, anche se per forza di cose saranno implementate con due cicli da n/2 iterazioni.
Pesi la prima metà del vettore e la seconda metà:
pesoPrimaMetà = sum (i = 1 : n/2) v[i] pesoSecondaMetà = sum (i = n/2+1 : n) v[i]
Queste contano come due pesate, anche se per forza di cose saranno implementate con due cicli da n/2 iterazioni.
"claudio86":
Le monete sono memorizzate in un vettore v di interi, v[ i] è il peso della moneta i.
Pesi la prima metà del vettore e la seconda metà:
pesoPrimaMetà = sum (i = 1 : n/2) v[i] pesoSecondaMetà = sum (i = n/2+1 : n) v[i]
Queste contano come due pesate, anche se per forza di cose saranno implementate con due cicli da n/2 iterazioni.
Direi proprio di no. Se tu avessi ogni v ti basterebbe cercare il minimo, ma l'unica cosa che tu hai sono due piatti. Formalmente hai una funzione, di complessità costante, che compara due sottoinsiemi. Penso che si possa supporre che la suddivisione in sottoinsiemi sia costante.
Io lo scriverei così:
FakeCoin :: A is Set -> c is Set
begin FakeCoin
if(card A == 1)
then
return A;
else
(A,B,C) is (Set, Set, Set);
(A,B,C) = subdivide A;
D is Set;
D = min A, B;
if D == EmptySet
then
return FakeCoin C;
else
return FakeCoin D;
endif
endif
end FakeCoin
"vict85":
Direi proprio di no. Se tu avessi ogni v[i ] ti basterebbe cercare il minimo, ma l'unica cosa che tu hai sono due piatti. Formalmente hai una funzione, di complessità costante, che compara due sottoinsiemi.
Beh, così sono capaci tutti
Dipende da quanto in dettaglio vuoi descrivere l'algoritmo. Il peso di un insieme di monete è la somma dei pesi delle singole monete. Nel mondo reale è un'operazione a costo costante ma su un computer no (per questo avevo sottolineato che ai fini dell'algoritmo i due cicli contavano come due operazioni, e come fatto notare anche da vict85).
Puoi anche vederla in un altro modo: tu non conosci i valori di v[ i], ma l'entità (funzione / classe / bilancia) che calcola il peso di insiemi di monete sì.
Comunque probabilmente il livello di dettaglio della tua soluzione è quello richiesto (però avrei evitato di dare la soluzione direttamente).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo