Il compleanno: vinco sempre io!
9 invitati e il festeggiato: 10 persone. Compie 12 anni, quindi K = 12. Ricostruiamo il posto che lo farà rimanere per ultimo.
Algoritmi
Laboratorio degli algoritmi a ritroso
Scegli il risultato e ricostruisci la partenza: un mazzo di carte o un cerchio di Josephus. Ogni mossa si può osservare, fermare e annullare.
Leggi la spiegazione e i due problemiIl mazzo di carte
In avanti: prendi da sotto, metti sopra; prendi da sotto, metti sul tavolo. A ritroso: riprendi dal tavolo, metti sotto; prendi da sopra, metti sotto.
La coppia: due vincitori scelti
20 amici, 2 vincitori e K = 11. Troviamo i due posti da assegnare alla coppia prima di iniziare.
Il cerchio di Josephus
Riuniamo i vincenti. Il prossimo perdente entra come numero provvisorio con ?, si sposta contando all’indietro e viene confermato nel punto raggiunto. Il giro successivo riparte dall’ultimo perdente inserito. Solo alla fine si individua il posto 1 e si numerano i posti.
È attiva la preferenza di movimento ridotto. Se vuoi vedere il trasferimento, seleziona questa casella.
Mazzo in mano
CimaCarta in movimento
Pila sul tavolo
CimaUscite desiderate, dalla prima all’ultima
Uscite osservate, dalla prima all’ultima
Mazzo preparato, dalla cima al fondo
Confronta con simulazione e permutazione
Etichette delle posizioni contate dal fondo: simuliamo il gioco, poi assegniamo a ciascuna posizione il valore richiesto alla sua uscita.
| Posizione uscita (dal fondo) | Valore da assegnare |
|---|
Vincenti in cerchio, perdenti da inserire
Numero con ? → spostamento a ogni conteggio → conferma nello stesso punto → ripartenza dall’ultimo perdente inserito. I numeri senza ? restano fermi.
Cerchio in costruzione · persone confermate
▼ Riferimento iniziale: persona 1, ferma in alto
Si muove solo il numero provvisorio con ?. Il cerchio ruota soltanto alla fine.
Con molti numeri, scorri all’interno del cerchio per vederli tutti.
Gruppo dei perdenti · ancora da inserire
Come leggere il conteggio
Il numero con ? entra provvisoriamente e cambia intervallo a ogni conteggio: gli altri numeri restano fermi. Al conto K il ? scompare e il perdente viene confermato esattamente lì. La prossima partenza è l’ultimo perdente inserito. Per conservare anche le identità dell’array PHP, il primo punto provvisorio è predisposto in anticipo: con 15 vincenti e K = 9 parte prima del 9 e arriva prima dell’1. Dopo l’ultimo inserimento un conteggio separato, ancora dall’ultimo perdente, individua il posto 1; solo allora il cerchio completo viene ruotato e numerato. L’ordine finale coincide con il ciclo PHP.
Riga finale dei posti
Adesso i numeri sono i posti: verde = vincente, blu = perdente. Il posto 1 è il punto da cui iniziare a contare per eliminare; non è il numero identificativo della persona 1.
Verde: vincenteBlu: perdente
Mostra anche il cerchio
Ricostruzione del cerchio
I posti sono numerati in senso orario. Il conteggio per eliminare parte dal posto 1 e segue il verso scelto; dopo ogni eliminazione ricomincia dalla persona successiva.
Qui si conta 1
Fila letta nel verso del conteggio, dal prossimo 1
Posti da assegnare ai vincitori
Posti eliminati nell’ordine