Gabi: Pagină nouă: == 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`...

2023-12-03T15:07:46Z

Pagină nouă: == Enunț == Turnurile din Hanoi este un joc matematic sau, dacă vreți, un puzzle. Este format din trei tije <code>A</code>, <code>B</code> și <code>C</code> și un număr variabil de discuri, de diferite diametre. Inițial discurile sunt așezate în ordine descrescătoare a diametrelor pe tija <code>A</code>, 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 <code>A</code> pe tija <code>C</code>...

New page

== Enunț ==
Turnurile din Hanoi este un joc matematic sau, dacă vreți, un puzzle. Este format din trei tije <code>A</code>, <code>B</code> și <code>C</code> și un număr variabil de discuri, de diferite diametre. Inițial discurile sunt așezate în ordine descrescătoare a diametrelor pe tija <code>A</code>, 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 <code>A</code> pe tija <code>C</code> folosind ca tijă intermediară tija <code>B</code>, 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 <code>n</code> de discuri aflate pe tija <code>A</code>, să se determine șirul mutărilor necesare pentru ca toate discurile să fie mutate pe tija <code>C</code>.

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

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 15</code>
* mutările vor fi scrise câte una pe linie, fără spații

= Exemplul 1 =
<code>hanoiIN.txt</code>
2
<code>hanoiOUt.txt</code>
3
A->B
A->C
B->C

== Exemplul 2 ==
<code>hanoiIN.txt</code>
16
<code>hanoiOUt.txt</code>
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>

2527 - Hanoi - Revision history