Java Programming Challenge: Recursing the Towers of Hanoi - dummies

Deze uitdaging helpt je om je programmeertalenten te gebruiken om een ​​Java-programma te schrijven dat de stappen zal afdrukken die nodig zijn om een ​​Towers of Hanoi-puzzel op te lossen gezien het aantal schijven.

De Towers of Hanoi is een klassieke logische puzzel die bestaat uit drie verticale pinnen en een aantal schijven van verschillende diameters. Elke schijf heeft een gat in het midden, waardoor de schijven over de pinnen kunnen worden geschoven.

De puzzel begint met alle schijven die op een van de pinnen zijn gestapeld, met de grootste schijf aan de onderkant en de kleinste aan de bovenkant. Het doel van de puzzel is om de stapel schijven naar een van de andere pegs te verplaatsen, volgens slechts twee eenvoudige regels: (1) je kunt maar één schijf tegelijkertijd verplaatsen, en (2) je kunt nooit een grotere schijf plaatsen top van een kleinere.

De volgende afbeelding toont de oplossing voor een stapel van drie schijven. Zoals u kunt zien, heeft de oplossing zeven zetten nodig:

1. Verplaats schijf 1 van pin 1 naar pin 3.

2. Verplaats schijf 2 van pin 1 naar pin 2.

3. Verplaats schijf 1 van pin 3 naar pin 2.

4. Verplaats Disk 3 van Peg 1 naar Peg 3.

5. Verplaats Disk 1 van Peg 2 naar Peg 1.

6. Verplaats Disk 2 van Peg 2 naar Peg 3.

7. Verplaats Schijf 1 van Peg 1 naar Peg 3.

Na deze zeven stappen bevindt de stapel schijven zich op Peg 3.

De oplossing voor de Towers of Hanoi puzzel met drie schijven.

De puzzel wordt interessant wanneer je begint met het toevoegen van schijven aan de startpositie. Met drie schijven heeft de puzzel slechts zeven zetten nodig om op te lossen. Met vier schijven zijn 15 zetten vereist. Met vijf schijven heb je 31 zetten nodig. Zes schijven vereist 64 zetten.

Als je de wiskunde hebt gevolgd, neemt het aantal zetten dat nodig is om de puzzel op te lossen exponentieel toe naarmate het aantal schijven toeneemt. Het aantal verplaatsingen dat nodig is om n schijven te verplaatsen is 2 ⁿ - 1. Voor een stapel van 20 schijven zijn bijvoorbeeld 2 ²⁰ nodig - 1 verplaatsingen; dat zijn meer dan een miljoen bewegingen!

Een interessante legende wordt geassocieerd met de puzzel: in een tempel in Hanoi werken monniken aan een puzzel van Towers of Hanoi met 64 schijven sinds de schepping van de aarde. Als ze klaar zijn, komt er een einde aan de wereld. Gelukkig moeten we lang wachten: als de monniken één schijf per seconde kunnen verplaatsen, duurt het nog eens 580 miljard jaar voordat ze de puzzel hebben voltooid.

Je uitdaging is simpel: schrijf een Java-programma dat de stappen zal afdrukken die nodig zijn om een ​​Towers of Hanoi-puzzel op te lossen gezien het aantal schijven. Het programma moet de gebruiker eerst vragen om het aantal schijven. Vervolgens worden de stappen weergegeven, één per regel.Elke stap moet aangeven naar welke peg een schijf moet worden verplaatst en naar welke peg de schijf moet worden verplaatst. De stappen moeten ook opeenvolgend worden genummerd.

Als het programma eenmaal is voltooid, moet het worden herhaald en moet de gebruiker opnieuw het aantal schijven opvragen. Het programma moet eindigen wanneer de gebruiker 0. invoert.

Hier is een voorbeeld van de console-uitvoer die uw programma zou moeten genereren:

Hoeveel schijven? (0 tot einde) 3 1: 1 tot 3 2: 1 tot 2 3: 3 tot 2 4: 1 tot 3 5: 2 tot 1 6: 2 tot 3 7: 1 tot 3 Hoeveel schijven ? (0 tot eind) 0

De enige andere vereiste voor het oplossen van deze uitdaging is dat uw oplossing recursieve programmering moet gebruiken. Met andere woorden, uw oplossing moet een methode bevatten die zichzelf oproept om de puzzel op te lossen.

Recursieve programmering kan een uitdaging zijn, dus hier zijn enkele hints voor de oplossing van deze puzzel:

• De puzzel bestaat uit drie pinnen. Een van hen bevat de beginstack van schijven; noem deze peg de source peg . Een van de resterende twee pegs is de peg waarnaar u de stapel schijven wilt verplaatsen; noem deze peg de doelpeg . De derde peg is beschikbaar voor u om te gebruiken als een tussenliggende peg om schijven tijdelijk op te slaan terwijl u ze verplaatst. Roep deze peg op de reservepeg .

• Uw recursieve methode moet drie parameters accepteren: het aantal schijven dat moet worden verplaatst, de bronpeg en de doelpeg. Gebruik de waarden voor gehele getallen 1, 2 en 3 om de pegs weer te geven.

• Het basisidee om de puzzel recursief op te lossen is als volgt: om een ​​stapel schijven van een bronpeg naar een doelpeg te verplaatsen, zijn drie stappen nodig:

  1. Verplaats alle schijven in de stapel met uitzondering van de onderste schijf naar de reservepen.

  2. Verplaats de grootste schijf in de originele stapel naar de doelpin.

  3. Verplaats de stapel die je hebt verplaatst in stap 1 van de reservepeg naar de doelpin.

• Natuurlijk kunt u met puzzelregels slechts één schijf tegelijk verplaatsen, dus u kunt stap 1 en 3 van de hier beschreven procedure niet uitvoeren door eenvoudigweg de stapel op te pakken en te verplaatsen. Dat is waar de recursie binnenkomt. Voor stap 1 en 3 roept u de methode recursief aan, elke keer dat u een minder schijf opgeeft die moet worden verplaatst, en elke keer dat u de vorige doelpin als reservepeg gebruikt.

• Vraagt ​​u zich af waarom de recursieve methode de reservepeg niet als argument hoeft te accepteren? Omdat je het gemakkelijk kunt berekenen, gegeven de bron en doelwit. Aangezien er slechts drie pegs zijn, genummerd 1, 2 en 3, is de som van de drie pegs 6 (1 + 2 + 3). Met de bron- en doelpegs kunt u de reservepeg berekenen door de bron- en doelpeg af te trekken van 6. Als de bronpeg bijvoorbeeld 1 is en de doelpeg 3, moet de reservepeg 2 zijn omdat

  6 - 3 - 1 = 2.

Ga voor de oplossing naar het tabblad Downloads van de productpagina Java All-in-One voor modellen, 4e editie.

Veel succes!