Java Programmeringsudfordring: Genopretning af tårnene i Hanoi - dummies

Denne udfordring hjælper dig med at bruge dine programmeringstalenter til at skrive et Java-program, der vil udskrive de trin, der er nødvendige for at løse et tårn i Hanoi-puslespil i betragtning af antallet af diske.

Hanoi Towers er et klassisk logisk puslespil, der består af tre lodrette pinde og et antal diske med forskellige diametre. Hver disk har et hul i midten, så diskene kan glides over pinnene.

Puslespillet starter med alle de diske stablet på en af pinnene, med den største disk i bunden og den mindste øverst. Formålet med puslespillet er at flytte stakken af diske til en af de andre stifter, og overholde kun to enkle regler: (1) du kan kun flytte en disk ad gangen, og (2) du aldrig kan placere en større disk på toppen af en mindre.

Nedenstående figur viser løsningen for en stak på tre diske. Som du kan se, kræver løsningen syv bevægelser:

Flyt disk 1 fra Peg 1 til Peg 3.
Flyt disk 2 fra Peg 1 til Peg 2.
Flyt Disk 1 fra Peg 3 til Peg 2.
Flyt disk 3 fra Peg 1 til Peg 3.
Flyt disk 1 fra Peg 2 til Peg 1.
Flyt disk 2 fra Peg 2 til Peg 3.
Flyt disk 1 fra Peg 1 til Peg 3.

Efter disse syv trin vil stakken af diske være på Peg 3.

Løsningen til tårnene i Hanoi puslespil med tre diske.

Puslespillet bliver interessant, når du begynder at tilføje diske til startpositionen. Med tre diske kræver puslespillet kun 7 træk til at løse. Med fire diske kræves der 15 træk. Med fem diske skal du bruge 31 bevægelser. Seks diske kræver 64 træk.

Hvis du har fulgt matematikken, øges antallet af bevægelser, der kræves for at løse puslespillet eksponentielt, da antallet af diske stiger. Specifikt er antallet af træk, der kræves for at flytte n diske, 2 ⁿ - 1. For eksempel kræver en stak på 20 diske 2 ²⁰ - 1 træk; det er mere end en million flytter!

En interessant legende er forbundet med puslespillet: På et tempel i Hanoi har munkene arbejdet på et tårn i Hanoi-puslespil med 64 diske siden jordens skabelse. Når de er færdige, vil verden komme til en ende. Heldigvis har vi lang tid at vente: Hvis munkene kan flytte en disk per sekund, vil det være endnu 580 milliarder år eller deromkring, før de afslutter puslespillet.

Din udfordring er enkel: Skriv et Java-program, der udskriver de nødvendige skridt til at løse et tårn i Hanoi-puslespil i betragtning af antallet af diske. Programmet skal først spørge brugeren for antallet af diske. Så skal det vise trinene, en pr. Linje.Hvert trin skal angive, hvilken pinde der skal flyttes en disk fra, og hvilken peg for at flytte disken til. Trinnene skal også sekventielt nummereres.

Når programmet er færdigt, skal programmet gentage og spørge brugeren om antallet af diske igen. Programmet skal slutte, når brugeren indtaster 0.

Her er en prøve af det konsolprodukt, dit program skal generere:

Hvor mange diske? (0 til slut) 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 diske ? (0 til slut) 0

Det eneste andet krav til løsning af denne udfordring er, at din løsning skal bruge rekursiv programmering. Med andre ord skal din løsning indeholde en metode, der kalder sig til at løse puslespillet.

Rekursiv programmering kan være udfordrende, så her er et par tip til løsningen af dette puslespil:

Puslespillet består af tre pinde. En af dem indeholder startstakken af diske; kalder denne peg på kildepen . En af de resterende to pegs er den pinde, du vil flytte stakken af diske til; kalder denne peg på target peg . Den tredje peg er tilgængelig for dig som midlertidig peg til at gemme diske midlertidigt, mens du flytter dem. Kald denne peg på reservedele .
Din rekursive metode skal acceptere tre parametre: antallet af diske, der skal flyttes, kildepen og målestiften. Brug heltalværdierne 1, 2 og 3 til at repræsentere stifterne.
Grundlæggende ideen om at løse puslespillet rekursivt er dette: For at flytte en stak disketter fra en kildepind til en målstift skal der træffes tre trin:
1. Flyt alle diske i stakken undtagen bunddisken til reservepeg.
2. Flyt den største disk i den oprindelige stak til målestiften.
3. Flyt stakken du flyttede i trin 1 fra reservepenet til målestiften.
Selvfølgelig giver puslespilreglerne dig mulighed for kun at flytte en disk ad gangen, så du ikke kan udføre trin 1 og 3 i den procedure, der gives her, ved blot at hente stakken og flytte den. Det er her rekursionen kommer ind. For trin 1 og 3 kalder du metoden rekursivt, hver gang du angiver en færre disk, der skal flyttes, og hver gang du bruger den foregående målsnål som reservepenet.
Spekulerer på, hvorfor den rekursive metode ikke behøver at acceptere reservepenet som et argument? Fordi du nemt kan beregne det, givet kilde og mål pegs. Da der kun er tre stifter, nummereret 1, 2 og 3, er summen af de tre stifter 6 (1 + 2 + 3). I betragtning af kilde- og målestifterne kan du beregne reservepenet ved at trække kilde- og målstiftet fra 6. Hvis kildepenet er 1 og målestangen er 3, skal reservepenet være 2, fordi

6 - 3 - 1 = 2.