Читайте также: |
|
Рекурсивный алгоритм решения задачи о Ханойских башнях.
Шаг 1: Решить вспомогательную задачу о переносе первых n-1 дисков со стержня А на стержень В. Стержень С использовать как вспомогательный (рекурсивный шаг)
Шаг 2: Перенести диск с номером n со стержня А на стержень С (прямой шаг)
Шаг 3: решить вспомогательную задачу о переносе первых n-1 дисков со стержня В на стержень С. Стержень А использовать как вспомогательный (рекурсивный шаг).
Займёмся выводом формулы для количества переносов n дисков.
Обозначим. Пусть T(n)-количество переносов, которое нужно сделать для переноса n дисков.
Обозначим T(n-1)-количество переносов, которое нужно сделать для переноса n-1 дисков (вспомогательная задача)
T(n)=2*T(n-1)+1
№ шага | Откуда | Куда | № диска |
А | С | ||
А | В | ||
С | В | ||
А | С | ||
В | А | ||
В | С | ||
А | С |
Private Sub click()
Dim a As String, b As String, c As String
a=”A”: b=”B”: c=”C”
Dim n As Long, count As Long
n=cells(1,3)
count=0
call hanoy(n As Long, cout As Long, a As String, b As String, c As String)
If n=0 Then Exit Sub
call hanoy(n-1, count,a,c,b) ‘Шаг1
‘Шаг 2 (перенос диска n)
count=count+1
cells(1+count,4)=count
cells(1+count,5)=a
cells(1+count,6)=c
cells(1+count,7)=n
Call hanoy(n-1,count,b,a,c) ‘Шаг3
End Sub
STACK
Бытовые примеры стека.
-Железнодорожный тупик.
-стопка горшков.
-магазин пистолета.
Принцип(девиз) работы Stack
-Первым пришёл-последним ушёл.
очередь. Первым пришёл-первым ушёл.
Определение.
Стеком называется динамическая структура данных, в которой добавление новых элементов и удаление существующих происходит в специальной точке, называемой вершиной стека.
Стек является основным инструментов для практической программной реализации рекурсии. Он необходим для управления точками возврата рекурсивных алгоритмов (запоминает, куда нужно вернутся после рекурсивного вызова). Он необходим для запоминания параметров рекурсивных процедур. Сама система создаёт СТЕК!
Использование стека рассмотрим на простом модельном примере. Им является задача о проверке правильности расстановки скобок разных типов.
Формулировка задачи:
Пусть дано арифметическое выражение содержание скобки разных типов ((), [], {} и т.д.) Скобка каждого типа может быть либо открывающей, либо закрывающей. Требуется написать алгоритм, проверяющий правильность расстановки скобок.
Алгоритм проверки правильности расстановки скобок разных типов.
На входе алгоритм- символьная скобка с записью исследуемого скобочного выражения.
На выходе из алгоритма- диагностика (сообщение).
Для промежуточного хранения данных алгоритм использует Stack
Шаг 1. Просматривать входную строку слева направо символ за символом.
1.1. если текущий символ- открывающая скобка, то записать её в stack.
1.2. если текущий символ- закрывающая скобка, то:
1.2.1. проверить, пуст стек или нет. Если стек пуст, то ошибка: выдать сообщение об ошибке: «Закрывающих скобок больше, нет открывающих». Работу алгоритма прекратить.
1.2.2. Stack не пуст. Извлечь из него открывающую скобку и проверить типы открывающей и закрывающей скобок. Если типы скобок совпали, то ничего не делаем, а если не совпали, то ошибка: выдать сообщение «несоответствие типов скобок». Работу алгоритма прекратить.
Шаг 2. Проверить Stack. Если он пуст, то скобки расставлены верно. Если не пуст, то ошибка: выдать сообщение: «Открывающих скобок больше, чем закрывающих». Работу алгоритма прекратить.
Private Sub click()
Dim A As String, Otkr As String, Zakr As String, x As String. y As String
Dim Ot As Integer, Za As Integer
Dim I As Integer, L As Integer, TS As Integer ‘Вершина стека
Dim ST() As String ‘Сам стек
Otkr=”([{<”
Zakr=”)]}>”
A=InputBox (“Введите выражение со скобками”+otkr+zakr, “Проверка скобок”)
L=Len(A) ‘В перемещенную L помещаем длину строки А (со скобками)
ReDim ST(L)
TS=0 ‘инициализация стека
For I=1 To L
X=Mid(A,I,1) ‘вырезает i-й символ из строки А, начиная с I, с количеством «1» заданных символов
Ot=Instr(otkr,x) ‘ Записывает порядковый номер в переменную Ot (от 1 до 4)
If Ot <>0 Then
Если текущий символ – открывающая скобка, то записываем его в стек
TS=TS+1
ST(TS)=x
GoTo cont ‘(→стек
End If
Za=instr(zakr,x):If Za=0 Then GoTo cont ‘Проверяем,евляется ли текущий символ закрывающей скобкой.
If TS=0 Then MsgBox “Закрывающих скобок больше” “Проверка скобок” ‘ проверка пуст стек или нет.
Exit Sub
y=ST(TS)
TS=TS-1 ‘стек→(
Ot=instr(otkr y)
If Za<> Ot Then MsgBox “Несоответствие типов скобок”, “Проверка скобок”
Exit Sub
Cont:
Next I
If TS=0 Then
MsgBox “Скобки расставлены верно”,”Проверка скобок”
Else
MsgBox “Открывающих скобок больше”,”Проверка скобок”
End If
End Sub
Дата добавления: 2015-01-07; просмотров: 15 | Поможем написать вашу работу | Нарушение авторских прав |