7 (Лабораторная работа №7)

Лабораторная работа №7 по информатике: 8 факультет, 1 курс, 1 семестр 2007/08 уч. года Программирование в алгоритмической модели Маркова Краткое описание интерпретатора алгоритмов Маркова Интерпретатор алгоритмов Маркова пмп функционирует на ЭВМ ПЕС А!рЬа в среде НР Тгпб4 (Л~ПХ. Вызов пагп осуществляется из среды интерпретатора команд 1Л~ИХ следующим образом: паж Т-т1 <имя-Файла-с-НАм>. лат Параметр — и включает интерпретацию метасимволов алгоритма. Метасимволы задаются заглавными буквами (А, В, С ) и воспринимаются как любыс буквы алфавита.

Тем самым метасимволы залают группы однотипных правил. В данной системе алгоритмы хранятся в текстовых файлах с расширением . паза, создаваемых с помощью любого доступного редактора текстов. Каждая продукция должна располагаться на отдельной строке. Символы -+ и ~-+ представляются составными знаками (словами) -> и ->. соответственно. Начальные и конечные пробелы слов в левой и правой части правил игнорируются. Протокол работы паза помещается в текстовый файл паза. оие, создаваемый (илн перезаписываемый) в текущей директории. На алгоритмы Маркова, выполняемые пав, налагаются следующие ограничения: ° В состав алгоритма может входить до б2 продукций. Алгоритмы„не удовлетворяющие этому требованию, не интерпретирукпся.

° Нс рекомендуется использовать правила, значащая длина слов в левой и правой части которых превышает 9 знаков. ° Длина входного сообщения и всех сообщений, полученных в результате выполнения подстановок, не мозкет превышать 80.

При нарушении этого требования интерпретация текущего сообщения прерывается. После этого возможна обработка друпк о входного сообщения. Во время работы пап~ экран терминала нмсст следующую структуру: ° в двух верхних строках вводится входное сообщение и отображается текущее обрабатываемое сообщение; ° в третьей строке, выделенной инверсным отображением, выводятся диагностики и предупреждения системы, а также подсказки по горячим клавишам; ° в строках 4 — 24 в несколько столбцов отображается текст алгоритма. Текущая применяемая продукция помечается слева знаком >. После ввода входного сообщения начинается его пошаговая обработка.

При этом пользователь может ввести одну из следующих команд, нажав соответствующую комбинацию клавиш: ВЕТОК ВЕТСВК ВКТСВВ СТВО-С Продолжение пошаговой интерпретации Переход к интерпретации текущего сообщения без остановок Прерывание обработки текущего сообщения Прерывание работы интерпретатора По данной работе проводится входной контроль знаний как по НАМ и по интерпретатору паш, так и по теме "'Представление данных в ЭВМ*'.Ддя с)ол~аиачггхработ в среде МЯ %шс(опз студенты могут использовать другие программы входящие в состав е-хрестоматии к курсу: НАМ (автор Ганущак А. А.), мультнмодельную систему Рыбакова К.

А., а также системы программирования на РЕФАЛЕ (уточнить у доц. Ленинской М. А.). асЫ ( е.1 '1' = <асЫ е.1> 'О' е.2 '0' = е.2 '1'; — 111 Пример алгоритма Маркова, числа: >1 -> 1> >о -> о> > -> < 1< -> <О о< ->. < ->. 1 и программы на РЕФАЛе, добавляющих единицу к изображению двоичного Этот же алгоритм с использованием метасимволов (проф. Титов В.К.): Ещб один пример программирования в марковской модели (доц.

Левинская М.А.) показывает, что алгоритм дифференцирования записьгвастся на РЕФАЛе простой транслитерацией соответствующих математических правил: с11Н 1 е.1 'ь' е.2 = <г1111 е.1> 'ь' <г1111 е 2>г е.1 '*' е.2 = <сИХХ е.1> '"' е.2 '+' <г1111 е.2> '*' е.1г 'х' = '1'г е.1 , <туре е.1>: 'гг' е.2 = 'О'г Другие примеры НАМ приведены в конспекте лекций по курсу. Там же имеются ссылки на литературу по НАМ. Программное обеспечение пега разработано доц.

Журавлевой Т.Э. в ! 995 г. на ЭВМ М(сгоЧАХ П в среде ГгееВЯЭ 4.3. "Всякое слово есть часлгг, всякое число есть слово. " Основггой закоо Кабболы Варианты заданий (~ отмечены задачи повышенной сложности) Кодирование числа в римской записи по Цезарю в алфавите (1,Ъ',Х,1.,С,О,М) (разбирается на занятии).

Входное слово представляет собой два троичных числа без знака, разделенные знаком "-ь". Составить алгоритм вычисления суммы этих чисел. 2. " Входное слово представляет собой два троичных числа без знака, разделенные знаком "-". Составить алгоритм вычисления разности этих чисел. 3. * Входное слово представляет собой троичное число без знака. Составить алгоритм копирования числа. Результат должен состоять нз исходного слова и его копии, разделенных знаком "=".

4. " Входное слово представляет собой троичнос число без знака. Составить алгоритм реверса (инвертирования) числа (записи его цифр в обратном порядке). Составить алгоритм перевода числа из троичной системы счисления в девятиричную. Составить алгоритм перевода числа из девятиричной системы счисления в троичную. Входное слово представляет собой два троичных числа без знака, разделенные знаком "<". Составить алгоритм вычисления троичного логического сдвига первого числа влево на число разрядов второго числа. 8. "* Входное слово представляет собой два троичньгх числа без знака, разделенные знаком ">".

Составить алгоритм вычисления троичного логического сдвига первого числа вправо на число разрядов второго числа. 9. " Входное слово представляет собой два двоичных числа без знака, разделенные знаком "<". Составить алгоритм вычисления двоичного логического сдвига второго числа влево на число разрядов, равное первому числу. 111 " Входное слово представляет собой два двоичных числа без знака, разделенные знаком ">".

Составить алгоритм вычисления двоичного логического сдвига второго числа вправо на число разрядов, равное первому числу. 5. б. 7.* В настоящее время на ЭВМ 13ЕС А1рЬа в среде ГгееВЯ3 (АХР5, б) доступна только экспериментальная версия интерпретатора НАМ со встроенным редактором алгоритмов. Метасимволы в этой версии не поддерживаются. 26 33 34 35 36 ьь 12. ь* 13. "" ьь 15.

'" ф ) 17. * 18. * 19. " 20. ь 21. "" 22. 24. "" 25. 27. 29. *" 30. "" 31. 32 37. ~ь 38 39. ~" 40. 41. " 42. " Входное слово представляет собой два двоичных числа без знака, разделенные знаком "'". Составить алгоритм вычисления двоичного арифметического сдвига второго числа влево на число разрядов, равное первому числу. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "!". Составить алгоритм вычисления двоичного арифмстичсскопз сдвига второго числа вправо на число разрядов, равное первому числу. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "-".

Составить алгоритм вычисления двоичного циклического сдвига второго числа влево на число разрядов первого числа. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "-". Составить алгоритм вычисления двоичного циклического сдвига второго числа вправо на число разрядов первого числа. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "3". Составить алгоритм выделения разрядов первого числа по маске, в качестве которой используется второе число. Входное слово представляет собой два двоичных числа без знака, разделенные знаком 'Ъ".

Составить алгоритм выделения разрядов второго числа по маске, в качестве которой используется первое число. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "ог". Составить алгоритм вычисления поразрядной конъюнкции исходных чисел. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "~". Составить алгоритм вычисления поразрядной дизъюнкции исходных чисел.

Входное слово представляет собой произвольную последовательность десятичных чисел без знака, разделенных знаками "Ф". Составить алгоритм вычисления числа слов в последовательности. Входное слово представляет собой два троичных числа без знака, разделенные знаком " ". Обменять числа местами. Входное слово представляет собой два двоичных числа без знака, разделенные знаком "%". Вычислить наибольший общий делитель исходных чисел. Входное слово представляет собой десятичную запись целого неотрицательного числа в прямой кодировке.

Получить дополнительную кодировку для отрицателъного числа с тем жс абсолютным значением. Входное слово представляет собой десятичную запись целого неотрицательного числа в прямой кодировке. Получить обратную кодировку для отрицательного числа с тем же абсолютным значением. Составить алгоритм умножения двух неотрицательных целых чисел в алфавите Д.

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

Составить алгоритм натурализации десятичного числа в позиционной записи (перевода в единичную систему счисления Щ). Входное слово представляет собой два двоичных числа без знака, разделенных символом "сгсг". Составить алгоритм вычисления логического произведения (его в Си) исходных чисел. Составить алгоритм кодирования слова в латинском алфавите по Цезарю.