mattoncini

[ronfo]

Ciao a tutti.
ho trovato un interessante quesito che vi propongo , ma siccome la soluzione non presenta particolare difficoltà
aggiungo un'appendice che lo rende più interessante.
consideriamo una pila di 15 mattoncini numerati come in figura e situati nella colonna 1;

mattoncini

mattoncini.jpg (34.99 KiB) Visto 9924 volte

procediamo come segue:
prendiamo il mattoncino 1 e lo posizioniamo nella colonna 2
prendiamo il mattoncino 2 e lo posizioniamo nella colonna 3
prendiamo il mattoncino 3 e lo posizioniamo nuovamente nella colonna 2
e cosi con i successivi mattoncini alternativamente sino ad esaurimento della colonna 1.
ripetiamo ora il procedimento in modo analogo con la terza colonna ponendo il primo mattoncino sulla colonna 2
poi quello successivo nella colonna 1 e così di seguito sino ad esaurimento della terza colonna.
ricominciamo smontando nuovamente la prima colonna e così di seguito fino ad avere tutti i mattoncini sulla colonna due.
Al termine del procedimento quale mattoncino si troverà in cima alla colonna?
Generalizzando il problema: se ci sono N mattoncini sulla prima colonna quale sarà il mattoncino in cima alla colonna al termine del procedimento?
volendo renderlo ancora più difficile se le colonne sono M ( chiaramente M<N) e ne scegliamo una a caso posso determinare matematicamente il mattoncino che risulterà in cima ?

[Info]

Mi ricorda molto la torre di Hanoi...... sono sulla strada giusta? pero`prima di spostare il terzo disco devo spostare il primo sopra il secondo.... altrimenti si ritroverebbe su un disco piu`piccolo, cosa che non e`permessa dal gioco.... ecco un programmino vb che avevo sviluppato tempo fa, che risolve questo caso, dato un numero qualsiasi di dischi. Quanti ricordi guardando un vecchio VB6


Public Function Move&(NumD&, StartC&, TempC&, DestC&)
Static NumMoves

t = t & StartC & " " & TempC & " " & DestC & " | "
If Not (NumD < 2) Then
Call Move(NumD - 1, StartC, DestC, TempC)
End If

t = t & StartC & " -> " & DestC & " | "
NumMoves = NumMoves + 1

If Not (NumD < 2) Then
Call Move(NumD - 1, TempC, StartC, DestC)
End If
Move = NumMoves

End Function

[ronfo]

Ciao Info
in effetti , ora che me lo fai notare , sembra la torre di Hanoi , ma non c'è il vincolo che il mattoncino con il numero maggiore stia sotto.
Mi chiedevo se ci fosse un modo semplice per determinare quale mattoncino finisse in cima alla pila alla fine del procedimento senza dover fare tutti i passaggi?!
Se , per esempio, i mattoncini fossero 987654321 quale alla fine si troverebbe sopra gli altri.
Riciao e Buona giornata

[Info]

ciao Ronfo, fammi capire..... quindi dopo il primo passaggio avrei tutti i dischi dispari sulla pila 2 e tutti quelli pari sopra la pila 3.... e corretto? Per poi portare sulla pila 2 il disco 14 e il disco 12 sulla pila 1... e`corretto il ragionamento?

[ronfo]

Ciao Info
Si è propri così...
dalla prima pila si dividono i mattoncini pari da quelli dispari poi prendo quelli dalla pila tre (pari) e li divido tra la pila due e la pila uno, poi ricomincio dalla pila uno ... e vado avanti finché tutti i mattoncini sono sulla pila due .
(per risolvere il problema , quando il numero è basso , si possono prendere dei foglietti di carta e numerarli da 1 a N )
Con 15 mattoncini il risultato finale è che il mattoncino in cima alla pila 2 sarà l' 8 (salvo cappelle )
nuovamente ciao e buona giornata
Ronfo

[Info]

Ecco la sequenza completa alla fine Ronfo
1, 3, 5, 7, 9, 11, 13, 15, 14, 10, 6, 2, 4, 12, 8

a me sembra partendo da 1 prima un +2 fino alla fine poi da piu`alto disponibile sempre un -4,
poi dal piu' basso un +8... (l'ultimo numero...)

quindi penso si possa prevedere sempre l'ultimo.... finita l'aggiunta degli 8 ci sarebbe da togliere sempre
16 dal piu' alto e cosi`via.

con la stessa regola ho previsto e verificato l'ultimo con 32 dischi.....

[Info]

ecco una macro excel per calcolare la sequenza... aggiungi il codice ad un foglio di calcolo qualsiasi (fai click in B1 e avvii il calcolo)

Codice: Seleziona tutto

Private Sub Worksheet_SelectionChange(ByVal Target As Range)
If (Target.Address <> "$B$1") Then Exit Sub

Dim numDischi As Integer
numDischi = InputBox("Inserisci numero dischi: ")

ReDim hasFilled(1 To numDischi) As Boolean
Dim step As Integer

For n = 1 To numDischi Step 1
    hasFilled(n) = False
Next n

step = 2
num = 1
hasFilled(num) = True

For n = 1 To numDischi Step 1
    Sheet1.Cells(n, 1) = num
    
    If ((num + step > numDischi) Or (num + step <= 0)) Then
        If (step > 0) Then
            k = numDischi
            While (k > 0)
                If (hasFilled(k) = True) Then
                    k = k - 1
                Else
                    GoTo esc
                End If
            Wend
        Else
            k = 1
            While (k <= numDischi)
                If (hasFilled(k) = True) Then
                    k = k + 1
                Else
                    GoTo esc
                End If
            Wend
        End If
esc:
        num = k
        step = step * -2
    Else
        num = num + step
    End If
    
    If (num <= numDischi And num > 0) Then
        hasFilled(num) = True
    End If
Next n
End Sub

[ronfo]

Grazie info per il programma
appena ho un minuto di tempo lo provo ...
Buona giornata

[gnugnu]

Ho ripreso questo problema per vedere se riuscivo a trovare un algoritmo, usabile anche a mano, che, a partire da N, fornisse f(N): l'etichetta del mattoncino che si troverà in cima alla pila.
Credo, a meno di errori, funzioni il seguente algoritmo a due stadi.
Si scrive il numero in base 4.
Primo stadio.
A partire dalla cifra finale, se questa è maggiore di 1, si procede, verso sinistra sostituendo ciascuna cifra maggiore di 1 con 0, fino ad arrivare alla prima cifra o ad una cifra minore di 2.
Se si arriva alla prima cifra, questa viene lasciata inalterata se è 1, in caso contrario sostituita con 2 (ovviamente la prima cifra non può essere 0).
Transizione.
Se durante il primo stadio si incontra (anche nell'ultima posizione) una cifra minore di 2, la si sostituisce con 2, e si passa al..
Secondo stadio.
Si procede, sempre verso sinistra, lasciando inalterate le cifre dispari ed aumentando di 1 quelle pari; giunti alla prima cifra, se questa è 1 viene cancellata, altrimenti viene sostituita con 1.
In questo modo si ottiene la scrittura, sempre in base 4, di f(N).
Più lungo a dirsi che a farsi, in questo modo f(987654321)=534674934.
Provando a disegnare il grafico di f(N) si scoprono delle interessanti proprietà di autosimilitudine: di seguito i grafici per N<100, N<500 ed N<2000

mattoncini3.jpg (12.83 KiB) Visto 9799 volte

mattoncini2.jpg (26.25 KiB) Visto 9799 volte

mattoncini1.jpg (25.33 KiB) Visto 9799 volte

Ciao