Question

Mam rozwiązać problem wieży hanoi w C++

O to program,który przedstawia grę hanoi, wyświetla z jakich palików na jakie trzeba przesunąć krążek i na ilu krążkach chcesz grać.

#include <iostream>
#include <cstdio>
using namespace std;

void hanoi ( int n , char a, char c, char b)
{
if (n==1)
cout << a << " -> " << c << endl;
else
{
hanoi (n-1,a,b,c);
cout << a << " -> " << c <<endl;
hanoi (n-1,b,c,a);
}
}
int main()
{
cout <<"Ile krazkow jest na poczatkowym paliku?";
int ile;
cin>>ile;
hanoi (ile,'A','C','B');


cin.ignore();
getchar();
return 0;
}

lecz nie wiem co trzeba dodać aby program wyświetlał złożoność algorytmiczną, czyli ile było tych przesunięć w zalezonosci od ilosci krazkow:)
Bardzo prosze o pomoc

Answer 1

Zlicza wszystkie przesunięcia. Jak łatwo zauważyć złożonośc tego algorytmu to O()

 

 

#include <iostream>
#include <cstdio>
using namespace std;

void hanoi ( int n , char a, char c, char b, int &i)
{
     i++;
     if (n==1)
     cout << a << " -> " << c << endl;
     else
     {
         hanoi (n-1,a,b,c,i);
         cout << a << " -> " << c <<endl;
         hanoi (n-1,b,c,a,i);
     }

}

         int main()
         {
             int i = 1;
             cout <<"Ile krazkow jest na poczatkowym paliku?";
             int ile;
             cin>>ile;
             hanoi (ile,'A','C','B',i);
             cout << i << endl;
 
             cin.ignore();
             getchar();
             return 0;
          }