Hanojske kule
vreme | memorija | ulaz | izlaz |
---|---|---|---|
10 s | 256 Mb | standardni izlaz | standardni ulaz |
Data su tri štapa i na jednom od njih N diskova, različitih veličina, poređani po veličini. Potrebno je prebaciti diskove na drugi štap. Pravila prebacivanja su sledeća:
- U jednom koraku može se prebaciti disk sa vrha štapa na vrh drugog štapa.
- U svakom trenutku diskovi na štapovima moraju biti poređani po veličini.
Napisati program koji pronalazi minimalni broj prebacivanje i koji štampa proceduru prebacivanje.
Oznake štapova su A, B i C. Na početku diskovi su postavljeni na štap A i potrebno ih je prebaciti na štap C.
U prvom i jedinom redu ulaza nalazi se prirodni broj N.
U prvom redu izlaza štampati dva prirodna broja N i M, gde je N broj diskova a M minimalni broj prebacivanja. U narednih M redova štampati proceduru prebacivanja. Procedura prebacivanja se sastoji od M prebacivanja, u poretku izvršavanja, koja su opisana formom "stapA stapB disk". Prebacivanje "stapA stabB diskID" opisuje da se u datom potezu disk veličine diskID prebacuje sa štapa stabA na štap stapB (gde je naravno potreban uslov da je diskID na vrhu štapa stapA).
- 1 <= N <= 12
3
3 7
A C 1
A B 2
C B 1
A C 3
B A 1
B C 2
A C 1
Za dodatno objašnjenje i tok prebacivanja pogledati sliku.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.