[c++ / Torre di Hanoi] - Come si risolve iterativamente?

[unslee]

Ciao a tutti,
sono alle prese con la torre di Hanoi. Dati il numero degli anelli, la torre iniziale, la torre finale, la torre "di servizio" sono riusciuto a far girare il programma con una funzione ricorsiva in modo che dia tutte le istruzioni (es. da 1 a 3 vuole dire muovi un anello dalla torre 1 alla torre 3) per risolvere correttamente il problema.

Siccome ogni problema risolto adottando una funzione ricorsiva può anche essere risolto con una funzione iterativa, è un pò che cerco di capire come riscrivere la mia funzione void hanoi(int, int, int, int) senza far uso della ricorsione.

Ma niente, niente, niente! :muro:

Grazie anticipatamente dell'aiuto. Di seguito il programma con la funzione ricorsiva.


// Esercizio 642.cpp : definisce il punto di ingresso dell'applicazione console.
//

#include "stdafx.h"

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}

void hanoi(int, int, int, int);

int main()
{
int number;
int piniziale;
int pfinale;
int ptemp;

cout << "Inserisci il numero di anelli da spostare: ";
cin >> number;

cout << "\n\nInserisci il numero della torre iniziale: ";
cin >> piniziale;

cout << "\n\nInserisci il numero della torre finale: ";
cin >> pfinale;

cout << "\n\nInserisci il numero della torre temporanea: ";
cin >> ptemp;

hanoi(number, piniziale, pfinale, ptemp);

return 0;
}

void hanoi(int number, int piniziale, int pfinale, int ptemp)
{


if (number == 1)
{
cout << "da " << piniziale << " a " << pfinale << endl;
return;
}
else
{
int ttemp = pfinale;
int ttemp2 = piniziale;
int ttemp3 = ptemp;

int ttemp4 = piniziale;
int ttemp5 = pfinale;
int ttemp6 = ptemp;

hanoi(number - 1, ttemp2, ttemp3, ttemp);
cout << "da " << piniziale << " a " << pfinale << endl;
hanoi(number - 1, ttemp6, ttemp5, ttemp4);
return;
}
}

[stdecden]

Da wikipedia(en):

Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a call stack, although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack.

Mai fatto, a dire la veritá, ci devo provare un giorno o l'altro. comunque spero di esserti stato utile

[unslee]

Il realtà il passaggio creda voglia dire che per avere una funzione iterativa equivalente ad una ricorsiva va analizzato lo stack.

Però sono sempre in panne ... non riesco a definire per bene l'iterazione!

Grazie lo stesso per l'aiuto!

[unslee]

Ho trovato un interessante spiegazione in merito qui:

http://www.eleves.ens.fr/home/defeo/serio/english/papers/hanoi/iterative.htm

Mi è quasi tutto chiaro, ma non riesco a capire questo passaggio:


Ci basta sapere quante volte (e in che direzione) ha già mosso il disco in questione per sapere su quale piolo si trovi. Osserviamo che il disco più piccolo muove ogni due mosse (lo si può dimostrare guardando il contatore binario); poiché il disco immediatamente sotto di esso muove la metà delle volte, deve necessariamente muovere ogni quattro mosse. In generale un disco di dimensione d, muove ogni 2d mosse. Quindi, supponendo che i sia il numero d'ordine della mossa, la seguente formula ci dice quante volte ha mosso il disco:

#mosse = i / 2d

C'è bisogno di una piccola correzione a questa formula, perché il primo disco non muove dopo due mosse, ma dopo una; il secondo muove dopo 2, il terzo dopo 4 e così via (anche questo si può dimostrare attraverso il contatore binario). Per cui la formula va aggiustata così:

#mosse = (i + 2d-1) / 2d

che è equivalente a:

#mosse = (i / 2d) + (1 / 2)

A questo punto, sapendo che il disco ha mosso sempre verso (ad esempio) destra e che la torre partiva dal piolo p, possiamo calcolare così il piolo su cui si trova il disco:

piolo = ((#mosse mod 3) + p) mod 3


cosa vuole dire #mosse? Sono alle prime armi con il C++ e per ora il simbolo # l'ho usato solo con include.

Grazie per l'aiuto!

[unslee]

Niente ...

Ho fatto un'analisi credo abbastanza precisa della procedura iterativa di cui al link. A parte il simbolo di cui al post precedente che non conosco. Non mi trovo su un postulato che nel link viene fatto.

Tornando a monte, seguendo la procedura del link, ho provato ad analizzare la questione come segue:

a) Abbiamo bisogno di quattro variabili e cioè: numero di dischi, piolo iniziale, piolo finale, piolo d'appoggio.

b) Definiamo le mosse quante sono:



while (int counter = numeroDischi; counter >= 3; counter --)
{
int mosse = 6;
mosse = mosse * 2 + 1
}



nella variabile mosse vado a memorizzare quante mosse sono necessarie.

c) Do in pasto alla funzione calcoloDisco(Mosse), come specificato nel link, il numero di mosse e mi viene restituita man mano l'indicazione di quale anello muovere (1 per l'anello più piccolo, 2 per quello più grande, 3 per quello più grande ancora e così via.

A questo punto so esattamente quale anello devo muovere per ogni mossa ma dovrei capire (da quale piolo) a quale piolo muoverlo.

Ora leggo nel link:



A questo punto dimostriamo che se l'intera torre va spostata verso destra, i dischi con la stessa parità del disco più grande si muoveranno sempre verso destra, mentre gli altri si muoveranno sempre verso sinistra (nel caso la torre vada spostata verso sinistra, è il contrario).




Io qui non riesco a capire proprio. Simulando l'esercizio con tre anelli disposti sul primo piolo, con due pioli liberi alla destra e torre da ricostruire sull'ultimo piolo a destra, il mio anello più piccolo (1) e anche l'anello intermedio si muovono sia a destra sia a sinistra ... :eek:

Please ..................help!

[atragon]

# = "numero"?

[banryu79]

Se proprio non ne vieni fuori vuoi un po' di documentazione rpova a guardare in questo sito (http://www.kernelthread.com/hanoi/): trovi più di cento implementazioni (in diversi linguaggi) del problema della torre di Hanoi.

[Vincenzo1968]

Nel sito indicato da banryu79, la versione cpp utilizza uno stack esplicito per implementare l'algoritmo iterativamente. Proprio quello che stavi cercando ;)

[unslee]

Ciao a tutti!
In realtà il programma indicato da banryu79 è ancora troppo complesso per me. Ci sono molto cose che non ho studiato ancora :mbe:

Mi conservo il link. Magari andando avanti con lo studio più in là sarò capace di capirlo appieno.

Grazie mille a tutti per l'aiuto e la disponibilità!

[Vincenzo1968]

Ciao a tutti!
In realtà il programma indicato da banryu79 è ancora troppo complesso per me. Ci sono molto cose che non ho studiato ancora :mbe:

Mi conservo il link. Magari andando avanti con lo studio più in là sarò capace di capirlo appieno.

Grazie mille a tutti per l'aiuto e la disponibilità!

Ciao,

La tecnica utilizzata in quel file è quella che si utilizza proprio per trasformare una funzione da ricorsiva a iterativa.
Si utilizza, cioè, uno stack esplicito. Nelle versioni iterative, viene utilizzato lo stack(implicito) di sistema per memorizzare le variabili e il valore di ritorno tra una chiamata e l'altra della funzione.
Nel caso in esame, l'utilizzo di uno stack esplicito è l'unico modo per risolvere il problema. Nei casi in cui la chiamata ricorsiva è soltanto nell'ultima riga della funzione, è possibile utilizzare semplicemente un ciclo(while o for).

Trovi maggiori dettagli, con un esempio di conversione(funzione di attraversamento degli alberi binari), in questo libro:

http://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structures/dp/0201314525

Dello stesso autore, c'è anche la versione per C++(in italiano).

[gaxy]

A questa URL (http://www.geo.uni-bonn.de/members/hattendorf/html/misc/hanoi/iterative_solutions/welcome.html) trovi due versioni iterative e la prima mi sembra affrontabile... :)

(AUSGABE è l'output, credo significhi che puoi scegliere se stampare o meno a video...)