Hanojaus bokštai 2


Pradinių duomenų failas:
hanoj.in  
Rezultatų failas:
hanoj.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

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 (1 <= N <= 10) – 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

Pradiniai duomenys Rezultatai
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ų.