Переместить 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» можно вычислять как по рекурсивной, так и по нерекурсивной формуле

int sochet1(int n, int k)

{

if ((k==0)||(k==n))

return 1;

else

return(sochet1(n-1,k)+ sochet1(n-1,k-1));

}

int sochet2(int n, int k)

int i, t, s;

{

if ((k==0)||(k==n))

return 1;

else

{

if (n-k > k) t=k;

else t=n-k;

s = 1;

for (i=1;i<=t;i++)

s=s*(n-i+1))/i;

return s;

}

}

Упр. Сравнить время выполнения рекурсивного и нерекурсивного алгоритмов.

Указатели на функции

Дата добавления: 2013-12-13