Naloge iz programiranja

Hanoiski stolpiči

Obstaja legenda, ki pravi, da so v hindujskem templju tri palice. Na začetku je bil na prvi sklad iz 64 zlatih obročev. Vsi so bili različne velikosti in zloženi po velikosti, tako da so bili manjši obroči na večjih v obliki piramide. Brahmani premikajo te diske v skladu z pradavnimi pravili. Njihov cilj je vse diske prenesti na zadnjo palico, pri čemer morajo upoštevati pravila:

  • vedno lahko premaknejo le po en disk naenkrat (to imenujemo poteza);
  • na katerikoli palici morajo biti diski vedno razporejeni od največjega (na dnu) do najmanjšega (na vrhu).
Zanima nas, kako morajo svečeniki prestavljati obroče, da bodo naredili kar se da malo potez. Ker se izkaže, da je 64 obročev zelo veliko, naj bo število obročev na začetni palici parameter programa.

Namig