{
if (n==1)//если имеется только 1 диск, то это //элементарно
{
fprintf(st1,"Переставить диск номер 1 со столбика %c на столбик %c\n",Source,Dest);
}
else//иначе:
{//сначала перемещаем n-1 диск со столбика A на //столбик B, используя столбик C как вспомогательный
Move_Disks(n-1,Source,Temp,Dest);//вызов процедуры из //самой себя, или рекурсия
fprintf(st1,"Переставить диск номер %d со столбика %c на столбик %c\n",n,Source,Dest);
//затем перемещаем n-1 диск со столбика B на столбик //C, используя столбик A как вспомогательный
Move_Disks(n-1,Temp,Dest,Source);//вызов процедуры из //самой себя, или рекурсия
return;//возврат из ф-ии
}
}
-------------------------------------------------------------------------------------------------------
Лемма 2.Рекурсивный алгоритм «разделяй и властвуй» решения задачи о ханойских башнях дает решение, приводящее к 2^n-1 перемещениям.
Как обычно, из кода немедленно следует, что количество перемещений удовлетворяет условию рекурентности. В данном случае количество перемещений дисков, удовлетворяющее условию рекурентности, определяется формулой:
