16 decembrie 2011

Turnurile din Hanoi

A                 B                 C

Varianta cu Divide et Impera:


#include <iostream>

using namespace std;
int tija[67];
// tija['A'], tija['B'], tija['C'] = nr discuri de pe fiecare tija

void hanoi (int n, char a, char c, char b, int & nm) {

if (n==1) {
tija[a]--;
tija[c]++;
cout<<"Mutarea: "<<a<<"->"<<c<<" (A: "<<tija['A']<<" discuri, B:";
cout<<tija['B']<<" discuri, C: "<<tija['C']<<" discuri)"<<endl;
}
else {
// muta n-1 discuri din a in b, folosind c
hanoi (n-1, a, b, c, nm);
tija[a]--;
tija[c]++;
cout<<"Mutarea: "<<a<<"->"<<c<<" (A: "<<tija['A']<<" discuri, B:";
cout<<tija['B']<<" discuri, C: "<<tija['C']<<" discuri)"<<endl;
// muta n-1 discuri din b in c, folosind a
hanoi (n-1, b, c, a, nm);
}
nm++;
}

int main () {

int n;
int nr_miscari = 0;
char a='A', b='B', c='C';
cout<<"n=";
cin>>n;

tija['A']=4;
tija['B']=0;
tija['C']=0;
cout<<"Initial: (A: "<<tija['A']<<" discuri, B:";
cout<<tija['B']<<" discuri, C: "<<tija['C']<<" discuri)"<<endl;

// muta n discuri de pe tija a pe tija c, folosind tija b
hanoi (n,a,c,b, nr_miscari);

cout<<"S-au folosit "<<nr_miscari<<" miscari"<<endl;
return 0;
}

pentru jucat, apasati AICI
pentru solutia folosind stive, apasati AICI, la cap.3