Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Лекция VII

Читайте также:
  1. Амплитудная селекция
  2. Беседа как метод обучения детей дошкольного возраста диалогической речи (лекция).
  3. Вводная лекция
  4. Вводная лекция
  5. Вопрос 1.Лекция.
  6. Воскресная лекция Шрилы Радханатхи Свами в Киеве о Бхакти Тиртхе Свами
  7. Временная селекция
  8. Вступительная лекция.
  9. Вступительная лекция.
  10. ВТОРАЯ ЛЕКЦИЯ

Рекурсивный алгоритм решения задачи о Ханойских башнях.

 

Шаг 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 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав