PER SCALARE LA TORRE DI HANOI SERVE UN ALGORITMO RICORSIVO

PER SCALARE LA TORRE DI HANOI SERVE UN ALGORITMO RICORSIVO

Digital

19/10/2017 Release by Formati e occupati

In Sintesi

L'algoritmo ricorsivo e il rompicapo di Hanoi

La notizia

<div style="text-align:justify">
<span style="font-size: 12pt;" data-mce-style="font-size: 14pt; color: #808080;">
</br>
L’algoritmo ricorsivo è particolarmente utile per eseguire compiti ripetitivi su set di variabili in input perché è in grado di richiamare se stesso generando una sequenza di operazioni che possono terminare solo quando si verifica una specifica condizione detta di terminazione.

PRO: la tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molteplici tipologie di problemi comuni.
CONTRO: la ricorsione viene di norma implementata attraverso funzioni che per essere invocate necessitano di un costo rilevante a discapito, talvolta, dell’efficienza.

Tra gli esempi più comuni ci sono il calcolo del fattoriale e la sequenza di Fibonacci di cui abbiamo parlato anche qui.
Questo Javadì vogliamo proporvi la Torre di Hanoi, un rompicapo matematico composto da tre paletti e un certo numero di dischi che possono essere infilati in una qualunque delle colonne.
Il gioco, inventato nel 1883 dal matematico francese Edouard Lucas, inizia posizionando tutti i dischi su un unico paletto in ordine decrescente in modo da formare un cono.
Lo scopo finale è quello di spostare tutti i dischi da una colonna all’altra potendone tuttavia sfilare uno alla volta e appoggiandoli solamente su quelli più grandi, mai sui più piccoli.
Vediamo un po’ come possiamo scriverla in codice:

</div>
<div style="text-align:center">
<span style="font-size: 14pt;color: #0D97FF;" data-mce-style="font-size: 14pt; color: #808080;">CODICE</div>
</br>
<div style="width:90%;border:2px solid black;padding:20px;box-shadow: 8px 10px 12px -4px rgba(0,0,0,0.65);border: 9px double #000000;border-radius: 5px 5px 5px 5px;background-color:#B0C2B3;margin-left:5%;margin-right:5%;">
<code style="color:#FFE719;font-size:12px;background-color:inherit">
package javadi;

import java.util.Scanner;

public class Hanoi
{
   public static void main(String[] args)
   {
             System.out.println("Inserire il numero di dischi");
            Scanner tastiera = new Scanner(System.in);
         int num=Integer.parseInt(tastiera.nextLine());
         TorreHanoi(num, 1, 2, 3);
          tastiera.close();
    }
   public static void TorreHanoi(int nDischi, int pioloOrigine, int pioloAppoggio, int pioloDestinazione)
   {
       if(nDischi == 1)
          System.out.println("Sposto dal piolo "+pioloOrigine + " al piolo " + pioloDestinazione);
       else
       {
          TorreHanoi(nDischi-1, pioloOrigine , pioloDestinazione, pioloAppoggio    )
          TorreHanoi(1,                     pioloOrigine , pioloAppoggio    , pioloDestinazione);
          TorreHanoi(nDischi-1, pioloAppoggio, pioloOrigine     , pioloDestinazione);  
        }
    }
}
</code>
</div>
</br>
<div style="text-align:center">
<span style="font-size: 14pt;color: #0D97FF;" data-mce-style="font-size: 14pt; color: #808080;">CURIOSITÀ</div>
<div style=’text-align:justify’>
<span style="font-size: 12pt;" data-mce-style="font-size: 14pt; color: #808080;">
Secondo la famosa leggenda sul rompicapo di Hanoi, la divinità induista Brahma (creatrice dell’intero universo materiale) portò nel grande tempio di Benares, tre colonnine di diamante e, su una di esse collocò sessantaquattro dischi d’oro in ordine decrescente mantenendo il più piccolo in alto e finendo con il più grande in basso.
La divinità disse ai monaci di spostare i dischi dalla prima alla terza colonnina seguendo regole ben precise, le stesse spiegate in precedenza.
Una volta completato il compito, la torre crollerà e, con essa, il mondo intero.

Siccome il gioco si basa sulla proprietà matematica 2n-1 (il numero minimo di mosse necessarie a compiere il gioco), se supponiamo di avere 3 dischi, il numero di mosse minime da fare sarebbe 7 e quindi i monaci dovrebbero effettuare almeno 18.446.744.073.709.551.615.
Se infine supponiamo che compiano una mossa al secondo, il mondo non finirà prima di 5.845.580.504 secoli quando ormai il sole avrà bruciato la Terra.
<hr style="border-color: grey; height:10px;">
Se ti è piaciuto l’articolo, faccelo sapere nei commenti e condividilo coi tuoi amici.
Se ne vuoi altri, visita il nostro blog
Per non perdere le nostre rubriche sul mondo del #lavoro, #digital e #IT, continua a seguirci su Facebook
Se infine vuoi una panoramica sui corsi, clicca qui
</div>



Allegati:

ANT srl - Formati e Occupati news


23/10/2017

SOLUZIONE al #DEBUGFRIDAY del 20 Ottobre

Soluzione al Debug Friday del 20 Ottobre

23/10/2017

UNIVERSITÀ E LAVORO NELL'ERA DIGITALE

Università e lavoro nell’era digitale; come creare opportunità professionali per il futuro

20/10/2017

DEBUG FRIDAY DEL 20 OTTOBRE

Debug Friday del 20 Ottobre