2527 - Hanoi

Enunț

Turnurile din Hanoi este un joc matematic sau, dacă vreți, un puzzle. Este format din trei tije A, B și C și un număr variabil de discuri, de diferite diametre. Inițial discurile sunt așezate în ordine descrescătoare a diametrelor pe tija A, de la vârf către bază, astfel încât să formeze un turn.

Scopul jocului este acela de a muta toate discurile de pe tija A pe tija C folosind ca tijă intermediară tija B, respectând următoarele reguli:

• la un moment dat doar un singur disc poate fi mutat
• fiecare mutare constă în luarea celui mai de sus disc de pe o tija și mutarea acestuia pe o altă tijă
• un disc cu diametrul mai mare nu poate fi poziționat deasupra unui disc cu diametrul mai mic.

Cerința

Dacă se cunoaște numărul n de discuri aflate pe tija A, să se determine șirul mutărilor necesare pentru ca toate discurile să fie mutate pe tija C.

Date de intrare

Fișierul de intrare hanoiIN.txt conține pe prima linie numărul natural nenul n, ce reprezintă numărul de discuri aflat pe tija A.

Date de ieșire

Fișierul de ieșire hanoiOUT.txt va conține pe prima linie numărul m, ce reprezintă numărul minim de mutări ce se efectuează. Pe următoarele m linii vor fi scrise mutările sub forma: tija sursă->tija destinație.

Restricții și precizări

• 1 ≤ n ≤ 15
• mutările vor fi scrise câte una pe linie, fără spații

Exemplul 1

hanoiIN.txt

2

hanoiOUt.txt

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

Exemplul 2

hanoiIN.txt

16

hanoiOUt.txt

Restrictii neindeplinite.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n):

   return 1 <= n <= 15

def hanoi(n, sursa, intermediar, destinatie, mutari):

   if n == 1:
       mutari.append(f"{sursa}->{destinatie}")
   else:
       hanoi(n-1, sursa, destinatie, intermediar, mutari)
       mutari.append(f"{sursa}->{destinatie}")
       hanoi(n-1, intermediar, sursa, destinatie, mutari)

def main():

   with open("hanoiIN.txt", "r") as f_input, open("hanoiOUT.txt", "w") as f_output:
       n = int(f_input.readline().strip())

       if not verifica_restrictii(n):
           f_output.write("Restrictii neindeplinite.\n")
           return

       mutari = []
       hanoi(n, 'A', 'B', 'C', mutari)

       f_output.write(str(len(mutari)) + "\n")
       for mutare in mutari:
           f_output.write(mutare + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>