Newsgroup: it.hobby.enigmi
Titolo: Antico cerimoniale

 :) dario
Questa è una routine ricorsiva in VB che simula tutti i movimenti delle
persone. La riporto per chi fosse interessato.
'  n indica la persona, bIn vale True se la persona entra e False se esce,
il vettore "presente" indica lo stato di ogni persona nella stanza
Public Sub Sposta(n As Integer, bIn As Boolean, presente() As Boolean)
    ' se la persona è già dove deve essere, non fare niente
    If presente(n) = bIn Then Exit Sub
    ' solo se non è il numero 1 fa uscire il diretto superiore
    If n <> 1 Then Sposta n - 1, False, presente
    Dim i As Integer
    ' fa entrare tutti gli altri superiori
    For i = n - 2 To 1 Step -1
        Sposta i, True, presente
    Next
    ' notifica la presenza nella stanza
    presente(n) = bIn
    ' stampa e conta le mosse
    If bIn Then
        Debug.Print "Entra"; n
    Else
        Debug.Print "Esce"; n
    End If
    conta = conta + 1
End Sub
Una volta dichiarato un vettore di N Boolean, va chiamata in questo modo:
For i = N To 1 Step -1
    Sposta i, True, presente
Next
Come dice GaS, il problema ha una notevole somiglianza con la Torre di
Hanoi, la cui soluzione ricorsiva, però, non necessita del vettore. Mi
sembra che in questo caso del vettore non se ne possa fare a meno. Voi che
cosa ne pensate?
Ciao
Giorgio

 dirigenti.
Scusatemi ma ho sbagliato la formula finale.
La generalizzazione giusta è quella proposta da silvio Sergio poco sotto.
Walker

 Voi che cosa ne pensate?
Credo si possa fare tutto in puro stile Hanoi.
Ecco le routine necessarie (vi ricordo che chiunque abbia Excel o altri
programmi Office può incollare il codice con l'editor di VB).
Se volessimo solo contare le mosse, basterebbe la sola "aggiungi" che come
numero di operazioni è equivalenti alla "togli" (le esegue in ordine
inverso).
Sub aggiungi(n As Integer)
  ' fa entrare i primi n impiegati
  If n < 1 Then Exit Sub 'non c'è niente da aggiungere
  aggiungi n - 2    'I..IIOO
  Debug.Print n;    'I..IIOI
  togli n - 2       'O..OOOI
  aggiungi n - 1    'I..IIII
End Sub
Sub togli(n As Integer)
  ' fa uscire gli impiegati da 1 a n
  If n < 1 Then Exit Sub
  togli n - 1       'O..OOOI
  aggiungi n - 2    'I..IIOI
  Debug.Print n;    'I..IIOO
  togli n - 2       'O..OOOO
End Sub
Ecco l'output della chiamata "aggiungi 5"
1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Ciao, Silv:o)

 poco sotto.
Che in forma chiusa si puň scrivere come
N_i = int(2^(i+1)/3)
Silv:o)

 Ciao, Silv:o)
Mi pare che Dario conosceva un semplice metodo non ricorsivo per la torre di
Hanoi, era un triangolo che forniva la giusta sequenza di dischi da
spostare.
Proviamo a fare qualcosa di analogo per questo problema sorprendentemente
simile.
5
dopo il 5 mettiamo un 4
5 4
alterniamo i numeri inseriti con dei 3 in modo da terminare con un 3
3 5 3 4 3
alterniamo i numeri inseriti con dei 2
3 2 5 2 3 2 4 2 3 2
alterniamo i numeri inseriti con degli 1
1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
La regola č semplice. I nuovi numeri vanno aggiunti in modo da terminare la
sequenza con il numero appena inserito.
La sequenza per n=6 sarebbe:
-           6
-           6               5
-   4       6       4       5       4
-   4   3   6   3   4   3   5   3   4   3
- 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2
- 214121312161213121412131215121312141213121
Incidentalmente il numero di elementi aggiunti di volta in volta ricalca la
progressione dei movimenti necessari al variare di n.
Silv:o)


Riconosco che si può fare! :-)
Devo però dire che in questi tipi di problemi mi affascina il fatto di
scrivere soluzioni in cui le informazioni che io do al programma sono le
minime indispensabili. Nel mio caso non ho fatto altro che tradurre in
codice ricorsivo le regole indicate da Dario, con la sola aggiunta del
criterio di riempimento e svuotamento della stanza partendo sempre dal
fondo.
Nel caso specifico il mio programma è ignaro (e a dire il vero lo ero
anch'io - non avevo analizzato a fondo il problema! :-) ) del fatto che la
stanza si svuota una volta inserita l'ultima persona, prima che cominci la
manovra per inserire la penultima, ecc.
Mi riferisco alla tua riga:
    togli n - 2       'O..OOOI
che si basa su un'informazione non direttamente ottenibile dagli elementi
forniti.
Nonostante non disponga di questo tipo di informazione, il mio programma
trova comunque la soluzione corretta. Era per questo tipo di approccio che
intendevo non fosse possibile fare a meno del vettore.
Ciao :-)
Giorgio

 progressione dei movimenti necessari al variare di n.
Veramente un ottimo lavoro !
ciao :) dario