Java Programmeringsutfordring: Tilbakekalling av Towers of Hanoi - dummies

Denne utfordringen hjelper deg med å bruke programmeringstalenter til å skrive et Java-program som vil skrive ut trinnene som trengs for å løse et Towers of Hanoi-puslespill, gitt antall disker.

Hanoi Towers er et klassisk logisk puslespill som består av tre vertikale pinner og en rekke disker med ulike diametre. Hver disk har et hull i midten, slik at platene kan glides over pinnene.

Puslespillet starter med alle platene stablet på en av pinnene, med den største disken nederst og den minste på toppen. Formålet med puslespillet er å flytte stakken av disker til en av de andre pinnene, og overholde bare to enkle regler: (1) du kan bare flytte en plate om gangen, og (2) du aldri kan plassere en større disk på toppen av en mindre.

Følgende figur viser løsningen for en stabel med tre disker. Som du kan se, krever løsningen syv trekk:

Flytt disk 1 fra Peg 1 til Peg 3.
Flytt disk 2 fra Peg 1 til Peg 2.
Flytt disk 1 fra Peg 3 til Peg 2.
Flytt disk 3 fra Peg 1 til Peg 3.
Flytt disk 1 fra Peg 2 til Peg 1.
Flytt disk 2 fra Peg 2 til Peg 3.
Flytt disk 1 fra Peg 1 til Peg 3.

Etter disse syv trinnene, vil stakken av disker være på Peg 3.

Løsningen for tårnene i Hanoi puslespill med tre disker.

Puslespillet blir interessant når du begynner å legge disker til startposisjonen. Med tre disker krever puslespillet bare 7 trekk for å løse. Med fire disker er det nødvendig med 15 trekk. Med fem disker trenger du 31 trekk. Seks disker krever 64 trekk.

Hvis du har fulgt matematikken, øker antallet flyttinger som kreves for å løse puslespillet eksponentielt etter hvert som antall disker øker. Spesielt er antall flyttinger som kreves for å flytte n disker, 2 ⁿ - 1. For eksempel vil en stabel på 20 disker kreve 2 ²⁰ - 1 trekk; det er mer enn en million trekk!

En interessant legende er knyttet til puslespillet: På et tempel i Hanoi har munker jobbet på et tårn i Hanoi-puslespillet med 64 disker siden jordens oppbyggelse. Når de er ferdige, kommer verden til en slutt. Heldigvis har vi lang tid å vente: Hvis munkene kan flytte en disk per sekund, vil det være ytterligere 580 milliarder år eller så før de fullfører puslespillet.

Din utfordring er enkel: Skriv et Java-program som vil skrive ut trinnene som trengs for å løse et Towers of Hanoi-puslespill, gitt antall disker. Programmet bør først spørre brukeren for antall disker. Da skal det vise trinnene, en per linje.Hvert trinn skal indikere hvilken pinne som skal flyttes en disk fra, og hvilken pinne som skal flyttes til. Trinnene bør også sekvensielt nummereres.

Når programmet er ferdig, bør programmet gjenta, og spør brukeren om antall disker igjen. Programmet bør avsluttes når brukeren kommer inn 0.

Her er et eksempel på konsollutgangen ditt program skal generere:

Hvor mange disker? (0 til slutt) 3 1: 1 til 3 2: 1 til 2 3: 3 til 2 4: 1 til 3 5: 2 til 1 6: 2 til 3 7: 1 til 3 Hvor mange disker ? (0 til slutt) 0

Det eneste andre kravet for å løse denne utfordringen er at løsningen din må bruke rekursiv programmering. Med andre ord, må løsningen inneholde en metode som kaller seg for å løse puslespillet.

Rekursiv programmering kan være utfordrende, så her er noen få tips til løsningen av dette puslespillet:

Puslespillet består av tre pinner. En av dem inneholder startstakken av disker; ring denne pinnen til kildepinnen . En av de resterende to pinnene er pinnen du vil flytte stakken av disker til; ring denne pinnen til måletegn . Den tredje pinnen er tilgjengelig for at du kan bruke som mellomliggende pinne til å lagre disker midlertidig når du flytter dem. Ring denne pinnen til reservepenne .
Din rekursive metode bør akseptere tre parametere: antall disker som skal flyttes, kildepinne og målpinnen. Bruk tallverdiene 1, 2 og 3 til å representere pinnene.
Den grunnleggende ideen om å løse puslespillet rekursivt er dette: For å flytte en stabel med disker fra en kildepinne til et målpinne, krever tre trinn:
1. Flytt alle platene i stakken, bortsett fra den nederste disken til reservedel.
2. Flytt den største disken i den originale stakken til målpinnen.
3. Flytt stakken du flyttet i Trinn 1 fra reservepinnen til målpinnen.
Selvfølgelig gir puslespillreglene deg muligheten til å flytte bare en disk om gangen, slik at du ikke kan utføre trinn 1 og 3 i prosedyren som er gitt her, ved å bare plukke opp stakken og flytte den. Det er her rekursjonen kommer inn. For trinn 1 og 3, kaller du metoden rekursivt, hver gang du angir en færre disk som skal flyttes, og hver gang du bruker den forrige målpinnen som reservepinnen.
Lurer på hvorfor den rekursive metoden ikke trenger å godta reservepenningen som et argument? Fordi du enkelt kan beregne den, gitt kilde- og målpinnene. Siden det bare er tre pinner, nummerert 1, 2 og 3, er summen av de tre pinnene 6 (1 + 2 + 3). Gitt kilde- og målpinnene kan du beregne reservepinnen ved å trekke kilde- og målpinnen fra 6. Hvis kildepinnen er 1 og målpinnen er 3, må reservepinnen være 2 fordi

6 - 3 - 1 = 2.