Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Разработка программ для машины Поста - файл LAB_3.doc


Лабораторная работа - Разработка программ для машины Поста
скачать (11.8 kb.)

Доступные файлы (4):

add_2_poz.pst
add.pst
LAB_3.doc67kb.27.04.2007 18:35скачать
золото_1.pst

содержание
Загрузка...

LAB_3.doc

Реклама MarketGid:
Загрузка...

ЛАБОРАТОРНАЯ РАБОТА № 3




Разработка программ для Машины Поста



Цель работы: развить у студентов математическую интуицию, повысить уровень их математической культуры путем закрепления навыков работы на Машине Поста.


  1. Теоретические сведения

    1. Устройство машины Поста

Машина Поста - абстрактная машина, которая состоит из ленты и каретки (считывающая и записывающая головка). Лента бесконечна и разделена на секции одинакового размера. В каждую секцию ленты заносится один символ двоичной информации, который подлежит обработке. Один из символов двоичного алфавита - метка "V", другой - пустота. Если в секцию занесена "V" - секция отмеченная, если в секции "V" нет - секция пустая или неотмеченная.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию. А такая секция называется текущей или обозреваемой.

За единицу времени, которая называется шагом, каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может также распознать стоит или нет метка в обозреваемой ею секции, может заносить метку в пустую секцию и может удалять метку из отмеченной ячейки.

Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции являются недопустимыми.

^

1.2. Система команд машины Поста


Формат команды машины Поста имеет вид: nKm, где:

n - номер текущей команды;

K - команда из системы команд машины Поста (см. табл. 1);

m - ссылка - номер команды, которая будет выполняться следующей.

Последовательность команд из системы команд составляет программу, если:

  1. на n - ом месте этой программы будет стоять команда с номером n.

  2. ссылке m соответствует реальная команда в программе.
^

1.3. Таблица машины Поста


В нее непосредственно вписывается алгоритм решения задачи. В столбце "Номер" формируются номера команд алгоритма, начиная с 1, с шагом 1. В столбце "Команды" указываются команды машины Поста. Они выбираются из выпадающего по нажатию клавиши "Enter" или щелчку мыши списка.

В столбце "Отсылка" указываются номера отсылок, т.е. номер строки, которая должна выполняться следующей. Значения в этом столбце не должны быть меньше 1 и больше номера последней команды. В столбце "Комментарии" можно писать различные пояснения, а можно ничего не писать. При выполнении этот столбец игнорируется. Чтобы удалить, вставить, добавить строки, очистить строки или столбцы воспользуйтесь соответствующими пунктами главного или всплывающего меню или панелью инструментов.

^
Таблица 1. Система команд машины Поста

a --> b

Сдвиг каретки вправо, содержимое ленты не меняется.

a <-- b

Сдвиг каретки влево, содержимое ленты не меняется.

a V b

В обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемая секция пустая, в противном случае команда считается невыполнимой.

a ‡ b

Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемая секция содержит метку, в противном случае команда считается невыполнимой.

a ? b1 , b2

Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть - команде с номером b2. Содержимое ленты не меняется.

a ! [ b ]

Команда останова машины. Содержимое ленты не меняется. У команды остановки ссылка не обязательна.


  1. Задание на работу

2.1. Выполнить на Машине Поста функцию сложения двух чисел, заданных в позиционной системе счисления. В качестве исходных данных использовать две последние цифры в зачетной книжке, заданные в позиционной системе счисления. Пример программы сложения двух чисел, заданных в позиционной системе счисления для машины Поста приведен в табл. 2.


Таблица 2. Пример программы сложения двух чисел для машины Поста

1

<--

2

 

Поиск начала первого числа: сдвигаемся влево

2

?

3

1

до тех пор, пока не встретим неотмеченную ячейку.

3

-->

4

 

Сдвигаемся вправо, на 1-ую метку первого числа и

4



5

 

удаляем ее

5

-->

6

 

ищем конец первого числа: сдвигаемся вправо,

6

?

7

5

пока каретка не встанет на неотмеченную ячейку и

7

V

8

 

ставим метку

8

-->

9

 

проверяем, заполнился ли промежуток между числами

9

?

1

10

если не заполнился - на первую строку, иначе - переход на

10

!

 

 

Конец

2.2. Для машины Поста написать программу, которая ставит метку на позиции справа от текущей позиции каретки.

2.3. Записать в секции ленты 12 меток и составить программу, которая стирает:

а) все нечетные метки справа налево;

б) все четные метки справа налево;

в) все нечетные метки слева направо;

г) все четные метки слева направо.
2.4. Найти на ленте драгоценный камень по методу Успенского.


  1. Порядок работы

Запустить программу Algo2000.exe и при помощи команды ННТЕРПРЕТАТОР перевести ее в режим работы Машина Поста. Используя файл add.pst, изучить принцип программирования на машине Algo2000.exe.
^

3.1. Порядок работы машины Поста


Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Чтобы машина Поста работала, надо задать некоторую программу и некоторое состояние машины (т.е. нужно как-то расставить метки по секциям ленты, в частности, можно все секции оставить пустыми, и поставить каретку против одной из секций).

Работа машины на основании заданной программы происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы. Эта команда выполняется за один шаг, после чего машины приступает к выполнению той команды, номер которой равен отсылке первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение той команды, номер команды которой равен отсылке предыдущей команды.

Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-ом шаге выполнялась команда с номером a, тогда:

1) если эта команда имеет единственную отсылку b, то на (k + 1)-ом шаге выполняется команда с номером b;

2) если эта команда имеет две отсылки b1 и b2, то на (k + 1)-ом шаге выполняется одна из двух команд - с номером b1 или с номером b2;

3) если же выполняющаяся на k-ом шаге команда вовсе не имеет отсылки, то на (k +1) - ом шаге и на всех последующих шагах не выполняется никакая команда – машина останавливается.

Возможные случаи останова машины Поста:

1) в ходе выполнения программы машина дойдет до выполнения невыполнимой команды; выполнение программы прекращается, машина останавливается - происходит безрезультатная остановка.

2) в ходе выполнения программы машина дойдет до выполнения команды остановки;

программа в этом случае считается выполненной, машина останавливается - происходит результативная остановка.

3) в ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда не останавливается - процесс работы машины происходит бесконечно.

^

3.2. Информационная лента машины Поста


Лента состоит из 1999 ячеек, нумерация от -999 до 999. Ячейка с толстой рамкой, находящаяся в центре ленты - каретка. Всплывающее меню ленты вызывается при щелчке правой кнопкой мыши на ленте. При получении фокуса лентой на ней появляется курсор (синий прямоугольник). Его можно сдвигать по ленте вправо и влево клавишами управления курсором. Удерживая клавишу Shift и нажимая клавиши "Влево"/ "Вправо" можно выделить несколько ячеек. Также ячейки можно выделить мышью: удерживая левую кнопку и выделив нужные. Метки ставятся/ удаляются в ячейках, которые выделены. Это можно сделать несколькими способами (лента должна быть сфокусирована):

• клавишей "Пробел"

• щелкнуть мышью на кнопку "V" на панели инструментов

• выбрать пункт главного или всплывающего меню "поставить/ удалить метки"

• двойным щелчком мыши (в этом случае изменение происходит только в одной ячейке).

Клавиши управления курсором "Вверх" или "Вниз" ставят курсор в каретку.

"Home" - курсор в начало видимой части ленты.

"End" - курсор в конец видимой части ленты.

"Ctrl" + "Влево" - сдвиг каретки влево

"Ctrl" + "Вправо" - сдвиг каретки вправо

Кнопки со стрелкой слева и справа от ленты - прокрутить каретку соответственно влево и вправо. Кнопки со стрелкой и вертикальной палочкой слева и справа от ленты - прокрутить каретку соответственно до крайней левой отмеченной ячейки и до крайней правой отмеченной ячейке. Номера этих ячеек указываются в строке состояния как мин и макс соответственно. Можно непосредственно поставить каретку в нужную ячейку, указав ее номер в редакторе над кареткой. Ленту можно запомнить (пункт меню Команда/ Запомнить ленту) и затем восстановить (Команда/ Восстановить ленту).

^

3.3. Исполнение алгоритма машины Поста


Запуск алгоритма на исполнение осуществляется:

• пунктом главного меню Пуск/ Запустить

• кнопкой Запустить на панели инструментов

При этом выполнение программы будет идти до тех пор, пока не встретиться команда стоп или не возникнет какая-нибудь ошибка.

Приостановить выполнение можно:

• пунктом главного меню Пуск/ Пауза;

• кнопкой Пауза на панели инструментов.

Если выполнение не было приостановлено, то оно всегда начинается с первой команды алгоритма. Если была нажата пауза, то можно продолжить выполнение с той команды, на которой машина остановилась. Программу можно выполнить по шагам:

• пунктом главного меню Пуск/ Пошагово;

• кнопкой Пошагово на панели инструментов.

При этом выполнится очередная команда и выполнение приостановится. Полностью прервать выполнение программы можно:

• пунктом главного меню Пуск/ Прервать;

• кнопкой Прервать на панели инструментов.

Регулировать скорость выполнения можно:

• пунктом главного меню Скорость
^ 3.4. Ошибки машины Поста
При возникновении этих ошибок происходит прерывание исполнения алгоритма.

• Не указана команда

• Не указана отсылка

• Неверно указан номер отсылки

• Команды с таким номером не существует

• Нельзя поставить метку, где она уже есть

• Нельзя стереть метку, где ее нет

• Ошибка чтения файла

• Ошибка записи файла


  1. ^ Содержание отчета

Отчет должен содержать название и цель работы, задания на выполнение задач, порядок решения, где необходимо указать последовательность состояний машины при выполнении задачи и полученные результаты.
^ ОСНОВНАЯ ЛИТЕРАТУРА


  1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

  2. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. - М.: Изд-во МАИ, 1992 .

  3. Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов./ Под ред. В.А. Садовничего. – 3-е изд., стер. – М.: Высшая школа, 2002.

  4. Мендельсон Э. Введение в математическую логику. М.: Наука, 1976.

  5. Клини С. Математическая логика. М.: Мир, 1973.

  6. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учеб. пособие. – М.: Логос, 2000. '

  7. Успенский В.А., Семенов А.А. Теория алгоритмов: основные открытия и приложения. М., 1987.



Скачать файл (11.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации