Int step(int X, int y)
{ if (Lbr[x][y] == 1 || Lbr[x][y] == 2)
return 0;
if (x == 0 || x == nx || y == 0 || y == ny)
{ Lbr[x][y] = 2;
return 1; // выход
};
Lbr[x][y] = 2; // отметить точку
if (step(x+1, y))
{ Lbr[x][y] = 2; return 1;}
if (step(x, y+1))
{ Lbr[x][y] = 2; return 1;}
If (step(X-1, y))
{ Lbr[x][y] = 2; return 1;}
If (step(X, y-1))
{ Lbr[x][y] = 2; return 1;}
Lbr[x][y] = 0; // снять отметку
return 0;
}
Void main(void)
{ step(1, 2);
for(int i = 0; i < NX; i++)
{ for(int j = 0; j < NY; j++)
printf("%ld ", Lbr[i][j]);
printf("\n"); }
}
Пример. Ханойские башни
Имеются три стержня с номерами 1, 2, 3. На стержень 1 надето n дисков различного диаметра так, что они образуют пирамиду.
Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного.
При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра.
Разработка алгоритма
Пусть требуется переместить три диска.
Чтобы переместить три диска с <1> на<3> нам необходимо сначала переместить два диска с <1> на <2> а потом переместить третий диск(самый большой) на<3>, так как <3> свободен.
Для того, чтобы переместить n дисков с <1> на <3> необходимо сначала переместить n - 1 дисков с <1> на <2> а потом переместить n-й диск (самый большой) на <3>, так как <3> свободен.
После этого необходимо переместить n - 1 дисков с <2> на <3>, при этом использовать стержень <1> как вспомогательный.
Эти три действия и есть рекурсивный алгоритм:
n - 1 дисков переместить на <2>
n-й диск переместить на <3>
n - 1 дисков переместить с <2> на <3>, при этом использовать <1> как вспомогательный
Доказано, что для n дисков минимальное число перемещений равно 2n-1.
#include <iostream>
using namespace std;
#define MAX_RINGS 64 //Макс.число колец
int st[4] [MAX_RINGS]; //1,2,3 - стержни
int nr[4]; // Число колец на стержнях
int nm; // Число перемещений
void Print_st() //Печать расположения колец
{ int i, j;
for(i = 1; i <= 3; i++)
{ cout<<"\n| ";
for(j = 0; j < nr[i]; j++)
cout<<st[i][j]<<' ';
}
cout<<endl;
}
void Init(int rings) //Установка нач. положения колец
{ for(nr[1] = 0; rings > 0; nr[1]++, rings--)
st[1][nr[1]] = rings; //нанизали кольца на 1-й стерж.
nr[2] = nr[3] = 0; //два других стержня пусты
nm = 0;
Print_st();
}
void Move1(int n1, int n2) // Перенос кольца со стержня n1 на n2
{ st[n2][nr[n2]++] = st[n1][--nr[n1]];
Print_st(); // Печать текущей позиции
nm++;
}
void Hanoi(int rings, int i1, int i2, int i3) // Перемещает верхние rings колец со стержня i1 на стержень i3, используя стержень i2 в качестве промежуточного.
1 <= i1, i2, i3 <= 3
{ if(rings == 1)
Move1(i1, i3);
else
{ Hanoi(rings - 1, i1, i3, i2);
Move1(i1, i3);
Hanoi(rings - 1, i2, i1, i3);
}
}