Turnurile din Hanoi

Se dau 3 tije simbolizate prin a,b,c. Pe tija a se gasesc n discuri de diametre diferite, asezate in ordine descrescatoare a diametrelor. Se cere sa se mute de pe tija a pe b, utilizand ca tija intermediara tija c, toate cele n discuri, respectand urmatoarele reguli:

-la fiecare pas se muta un singur disc ;

-nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametrul mai mic.

Rezolvare:

Daca n=1 se face mutarea ab, adica se muta discul de pe tija a pe tija b.

Daca n=2 se fac mutarile ac,ab,cb.

Daca n>2 . Notam cu H(n,a,b,c) sirul mutarilor celor n discuri de pe tija a pe tija b , utilizand ca tija intermediara, tija c.

Conform strategiei Divide et impera incercam sa descompunem problema in alte doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor. Deci:mutarea celor n discuri de pe tija a pe tija b,utilizand ca tija intermediara tija c, este echivalenta cu:

muatrea a n-1 discuri de pe tija a pe tija c , utilizand ca tija intermediara tija b;

mutarea discului ramas de pe tija a pe tija b;

mutarea a n-1 discuri de pe tija c pe tija b , utilizand ca tija intermediara tija a.

#include<iostream.h>
char a,b,c;
int n;
void h(int n,char a,char b, char c)
{
if(n==1) cout<<a<<b<<” “;
else
{
h(n-1,a,c,b);
cout<<a<<b<<” “;
h(n-1,c,b,a);
}
}
void main()
{
cout<<“n=”;cin>>n;
h(n,’a’,’b’,’c’);
}

{joscommentenable}