Переместить n-1 дисков с В на С, используя А как вспомогательный.
Переместить оставшийся нижний диск с A на C.
Переместить верхние n-1 дисков с A на В, используя С как вспомогательный.
Иначе
*/
void Mov(int n, char A, char C, char B)
//n - число дисков
//A – исходный стержень, на котором находятся диски
//B – вспомогательный стержень
//C – стержень, на который надо переставить диски
{
if (n==1)
cout<< ”Переставить диск 1 с ” << A << ” на ” << C;
else
{
Mov(n-1,A,B,C);
cout<< ”Переставить диск” << n
<< ”с ” << A << ” на ” << C;
Mov(n-1,B,C,A);
}
}
void main()
{
int n;
cout << ”введите число дисков”;
cin >> n;
cout<< ”решение: ”;
Mov(n, ’A’, ’C’, ’B’);
}
Пример, когда рекурсивный алгоритм становится крайне неэффективным.
Известную в комбинаторике величину «число сочетаний из n элементов по k» можно вычислять как по рекурсивной, так и по нерекурсивной формуле
