Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.6. Ханойские башни. Обработчик события Click кнопки 
Run
 
private void buttonRun_Click(object sender,
EventArgs e) 
{ 
int n = 4; 
for (int i = 0; i < 3; i++) 
ArSt[i] = new MyStack(); //
инициализация сте-
ков 
for (int i = n; i > 0; i--) 
ArSt[0].PushStack(i); //
заполнили стек, соот-
ветствующий 1-му стержню 
Drawing();
Hanoj(0, 1, 2, n); 
} 
Функция рисования башен представлена в листинге 3.7. 
Листинг 3.7. Рисование башен 
void Drawing() { 
int[] x0 ={80,202,324}; 
int y0 = 190; // y max 
int yH = 40; // y min 
int w = 15; // 
полуширина минимального кольца 
int h = 13; // 
высота кольца 
int e; 
gBitmap.Clear(Color.White); 
gBitmap.DrawLine(MyPen0, x0[0], y0, x0[0], yH); 
gBitmap.DrawLine(MyPen0, x0[1], y0, x0[1], yH); 
9 / 23

---

56 
gBitmap.DrawLine(MyPen0, x0[2], y0, x0[2], yH); 
for (int i=0; i <= 2; i++)
{ 
MyStack tmp = new MyStack(); 
while (!ArSt[i].StackIsEmpty())
{ 
e = ArSt[i].PopStack();
tmp.PushStack(e); 
} 
int y = y0; 
while (!tmp.StackIsEmpty())
{ 
e = tmp.PopStack(); n 
ArSt[i].PushStack(e); 
gBitmap.FillEllipse(MySolidBrush,x0[i]-e*w,y, 
2*e*w, h); 
y -= h; 
} 
} 
gScreen.DrawImage(bitmap, ClientRectangle); 
Thread.Sleep(500); 
} 
А как же «конец света»? Время его наступления зависит от числа M(n) 
перемещений колец, выполняемых функцией Hanoj(). Из структуры функ-
ции следует, что
( )
(
)
( )
2
1 1, 
0
0.
M n
M n
M
= ⋅
− +
= 
(3.1) 
Решение этого уравнения имеет вид: 
( )
2
1.
n
M n
=
−
(3.2) 
10 / 23

---

57 
Данный алгоритм имеет экспоненциальную скорость роста O(2
n
). Вре-
мя его выполнения резко возрастает с ростом n и становится весьма значи-
тельным уже при n > 10. 
Ну а что касается легенды, то при числе колец 64 число перемещений 
равно 2
64
– 1 или примерно 10
20
. Если монахи переносят одно кольцо в се-
кунду, то им потребуется свыше пяти миллиардов столетий. Так что время у 
нас еще есть!