Algoritmo

[Giova411]

Provare a scrivere un algoritmo che individua una moneta contraffatta in al più $log n$ pesate,
assumendo che siano date:
- $n$ monete d'oro, tutte dello stesso peso;
- una (contraffatta) che pesa meno delle altre;
- una bilancia con due piatti.

Da quanto tempo che non chiedevo... Sentivo la mancanza
Ecco, lo sapevo, ora dall'emozione son commosso

[_Tipper]

Mi sa tanto di ricerca dicotomica, vista poi la complessità... Supponi che $n$ sia dispari, allora $n+1$ è pari. Metti $\frac{n+1}{2}$ monete su un piatto della bilancia, $\frac{n+1}{2}$ monete sull'altro piatto. Quello che pesa di meno conterrà la moneta contraffatta. A questo punto si considera il gruppo di $\frac{n+1}{2}$ monete contenente quella contraffatta.
Se $\frac{n+1}{2}$ è ancora pari procedi allo stesso modo, se invece è dispari ne prendi una in mano, e dividi sui due piatti le altre. Se pesano ugualmente allora quella contraffatta è quella che hai in mano, altrimenti è nel gruppo che pesa di meno, e ripeti il tutto.
Ovviamente se $n+1$ è dispari parti tenendone una in mano e dividendo in due gruppi le altre.

Ad ogni passo dimezzi il numero delle monete in ballo, pertanto il numero di pesate non eccede $\log(n)$ (dove il logaritmo è stato supposto dal sottoscritto in base $2$).

[Giova411]

Ok TIPPERONE!
Forse ci sono!
GRAZIEEEE

[Giova411]

A pensarci bene non son sicuro di quello che avevo scritto in un PSEUDO(-PSEUDO )-codice...

// A è un array che contiene le monete, inizio è il primo indice di A, fine l'ultimo elemento in A


Trovamoneta(A,inizio,fine){

if (fine>=inizio) {
return nil
}

int m := $|__$(inizio+fine)/2$__|$

if ( peso(A,inizio,m-1) == peso(A,m+1,fine) ) {
return m
} else{
if ( peso(A,inizio,m-1) > peso(A,m+1,fine) ){
return Trovamoneta(A,m+1,fine)
} else {
return Trovamoneta(A,inizio,m-1)
}
}

}

[Cheguevilla]

Puoi semplificare ancora dividendo per 3:

Trovamoneta(inizio,fine)
{
   if (fine>=inizio) return inizio;
   int m1 = (inizio+fine)/3;
   int m2 = 2*m1;
   if ( peso(inizio, m1-1) == peso(m1, m2-1) ) 
   return Trovamoneta(m2, fine)
   else
      if ( peso(inizio, m1-1) > peso(m1, m2-1) )
      return Trovamoneta(m1, m2-1)
      else
         return Trovamoneta(m2, fine)
}

In questo modo, non si considera il caso limite "A", ma il codice è molto più semplice...

[Giova411]

OK!!! Tenchiù!