Сергей Сергеевич Лебедев
Меню сайта
Категории каталога
Мои статьи [21]
В разработке [1]
Наш опрос
Какими операционными системами Вы пользуетесь
Всего ответов: 100
Главная » Статьи » Мои статьи

Две стороны решения «Ханойской задачи»
Лебедев Сергей Сергеевич
Старший преподаватель кафедры математики и информатики
Коряжемского филиала ГОУ ВПО «ПГУ им. М. В. Ломоносова»
 
ДВЕ СТОРОНЫ РЕШЕНИЯ «ХАНОЙСКОЙ ЗАДАЧИ»
    Идея рекурсивных отношений волнует человечество с древнейших времен. Известно, что на заре зарождения математики ученые интересовались вопросом рекуррентных вычислений. Это подтверждается не только научными трудами тех времен, но даже мифами и легендами. Одну из таких легенд предлагаем вашему вниманию.
    Легенда гласит, что в одном из монастырей Дальнего Востока монахи пытались переместить стопку дисков с одного колышка на другой. Начальная стопка имела 64 диска, нанизанных на один колышек так, что их размеры последовательно уменьшались к вершине. Монахи пытались переместить эту стопку с этого колышка на второй при условии, что при каждом перемещении можно брать только один диск и больший диск никогда не должен находиться над меньшим диском. Третий колышек предоставляет возможность временного размещения дисков. Считается, что когда монахи решат эту задачу, наступит конец света…
    Многие ученые пытались найти решение данной задачи, которая получила название «Ханойская задача». С появлением компьютеров многие решения воспроизводились при помощи языков программирования. Предлагаем нашу* версию, специально разработанную на языке программирования высокого уровня Visual Basic 6.0:
 
Dim m() As Integer    ‘объявление массива отвечающего за положение колец в реальном времени
Dim n, s, X, Y, z, nvkx, nvky, Nk, min, V As Integer
 
Private Sub Command1_Click()
List1.Clear
m: n = Val(InputBox("Введите количество колец", "Ввод количества колец"))
If n <= 0 Then
  MsgBox "Неправильное число колец.", 48, "Wrong data!": GoTo m
End If
ReDim m(1 To 3, 1 To n)
For i = 1 To n
  m(1, i) = i: m(2, i) = 0: m(3, i) = 0
Next
s = 0
Do Until m(3, 1) = 1    ‘построение последовательности перекладывания колец
  s = s + 1
  If n Mod 2 = 0 Then
    If s = 1 Then Call shag(1, 2)
    If s = 2 Then Call shag(1, 3)
  Else
    If s = 1 Then Call shag(1, 3)
    If s = 2 Then Call shag(1, 2)
  End If
  If s = 3 Then Call shag(2, 3)
  If s > 3 Then s = 0
Loop
m(3, 1) = 0
End Sub
 
Private Sub shag(X, Y)    ‘вывод одного шага последовательности перекладывания колец
Call nvk(X, Y)
If m(X, nvkx) > 0 And m(Y, nvky) = 0 Then
  m(Y, nvky) = m(X, nvkx): m(X, nvkx) = 0
  List1.AddItem (X & "-->" & Y)
ElseIf m(Y, nvky) > 0 And m(X, nvkx) = 0 Then
  m(X, nvkx) = m(Y, nvky): m(Y, nvky) = 0
  List1.AddItem (Y & "-->" & X)
ElseIf m(X, nvkx) > m(Y, nvky) Then
  m(X, nvkx - 1) = m(Y, nvky): m(Y, nvky) = 0
  List1.AddItem (Y & "-->" & X)
ElseIf m(Y, nvky) > m(X, nvkx) Then
  m(Y, (nvky - 1)) = m(X, nvkx): m(X, nvkx) = 0
  List1.AddItem (X & "-->" & Y)
End If
End Sub
 
Private Sub nvk(X, Y)   ‘поиск номера верхнего кольца nvkx в столбце X ,а так же номера верхнего кольца nvky в столбце Y
Call Minz(X)
If min = 0 And Nk = n Then
  nvkx = n
ElseIf min > 0 Then
  nvkx = 1
ElseIf min = 0 And Nk < n Then
  nvkx = Nk + 1
End If
Call Minz(Y)
If min = 0 And Nk = n Then
  nvky = n
ElseIf min > 0 Then
  nvky = Nk
ElseIf min = 0 And Nk < n Then
  nvky = Nk + 1
End If
End Sub
 
Private Sub Minz(z)    ‘подпрограмма находит в столбце z массива номер меньшего кольца Nk или номер пустой ячейки
min = m(z, 1)
Nk = 1
For V = n To 2 Step -1
  If min > m(z, V) Then
    min = m(z, V): Nk = V
  End If
  If m(z, V) = 0 Then
    min = 0: Nk = V: Exit For
  End If
Next
End Sub
 
    Проведем поверхностный анализ предложенного кода программы. Основная процедура составлена таким образом, что в ней определяются те действия, которые необходимо выполнить в текущий момент времени при конкретном раскладе дисков. Все эти действия вынесены отдельными процедурами, для упрощения кода программы ввиду частого их использования. Таким образом, программа выполнена в виде «думающего» исполнителя, что является стандартным для классического программирования с обратной связью.
    Совершенно по – другому обстоит дело, если для решения «Ханойской задачи» применить рекурсивный метод. Приводим код программы:
 
Private Sub Command1_Click()
List1.Clear: f = 1: s = 2: t = 3
n = Val(InputBox("Введите количество колец.", "Ввод колец"))
If n > 0 Then
  Proc f, s, t, n
Else
  MsgBox "Неправильное число колец.", vbCritical, "Wrong data!"
End If
End Sub
Sub Proc(f, s, t, n)
If n = 1 Then
  List1.AddItem (f & "-->" & t)
Else
  Proc f, t, s, n – 1: List1.AddItem (f & "-->" & t): Proc s, f, t, n - 1
End If
End Sub
 
    Идея рекурсивной процедуры заключается в том, что она не определяет какие действия необходимо произвести, а лишь указывает, как это нужно делать. Сам подход основан на том, что перемещение постоянно осуществляется с колышка «f» на «t». Тогда задача сводится к определению взаимного расположения всех трех колышков в каждый момент времени. Проведя несколько экспериментов, можно выявить закономерность, по которой определяется взаимное расположение колышков.
    Подведем итог для всего вышесказанного.
    Во–первых, программа написанная с использованием рекурсий является более компактной и выглядит изящно.
    Во–вторых, сложность алгоритма значительно ниже.
    В–третьих, скорость выполнения выше, но за все это приходится расплачиваться увеличением используемых ресурсов оперативной памяти. В коде первой программы постоянно происходит переопределение одних и тех же переменных, т.е. задействованы одни и те же регистры памяти. В то время как к коде второй программы при каждом рекурсивном вызове приходится запоминать предыдущие значения переменных и новые значения, т.е. использовать все новые и новые регистры памяти, что естественно может вызвать переполнения стека памяти при больших входных значениях.
    Кроме того, чтобы использовать рекурсивный метод, программист должен сам выявить закономерности и определить необходимые действия, а в функции, которая будет вызывать сама себя нужно прописать, как будут реализованы эти закономерности.
-----
 * Код программы выполнил студент первого курса математического факультета специальности прикладная математика и информатика Крузин Евгений Сергеевич
Категория: Мои статьи | Добавил: Сергей_Лебедев (19.12.2008)
Просмотров: 703 | Рейтинг: 0.0/0 |
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск
Друзья сайта
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Copyright С.С. Лебедев © 2020Конструктор сайтов - uCoz