Școala Româno-Britanică
Modulul 5 Clasa a X-a | C++

Ora 6: Turnurile din Hanoi

Ce vei învăța astăzi: Problema clasică Turnurile din Hanoi (problema mutării a n discuri de pe o tijă pe alta, câte unul, fără a așeza un disc mare peste unul mic), rezolvarea recursivă și numărul de mutări 2^n - 1

Rezultat practic: Scrii programul recursiv pentru Hanoi în C++ și calculezi numărul de mutări (Competența 4.5)

Competența 4.5 Săptămâna 27

Înainte de a începe

De ce contează? Hanoi este problema clasică în care recursivitatea este soluția naturală, iar numărul de mutări 2^n - 1 este un rezultat cerut frecvent la teorie.

Ce știi deja?

Din ora 5, poți urmări execuția funcției cmmdc pe stivă? Care este cazul de bază al algoritmului lui Euclid?

Ideea-cheie: Pentru a muta n discuri, mutăm întâi n - 1 discuri pe tija auxiliară (tija de sprijin folosită temporar în timpul mutărilor), mutăm discul cel mare și apoi mutăm n - 1 discuri pe tija de destinație.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei rezolva problema Turnurile din Hanoi recursiv, vei înțelege numărul de mutări 2^n - 1 și vei scrie programul complet în C++.

Enunțul problemei Turnurile din Hanoi
Rezolvarea recursivă pas cu pas
Numărul de mutări: 2^n - 1
Program complet în C++

Problema Turnurile din Hanoi

Enunț: Avem trei tije (A, B, C) și n discuri de dimensiuni diferite, așezate pe tija A în ordine descrescătoare (cel mai mare jos). Scopul este să mutăm toate discurile pe tija C, respectând regulile: se mută un singur disc o dată și nu se poate pune un disc mare peste unul mic.

Cum gândim recursiv?

Pentru a muta n discuri de pe A pe C, folosind B ca tijă auxiliară:

  • Pasul 1: mutăm n - 1 discuri de pe A pe B (folosind C)
  • Pasul 2: mutăm discul cel mai mare de pe A pe C
  • Pasul 3: mutăm n - 1 discuri de pe B pe C (folosind A)
  • Caz de bază: pentru n = 1, mutăm direct discul de pe sursă pe destinație

Funcția recursivă hanoi în C++

Algoritm hanoi(n, sursa, auxiliar, destinatie): dacă n == 1 atunci mută discul de pe sursa pe destinatie altfel hanoi(n - 1, sursa, destinatie, auxiliar) mută discul cel mai mare de pe sursa pe destinatie hanoi(n - 1, auxiliar, sursa, destinatie)
Program C++ - Turnurile din Hanoi
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char aux, char destinatie)
{
    if (n == 1)
    {
        cout << "Mut disc de pe " << sursa << " pe " << destinatie << endl;
        return;
    }
    hanoi(n - 1, sursa, destinatie, aux);
    cout << "Mut disc de pe " << sursa << " pe " << destinatie << endl;
    hanoi(n - 1, aux, sursa, destinatie);
}

int main()
{
    int n;
    cout << "n = ";
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}
Mutările pentru n = 3
1A -> C
2A -> B
3C -> B
4A -> C
5B -> A
6B -> C
7A -> C

Numărul de mutări: 2^n - 1

Notăm cu M(n) numărul minim de mutări. Pentru n discuri, M(n) = 2 * M(n - 1) + 1, cu M(1) = 1. Rezolvând recurența, obținem M(n) = 2^n - 1.

n 2^n - 1
1 1
2 3
3 7
4 15
10 1023

Observă: numărul de mutări crește exponențial (aproximativ se dublează la fiecare disc nou), deci problema devine practic imposibilă pentru n mare.

Exercițiu de completare

Completează enunțul despre Hanoi cu cuvintele potrivite:

În problema Turnurile din Hanoi, se mută un singur ______ o dată și nu se poate pune un disc mare peste unul ______. Cazul de bază al funcției hanoi este atins când n = ______. Numărul minim de mutări pentru n discuri este ______.

Bancă de cuvinte:
disc mic 1 2^n - 1

Exercițiu de completare

Completează structura funcției hanoi:
______ hanoi(int n, char s, char a, char d)
{
    if (n == ______)
    {
        cout << "Mut discul";
        ______;
    }
    hanoi(n - 1, s, d, a);
    hanoi(n - 1, a, s, d);
}
Bancă de cuvinte:
void 1 return

Test de înțelegere

Test rapid - Hanoi:

1. Cazul de bază al funcției hanoi este:

2. Numărul de mutări pentru n = 4 discuri este:

3. În pasul recursiv, pentru mutarea a n discuri de pe A pe C:

Ai grijă la: ordinea tijelor în cele două apeluri recursive - sursa, destinația și auxiliarul își schimbă rolurile, iar o singură greșeală de ordine produce mutări incorecte.

Aprofundare

De ce 2ⁿ − 1 mutări? Fie M(n) numărul de mutări pentru n discuri. Pentru a muta n discuri trebuie: mutăm n − 1 discuri pe tija auxiliară (M(n − 1) mutări), mutăm discul cel mai mare (1 mutare) și mutăm cele n − 1 discuri pe destinație (M(n − 1) mutări). Deci M(n) = 2 · M(n − 1) + 1, cu M(1) = 1, ceea ce conduce la M(n) = 2ⁿ − 1. Pentru n = 64, conform legendei turnului din templul indian, ar fi nevoie de aproximativ 584 de miliarde de ani.

Complexitate și limite practice. Algoritmul are complexitate exponențială O(2ⁿ), deci poate fi folosit doar pentru n mic (de regulă sub 20). Pentru n = 30, numărul de mutări depășește un miliard, iar programul nu s-ar termina într-un timp rezonabil.

Rolul parametrilor. Schimbarea ordinii parametrilor în apeluri este esențială: în hanoi(n − 1, sursa, destinatie, auxiliar), tija care devine „auxiliar" în apelul interior este tocmai destinația din apelul exterior. O greșeală de ordine duce la o soluție incorectă sau la buclă infinită.

Legătura cu stiva. Execuția demonstrează perfect mecanismul LIFO: ultimul apel lansat (mutarea discului cel mai mare) este de fapt afișat în mijlocul secvenței, după ce subproblemele din jur s-au încheiat.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Turnurile din Hanoi

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze succesiunea de mutări necesară pentru a muta n discuri de pe tija A pe tija C, folosind tija B ca auxiliar.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa, câte o mutare pe linie, sub forma „de pe A pe C".

Restricții și precizări:

1 ≤ n ≤ 10.

Exemplu:

Intrare:

2

Ieșire:

de pe A pe B
de pe A pe C
de pe B pe C
Cum gândim soluția:
  1. Definim funcția hanoi(n, sursa, aux, destinatie)
  2. Cazul de bază: pentru n == 1, afișăm mutarea sursă -> destinație
  3. Altfel: hanoi(n-1, sursa, destinatie, aux), apoi mutarea sursă -> destinație, apoi hanoi(n-1, aux, sursa, destinatie)
  4. Apelăm hanoi(n, 'A', 'B', 'C')
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char aux, char destinatie)
{
    if (n == 1)
    {
        cout << "de pe " << sursa << " pe " << destinatie << endl;
        return;
    }
    hanoi(n - 1, sursa, destinatie, aux);
    cout << "de pe " << sursa << " pe " << destinatie << endl;
    hanoi(n - 1, aux, sursa, destinatie);
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Ce învățăm: problema folosește recursivitate dublă: două apeluri recursive în interiorul aceleiași funcții.

PbInfo - Numărul de mutări

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze numărul minim de mutări necesare în problema Turnurile din Hanoi, folosind funcția recursivă mutari(n) = 2 * mutari(n - 1) + 1, cu mutari(1) = 1.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa pe ecran valoarea 2^n - 1.

Restricții și precizări:

1 ≤ n ≤ 30. Rezultatul încape într-un număr de tip long long.

Exemplu:

Intrare:

3

Ieșire:

7
Cum gândim soluția:
  1. Definim funcția recursivă mutari(n)
  2. Cazul de bază: dacă n == 1, întoarcem 1
  3. Altfel întoarcem 2 * mutari(n - 1) + 1
  4. În main citim n și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

long long mutari(int n)
{
    if (n == 1)
        return 1;
    return 2 * mutari(n - 1) + 1;
}

int main()
{
    int n;
    cin >> n;
    cout << mutari(n);
    return 0;
}

Ce învățăm: funcția mutari recreează formula 2^n - 1 prin recurența sa.

EXERCIȚII PRACTICE

Exercițiul Practic: Hanoi în practică

Sarcini de lucru

Rezolvă sarcinile următoare despre Turnurile din Hanoi

Sarcina 1: Programul complet Hanoi

Cerință: Scrie programul C++ complet pentru problema Turnurile din Hanoi cu n discuri, afișând mutările. Testează pentru n = 3 și verifică că obții 7 mutări.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char aux, char destinatie)
{
    if (n == 1)
    {
        cout << "Mut disc de pe " << sursa << " pe " << destinatie << endl;
        return;
    }
    hanoi(n - 1, sursa, destinatie, aux);
    cout << "Mut disc de pe " << sursa << " pe " << destinatie << endl;
    hanoi(n - 1, aux, sursa, destinatie);
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}
Sarcina 2: Completează tabelul

Cerință: Pentru fiecare valoare a lui n, calculează numărul de mutări 2^n - 1 și completează tabelul de mai jos.

Soluție pentru Sarcina 2:
n = 1: 2^1 - 1 = 1
n = 2: 2^2 - 1 = 3
n = 3: 2^3 - 1 = 7
n = 5: 2^5 - 1 = 31

Scrie pe caiet

Titlul lecției

Turnurile din Hanoi. A șasea lecție din Modulul 5 îți arată problema clasică în care recursivitatea este soluția naturală.

Definiția lecției

Problema Turnurile din Hanoi cere mutarea a n discuri de pe tija sursă pe tija destinație, folosind o tijă auxiliară. Se respectă două reguli: se mută un singur disc o dată și nu se pune un disc mare peste unul mic. Rezolvarea recursivă are trei pași: se mută n - 1 discuri pe tija auxiliară, se mută discul cel mai mare pe destinație, apoi se mută n - 1 discuri de pe auxiliar pe destinație. Cazul de bază este n == 1, când discul se mută direct. Numărul minim de mutări este M(n) = 2^n - 1, deci pentru n = 3 sunt 7 mutări. Numărul de mutări crește exponențial, iar problema devine practic imposibilă pentru n mare.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm hanoi(n, sursa, auxiliar, destinatie): dacă n == 1 atunci mută discul de pe sursa pe destinatie altfel hanoi(n - 1, sursa, destinatie, auxiliar) mută discul cel mai mare de pe sursa pe destinatie hanoi(n - 1, auxiliar, sursa, destinatie)

Algoritmul cheie - cod C++

Program C++ - Turnurile din Hanoi
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char aux, char destinatie)
{
    if (n == 1)
    {
        cout << sursa << " -> " << destinatie << endl;
        return;
    }
    hanoi(n - 1, sursa, destinatie, aux);
    cout << sursa << " -> " << destinatie << endl;
    hanoi(n - 1, aux, sursa, destinatie);
}

int main()
{
    int n;
    cout << "n = ";
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Greșeli comune de evitat

Exemplu practic

Scenariu real: un muzeu tehnologic are 3 tije și 3 discuri și vrea să afișeze mutările pentru demonstrație. Numărul minim de mutări este 2^3 - 1 = 7:

Program C++ - Turnurile din Hanoi (exemplu practic)
void hanoi(int n, char sursa, char aux, char destinatie)
{
    if (n == 1)
    {
        cout << sursa << " -> " << destinatie << endl;
        return;
    }
    hanoi(n - 1, sursa, destinatie, aux);
    cout << sursa << " -> " << destinatie << endl;
    hanoi(n - 1, aux, sursa, destinatie);
}

Apelul hanoi(3, 'A', 'B', 'C') afișează cele 7 mutări necesare.

Sfaturi practice și trucuri