Šeštadieninė informatikos olimpiadininkų mokykla

Papildysime standartinę Hanojaus bokšto uždavinio formuluotę:

• Vienu ėjimu galima kelti tik vieną diską.
• Diską galima užmauti tik ant tuščio stiebo, arba uždėti ant didesnio už jį disko.
• Negalima kelti disko nuo kairiojo stiebo ant dešiniojo, ir atvirkščiai. Visi kėlimai turi vykti per tarpinį stiebą.

Mūsų uždavinyje stiebai yra pavadinti raidėmis A, B ir C, taigi disko negalima tiesiogiai kelti nuo stiebo A ant stiebo C, ir atvirkščiai – nuo C ant A. Parašykite programą, kuri atspausdintų ėjimus, kuriuos reikia atlikti, kad visus N diskų perkeltume nuo stiebo A ant stiebo C, laikantis minėtųjų taisyklių. Negana to, atliekamų ėjimų skaičius turi būti minimalus.

Pradiniai duomenys

Pradinių duomenų faile įrašytas vienintelis sveikas skaičius N () – diskų skaičius.

Rezultatai

Rezultatų failą turi sudaryti seka ėjimų, kuriuos atlikus visi diskai būtų perkelti nuo stiebo A ant stiebo C. Ėjimas aprašomas formatu X -> Y (čia X ir Y yra stiebų vardai A, B arba C). Užrašas X -> Y reiškia, kad nuo stiebo X reikia paimti mažiausią (taigi viršuje esantį) diską ir užmauti ant stiebo Y.

Pavyzdžiai

1

A -> B
B -> C

2

A -> B
B -> C
A -> B
C -> B
B -> A
B -> C
A -> B
B -> C

Patarimai

Spręskite uždavinį tokiu eiliškumu:

1. Išspręskite elementarius atvejus ranka
2. Kiek ėjimų reikia atlikti, norint perkelti 0, 1, 2, 3 diskus?
3. Prieš keliant didžiausiąjį diską, kur turi atsidurti visi likę?
4. Tarkime, jog mokame perkelti n-1 diskų. Kaip perkelti n diskų?
5. Kiek ėjimų reikia atlikti, norint perkelti n diskų?
6. Parašykite rekursyvią funkciją, paaiškinančią, kaip perkelti n diskų.