Turnurile din Hanoi

Aspecte teoretice:

Se spune că în Vietnamul antic, în Hanoi, erau trei turnuri, pe unul din ele fiind puse, în ordinea descrescătoare a diametrelor lor, mai multe (opt) discuri de aur. Din motive obiective, niște călugări, care le aveau în grijă, trebuiau să așeze discurile pe cel de-al doilea turn, în aceeași ordine. Ei puteau să folosească, eventual, turnul al treilea, deoarece, altfel discurile nu ar fi avut stabilitate. Discurile puteau fi mutate unul câte unul. De asemenea, nu era permis a așeza un disc mai mare peste unul mai mic, pentru ca cel de deasupra să nu-l strice pe cel de dedesubt.

Indicații de rezolvare:

Deși, aparent simplă, după câteva încercări, folosind un prototip în miniatură, cititorul va constata că problema nu e banală. Însă este posibilă o rezolvare optimă a ei (cu numai 2n-1 mutări, deci 255, pentru n=8), folosind tehnica recursivă Divide-et-impera.
Problema este de a muta n discuri de la turnul 1 la turnul 2. Pentru a o rezolva, să vedem cum se mută, în general, n discuri de la un turn p la un turn q. Se mută primele n-1 discuri de pe p pe r, r fiind turnul auxiliar, apoi singurul disc rămas pe p (discul cel mai mare) se mută de pe p pe q, după care cele m-1 discuri sunt mutate de pe r pe q.
Firește, mutarea celor n-1 discuri de la p la r și de la r la q se realizează la fel, deci prin
apeluri recursive.
Mutarea primelor n-1 discuri este corectă, deoarece existența discurilor de diametre mai mari, la bazele celor trei turnuri nu afectează cu nimic mutările discurilor mai mici.
În cazul limită n=1, avem doar o mutare a discului din vârful turnului p spre q, adică problema se rezolvă direct. Putem spune, așadar, că avem o descompunere în trei probleme a problemei mari.

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace HanoiCS
{
    class Program
    {
        static void hanoi(double x, char from, char to, char aux)
        {
            if (x == 1)
            {
                Console.WriteLine("Muta discul de la " + from + " la " + to);
            }
            else
            {
                hanoi(x - 1, from, aux, to);
                Console.WriteLine("Muta discul de la " + from + " la " + to);
                hanoi(x - 1, aux, to, from);
            } 
        }
        static void Main(string[] args)
        {
            double disk;
            double moves;
            Console.Write("Introduceti numarul de discuri: ");
            disk = Convert.ToInt32(Console.ReadLine());
            moves = Math.Pow(2, disk) - 1;
            Console.WriteLine("Numarul de miscari efectuate: " + moves);
            hanoi(disk, '1', '3', '2');
            Console.ReadLine();
        }
    }
}

Cod Sursa VB

Module Module1
    Sub hanoi(ByVal x As Double, ByVal from As Integer, ByVal too As Integer, ByVal aux As Integer)
        If (x = 1) Then
            Console.WriteLine("Muta discul de la " & from & " la " & too)
        Else
            hanoi(x - 1, from, aux, too)
            Console.WriteLine("Muta discul de la " & from & " la " & too)
            hanoi(x - 1, aux, too, from)
        End If
    End Sub
    Sub Main()
        Dim disk As Double
        Dim moves As Double
        Console.Write("Introduceti numarul de discuri: ")
        disk = Convert.ToInt32(Console.ReadLine())
        moves = Math.Pow(2, disk) - 1
        Console.WriteLine("Numarul de miscari efectuate este: " & moves)
        hanoi(disk, 1, 3, 2)
        Console.ReadLine()
    End Sub
 
End Module

Cod Sursa C++

#include "stdafx.h"
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<cmath>
using namespace std;
 
void hanoi(int x, char from, char to, char aux)
{
	if(x==1)
	{
		cout<<"Muta discul de la " <<from<< " la "<<to<<endl;
	}
	else
	{
		hanoi(x-1,from,aux,to);
		cout<<"Muta discul de la " <<from<< " la "<<to<<endl;
		hanoi(x-1,aux,to,from);
	} 
}
int main()
{
	double disk; 
	double moves; 
	cout<<"Introduceti numarul de discuri: ";
	cin>>disk;
	moves = pow(2,disk)-1; 
	cout<<"Numarul de miscari efectuate: "<<moves<<endl;
	hanoi(disk,'A','C','B');
	system("Pause");
}

Cod Sursa JAVA

 

import java.io.*; class HanoiJAVA     {         static void hanoi(double x, char from, char to, char aux)         {             if (x == 1)             {                 System.out.println("Muta discul de la " + from + " la " + to);             }             else             {                 hanoi(x - 1, from, aux, to);                 System.out.println("Muta discul de la " + from + " la " + to);                 hanoi(x - 1, aux, to, from);             }         }        public static void main(String args[])         {           String line = null;             double disk=0;             double moves;             System.out.println(“Introduceti numarul de discuri: “);             try       {           BufferedReader is = new BufferedReader(new InputStreamReader(System.in));           line = is.readLine();           disk = Integer.parseInt(line);         }         catch (NumberFormatException ex)         {           System.err.println(“Not a valid number: ” + line);         }         catch (IOException e)         {           System.err.println(“Unexpected IO ERROR: ” + e);         }             moves = Math.pow(2, disk) – 1;             System.out.println(“Numarul de miscari efectuate: ” + moves);             hanoi(disk, ‘1’, ‘3’, ‘2’);         }     }

Cod Sursa LISP

(defun dohanoi(n to from u)
(cond
(
(> n 0)
(dohanoi (- n 1) u from to)
(format t “move ~D –> ~D~&” from to)
(dohanoi (- n 1) to u from)
)
)
)

(defun hanoi(n)
(dohanoi n 3 1 2)
)

Rezultat: