Java Programmeringsutmaning: Återvinna tornen i Hanoi - dummies

Denna utmaning hjälper dig att använda dina programmerings talanger för att skriva ett Java-program som kommer att skriva ut de steg som behövs för att lösa ett torn i Hanoi-pussel med tanke på antalet diskar.

Hanoi Towers är ett klassiskt logiskt pussel som består av tre vertikala pinnen och ett antal skivor med olika diametrar. Varje skiva har ett hål i mitten, så att skivorna kan glida över pinnarna.

Pusslet börjar med alla skivor staplade på en av pinnarna, med den största skivan längst ner och den minsta längst upp. Pussens syfte är att flytta stapeln av skivor till en av de andra pinnarna, följ bara två enkla regler: (1) du kan bara flytta en skiva åt gången och (2) du aldrig kan placera en större skiva på toppen av en mindre.

Följande bild visar lösningen för en stapel med tre skivor. Som du kan se behöver lösningen sju steg:

Flytta disk 1 från Peg 1 till Peg 3.
Flytta disk 2 från Peg 1 till Peg 2.
Flytta disk 1 från Peg 3 till Peg 2.
Flytta disk 3 från Peg 1 till Peg 3.
Flytta disk 1 från Peg 2 till Peg 1.
Flytta disk 2 från Peg 2 till Peg 3.
Flytta disk 1 från Peg 1 till Peg 3.

Efter dessa sju steg kommer stacken av skivor att vara på Peg 3.

Lösningen för tornen i Hanoi pussel med tre skivor.

Pusslet blir intressant när du börjar lägga till skivor till startpositionen. Med tre skivor kräver pusslet bara 7 steg för att lösa. Med fyra skivor krävs 15 drag. Med fem skivor behöver du 31 drag. Sex diskar kräver 64 drag.

Om du har följt matematiken ökar antalet rörelser som krävs för att lösa pusslet exponentiellt, eftersom antalet diskar ökar. Specifikt är antalet rörelser som krävs för att flytta n skivor 2 ⁿ - 1. En stack på 20 diskar kräver 2 ²⁰ - 1 rörelser; det är mer än en miljon flyttar!

En intressant legend är förknippad med pusslet: På ett tempel i Hanoi har munkar arbetat på ett Towers of Hanoi-pussel med 64 diskar sedan jordens skapelse. När de är färdiga kommer världen att komma till ett slut. Lyckligtvis har vi lång tid att vänta: Om munkarna kan flytta en skiva per sekund kommer det att vara ytterligare 580 miljarder år innan de avslutar pusslet.

Din utmaning är enkel: Skriv ett Java-program som kommer att skriva ut de steg som behövs för att lösa en Towers of Hanoi-pussel med tanke på antalet diskar. Programmet bör först uppmana användaren för antalet skivor. Då ska det visa stegen, en per rad.Varje steg ska ange vilken pinne som ska flyttas en skiva från, och vilken pek för att flytta skivan till. Stegen bör också sekventiellt numreras.

När programmet är klart, bör programmet upprepas och frågar användaren om antalet skivor igen. Programmet bör sluta när användaren anger 0.

Här är ett urval av konsolutmatningen som ditt program ska generera:

Hur många diskar? (0 till slutet) 3 1: 1 till 3 2: 1 till 2 3: 3 till 2 4: 1 till 3 5: 2 till 1 6: 2 till 3 7: 1 till 3 Hur många diskar ? (0 till slutet) 0

Det enda andra kravet på att lösa denna utmaning är att din lösning måste använda rekursiv programmering. Med andra ord måste din lösning innehålla en metod som kallar sig för att lösa pusslet.

Rekursiv programmering kan vara utmanande, så här är några tips till lösningen av detta pussel:

Pusslet består av tre pinnar. En av dem innehåller startstapeln av diskar; Ring den här pinnen till källpinnen . En av de återstående två pinnarna är pinnen som du vill flytta stapeln av skivor till; Ring den här pinnen på målstiftet . Den tredje pinnen är tillgänglig för dig att använda som mellanliggande pinne för att lagra diskar på tillfälligt när du flyttar dem. Ring den här pinnen till reservpinnen .
Din rekursiva metod bör acceptera tre parametrar: antalet skivor att flytta, källpinnen och målpinnen. Använd heltalsvärdena 1, 2 och 3 för att representera pinnarna.
Grundläggande idén om att lösa pusslet återkommande är det här: Att flytta en stapel skivor från en källpinne till en målpinne kräver tre steg:
1. Flytta alla skivor i stapeln förutom den nedre skivan till reservpinne.
2. Flytta den största skivan i originalstacken till målpinnen.
3. Flytta stapeln du flyttat i steg 1 från reservpinnen till målpinnen.
Naturligtvis tillåter pusselregler dig att bara flytta en skiva åt gången, så att du inte kan åstadkomma steg 1 och 3 i proceduren som ges här genom att helt enkelt plocka upp stapeln och flytta den. Det är där rekursionen kommer in. För steg 1 och 3 ringer du metoden rekursivt, varje gång du anger en färre disk som ska flyttas, och varje gång du använder föregående målstift som reservpinnen.
Undrar varför den rekursiva metoden inte behöver acceptera reservpinnen som ett argument? Eftersom du enkelt kan beräkna den, med tanke på käll- och målpinnen. Eftersom det bara finns tre pinnar, numrerade 1, 2 och 3, är summan av de tre pinnarna 6 (1 + 2 + 3). Med tanke på käll- och målstiften kan du beräkna reservpinnen genom att subtrahera käll- och målpinnen från 6. Om till exempel källpinnen är 1 och målpinnen är 3 måste reservpinnen vara 2 eftersom

6 - 3 - 1 = 2.