Torre di hanoi metodo iterativo

[ZfreS]

Ho risolto il problema della torre di hanoi in maniera ricorsiva molto tempo fà, ma è tornata la curiosità di come risolverla iterativamente. Il fatto è che non ho la più pallida idea di come creare un algoritmo che lo sappia fare, poichè non so quanti passaggi deve fare. Potreste darmi una mano per favore?

[vict85]

Il numero minimo/corretto di mosse è \(2^n-1\). Lo si dimostra ricorsivamente.

[ZfreS]

Si, questa formula la conoscevo già, ma io volevo sapere come implementare un algoritmo in c++ che risolva iterativamente la torre di hanoi dato un numero n di dischi e specificao il piolo di partenza, appoggio e arrivo.

[vict85]

Se non ricordo male la mossa \(1\le s\le 2^n -1\) dipende solamente da \(n\) e da \(s\pmod 3\). Ma è più utile/educativo se lo trovi da solo/a facendo i calcoli.

[ZfreS]

"s" per cosa sta?

[vict85]

Il numero della mossa, ma facendo qualche conto mi ricordavo male. Quel modulo non dermina ogni cosa, solo i due pioli (ma non la direzione). La direzione la devi determinare in base a quale delle die mosse è ammissibile

[vict85]

Comunque ho implementato il gioco in C++, qui c'è l'implementazione (la dimensione della torre deve essere specificata in fase di compilazione):

Codice:

#include "TorreHanoiGioco.h"

//template<size_t N>
//void solve(vict::TorreHanoiGioco<N>& torre);

void solve(vict::TorreHanoiGioco<3>& torre)
{
   constexpr size_t S = vict::TorreHanoiGioco<3>::sorgente;
   constexpr size_t A = vict::TorreHanoiGioco<3>::ausiliario;
   constexpr size_t D = vict::TorreHanoiGioco<3>::destinazione;

   // esempio
   torre.mossa(S, D);
   torre.mossa(S, A);
   torre.mossa(D, A);
   torre.mossa(S, D);
   torre.mossa(A, S);
   torre.mossa(A, D);
   torre.mossa(S, D);
}

int main()
{
   constexpr size_t N = 3;
   vict::TorreHanoiGioco<N> torre;

   solve(torre);

   std::cout << "problema " << (torre.check() ? "" : "non ") << "risolto in "
      << torre.numero_mosse() << " mosse." << std::endl;
}

TorreHanoiGioco.h:

Codice:

#pragma once

#include "stack-fixed.h"

#include <iostream>
#include <cstdint>

namespace vict
{
   template <size_t N>
   class TorreHanoiGioco
   {
   public:
      TorreHanoiGioco() : _mosse(0) {
         for (size_t i = N; i != 0; --i)
         {
            _pali[sorgente].push(i);
         }
      };

      bool mossa(size_t i, size_t j)
      {
         bool res = false;
         if (i < N && j < N)
         {
            size_t li = _pali[i].last_or(N + 1);
            size_t lj = _pali[j].last_or(N + 1);
            if (li < lj) { res = mossa_internal(i, j); }
            else if (li > lj) {
               res = mossa_internal(j, i);
            }
         }
         if (!res)
         {
            std::cout << "Mossa non valida tra " << i << " e " << j << std::endl;
         }
         return res;
      }

      size_t numero_mosse()
      {
         return _mosse;
      }

      bool check()
      {
         if (!_pali[destinazione].full()) return false;
         size_t* arr = _pali[destinazione].get_data();
         for (size_t i = 0; i != N; ++i)
         {
            if (*(arr + i) != N - i) return false;
         }
         return true;
      }

      static size_t constexpr sorgente = 0;
      static size_t constexpr ausiliario = 1;
      static size_t constexpr destinazione = 2;

   private:
      bool mossa_internal(size_t i, size_t j)
      {
         size_t elem;
         if (!_pali[i].pop(elem)) return false;
         if (!_pali[j].push(elem)) return false;
         std::cout << "Mosso da " << i << " in " << j << std::endl;
         _mosse++;
         return true;
      }

      FixedStack<size_t, N> _pali[3];
      size_t _mosse = 0;
   };
}

stack-fixed.h

Codice:

#pragma once
#include <cstddef>

namespace vict {
   template < typename T, size_t N >
   class FixedStack
   {
   public:
      FixedStack() noexcept : _end(0) {};
      ~FixedStack() = default;

      // not copyable
      FixedStack(const FixedStack&) = delete;
      FixedStack& operator=(const FixedStack&) = delete;

      size_t num_entry() noexcept
      {
         return _end;
      }

      bool push(T element) noexcept
      {
         if (full())
            return false;

         _data[_end] = std::move(element);
         _end++;
         return true;
      }

      bool pop(T& element) noexcept
      {
         if (empty())
            return false;
         element = _data[--_end];
         return true;
      }

      bool last(T& element)
      {
         if (empty())
            return false;
         element = _data[_end - 1];
         return true;
      }

      T last_or(T value = T()) noexcept
      {
         return empty() ? value : _data[_end - 1];
      }

      T* get_data()
      {
         return &_data[0];
      }

      bool empty() noexcept
      {
         return _end == 0;
      }

      bool full() noexcept
      {
         return _end == N;
      }

   private:
      T _data[N];
      size_t _end;
   };
} // namespace vict


L'implementazione della funzione solve non è inclusa nel codice per darti la possibilità di testare i tuoi algoritmi. Ho inserito una implementazione banale della funzione nel caso N=3 per mostrarti come usare la classe.

P.S.: Ho creato la classe FixedStack perché mi andava, ma puoi usare qualsiasi classe simile al suo posto. Esistono anche altri approcci. Il gioco stampa a video le mosse fatte.

[ZfreS]

Non ho ancora studiato i template, ma proverò a studiare il tuo codice, potrei chiederti su cosa si basa? Comunque grazie infinite per l'aiuto, davvero molto gentile!

[ZfreS]

Che altri aprocci esistono?

[vict85]

Non è essenziale avere una classe per esempio. L'uso dei template non è necessario ed è semplice scrivere una versione in cui N viene inserito dall'utente. Il gioco stesso può probabilmente essere implementato usando meno memoria e suppongo che sia possibile implementare la funzione solve senza la limitazione n < 32 o 64. L'interfaccia della classe può essere tranquillamente diversa e potresti voler spostare o rimuovere l'output sulla console. Insomma ci sono tante piccole cose che possono cambiare.