![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
VI.3. Символьное представление чисел ⇐ ПредыдущаяСтр 3 из 3
В
± ± где и вещественных чисел и
где 49. ( 50. (Преобразования из одной формы в другую.) а) Преобразовать целое число б) Преобразовать вещественное число в) Преобразовать вещественное число г) Выполнить обратные преобразования. Указания. а) значение цифры 51. (Операции над числами в символьном представлении.) а) Сложить и перемножить два целых числа вида одинаковой длины. б) Сложить и перемножить два вещественных числа вида
представленных в символьном виде в 52. (Числа-палиндромы.) Палиндромы − это десятичное число, читаемое одинаково туда и обратно. Например,
53. (Точное представление.) Напечатать точное десятичное представление несократимой, рациональной дроби 1 54. (Римские цифры.) а) Записать заданное целое число римскими цифрами. б) выполнить обратное преобразование. Указание. Для записи чисел в римской нотации, которая, заметим, не является позиционной, используются цифры I ( V.1.4. Задачи из раздела " Синтаксис и компиляция" 55. (Распознавание регулярных цепочек символов.) а) Следующая синтаксическая диаграмма дает правило конструирования регулярного выражения из букв
![]() Примерами регулярных выражений, полученных по этой диаграмме, являются: а) Установить, является ли заданная последовательность букв регулярным выражением указанного типа. Указание. Разрешен только однократный просмотр исходной последовательности, т.е. слева направо, без возвратов. б) решить задачу а), считая, что регулярное выражение задается одной из следующих диаграмм (на выбор): Вставить рисунок на стр. 22 Вставить рисунок на стр. 22 Вставить рисунок на стр. 23 Вставить рисунок на стр. 23 56. (Распознавание некоторых синтаксических конструкций.) Используя синтаксические диаграммы, определим следующие конструкции: Имя: Целое: integer Описание имя: , char имя множество [ ] целое , список формальных параметров: integer (имя:) , char ; ВСТАВИТЬ РИСУНОК НА СТР. 23 для заданной последовательности символов установить, является ли она: а) именем, б) целым, в) описанием, г) множеством, д) списком формальных параметров. 57. (Правильная последовательность скобок.) Правильная последовательность скобок (сокращенно: ППС) - это конструкция, определяемая следующей диаграммой: () ППС Вставить рисунок на стр. 24 Для заданной последовательности символов установить, являет ся ли она ППС. Поясняющие примеры. Последовательности ″ ()(())″ и ″ (()())″ являются ППС, а ″ (()))(.)(″ и ″)()()()(″ не являются. Указание. При просмотре последовательности слева направо необходимо контролировать, чтобы число просмотренных закрывающих скобок не превышало числа открывающих. К концу просмотра число закрывающих скобок должно сравняться с числом открывающих. 58. (Язык Дика (слово) [ слово ] Вставить рисунок на стр. 24 Для заданной последовательности символов установить, является ли она. словом языка Поясняющие примеры. Последовательность скобок ″ [(([()]))]()″ является словом языка Указание. От " правильной последовательности скобок " предыдущей задачи " слова" этой задачи отличаются лишь наличием двух сортов скобок. Для контроля правильности закрытия скобок удобно использовать специальный массив-стек. При просмотре исходного текста в стек помещаются только открывающие скобки; если встречается закрывающая скобка, то соответствующая открывающая исключается из стека. Подчеркиваем, что закрыться может только последняя (!) из незакрытых скобок, причем если только она парна текущей закрывающей скобке. Поэтому стек либо заполняется слева, направо, либо освобождается справа налево. Замечание. Можно устранить использование стека, применяя технику, известную в математической логике под названием " гёделизация". Вместо стека заведем целочисленную переменную 59. (Использование стека.) Текст а) Установить, является ли заданный текст допустимым. б) Пусть Пояснения. 1) Стек − это линейный список, в котором все включения и исключения осуществляются на правом конце, называемом вершиной стека. Таким образом, стек либо заполняется слева направо, либо освобождается справа налево. Для моделирования стека здесь рекомендуется использовать массив. 60. (Использование дека с ограниченным выходом.) Текст, составленный из букв а) Установить, является ли заданный текст допустимым. б) Пусть Пояснения. 1) Дек − это линейный список, в котором все включения и исключения (и всякий доступ) возможны на обоих концах списка. Для моделирования дека здесь рекомендуется использовать массив. 2) 61. (Выделение подтерма.) Термы образуются из переменных и функциональных символов. Функциональные символы − это имена функций; каждый функциональный символ имеет размерность (или местность, или арность) − число аргументов функции. Общее определение терма таково: 1) переменная есть терм; 2) если X Y Z О Д Т терм терм терм Например, В заданной последовательности символов, являющейся термом, выделить первый подтерм, начинающийся с функционального символа Указание. Чтобы вычислить номер конечной позиции подтерма, потребуется в процессе просмотра подтерма слева направо считать количество еще незаполненных аргументных мест. 62. (Синтаксический анализ простых арифметических выражений.) Арифметические выражения в скобочной (
Пример записи одного и того же выражения в скобочной и бесскобочной нотациях: Написать программы для проверки правильности запись арифметических выражений в виде Указание. В строке символов Остальное − дело техники. Впрочем, отметим, что синтаксис 63. (Перевод в прямую польскую запись. Обратный перевод.) а) Преобразовать арифметическое выражение, представленное в виде б) Выполнить обратное преобразование (переход от Указания. Предположим, что строка символов а) Алгоритм перевода б) Перевод 64. (Обработка арифметических выражений. Перевод в польскую запись и вычисление значения.) Здесь рассматриваются арифметические выражения, составленные из переменных, знаков операций и круглых скобок. Для обозначения переменных используются одиночные буквы. В качестве знаков операций используются
В отличие от задачи 63, где рассматриваются выражения в полной скобочной записи, здесь некоторые скобки могут быть опущены. Так, вместо а) Преобразовать инфиксную запись арифметического выражения в суффиксную. б) Каждой переменной (букве) арифметического выражения в суффиксной записи сопоставлено некоторое числовое значение. Вычислить значение выражения при обычной интерпретации арифметических операций. Указания. а) Переход от инфиксной записи к суффиксной может быть осуществлен за один последовательный просмотр. Алгоритм преобразования основан на использовании стека − памяти, действующей по принципу " последним пришел – первым ушел": 1) из входной строки, являющейся записью исходного алгебраического выражения, извлекается очередной символ 2) Если 3) Если 4) Если 5) Если 6) Если просмотр выходной строки еще не закончен, то переходим на шаг 1); в противном случае из стека последовательно переносятся все оставшиеся операции. б) Вычисление значения выражения, представленного в суффиксной записи, также основано на использовании стека и может быть осуществлено за один последовательный просмотр: 1) Если очередной символ выражения есть буква, то сопоставляемое ей числовое значение заносится в стек. 2) Если очередной символ выражения есть знак операции В результате такого просмотра в стеке останется только одно значение. Это и есть искомое значение выражения. VI.5. Дополнительные задачи (трудные) 65. (Алгебра блоков.) Последовательность, составленную из литер а) Выполнить преобразования (Запись б) Вычислить блок, являющийся значением выражения вида где Поясняющий пример:
− записи одного и того же выражения соответственно в виде 66. (Аналитическое, или символьное дифференцирование.) Синтаксис конструкции
Пример конструкции (это эквивалент выражения Найти Указание. Правила (l) − (9) рекурсивны: в определении 67. (Печать с выравниванием.) Входной текст представляет собой последовательность слов, разделенных пробелами, запятыми и точками. Напечатать его в соответствии со следующими требованиями:
НАПЕРЁД ЗАДАННОЙ ДЛИНЫ. ПРИ ВВОДЕ ТЕКСТА ЛИШНИЕ ПРОБЕЛЫ ПРЕДМЕСТЗУЩИИИ БУКВАМИ. СЛОВА ПЕРЕНОСИТЬ НЕЛЬЗЯ. ПОСЛЕДНИЙ СИМВОЛ В КАЖДОЙ СТРОКЕ НЕ ДОЛЖЕН БЫТЬ ПРОБЕЛОМ: ПОЭТОМУ ПРИ ПЕЧАТИ МЕЖДУ СЛОВАМИ ВСТАВЛЯЮТСЯ ДОПОЛНИТЕЛЬНЫЕ ПРОВБЛЫ, НО ТАК, ЧТОБЫ ПРОМЕЖУТКИ МЕЖДУ СЛОВАМИ БЫЛИ ПРИМЕРНО ОДИНАКОВЫМИ. ПОСЛЕДНЯЯ СТРОКА НЕ ВЫРАВНИВАЕТСЯ.
68. (Составление подстрочника. − Примитивный перевод с английского на русский.) Предположим, что задан англо-русский словарь, образованный парами 69. (Поиск анаграмм.) Анаграммой слова называется другое слово, полученное перестановкой букв. В заданном словаре русских слов найти все группы слов, являющиеся анаграммами друг друга. Печатать только те группы, которые состоят из двух или более слов. 70. (Головоломка по отгадыванию слов.) Даны список слов и таблица, составленная из букв. Напечатать каждое слово из списка, которое присутствует в таблице, если читать по горизонталям и диагоналям в любом направлении. Для заданного направления каждый из элементов таблицы может быть использован в качестве начального не более чем для одного слова из списка. Пример. Пусть даны список слов (слева) и таблица (справа):
М О С К В А Ь А В О Т С О Р К Л И Н Н Н М О С К В А К Р О С Т О В А Е О С Л Н О Н К А З А Н Ь З Ж Р М И Е Р Л К У Р С К А У Б А Н И Р Д М У Р О М К А Л У Г А Л О К А Л У Г А О Р Е Л
Тогда получаем решение: Р О С Т О В 1, 8 В Л Е В О М О С К В А 2, 2 В П Р А В О К Л И Н 2, 5 В Н И З К А З А Н Ь 6, 1 В В Е Р Х К У Р С К 6, 1 В В Е Р Х – В П Р А В О К А Л У Г А 6, 1 В П Р А В О О Р Е Л 6, 8 В В Е Р Х – В Л Е В О
71. (Проверка решения кроссворда.) Рисунок кроссворда задан целочисленной матрицей. Неотрицательные числа обозначают белые клетки кроссворда а отрицательные − чёрные. Кроме того, положительные числа используются, как обычно, для нумерации клеток, начиная с которых вписываются соответствующие слова по горизонтали и вертикали. Имеется также два списка Установить, являются ли списки Пояснение. Произвольное слово 1) не останется белых клеток, 2) разные буквы не накладываются друг на друга, 3) ни одна из букв не вписана в чёрную клетку. 72. (Декомпозиция кроссворда.) Операция декомпозиции заполненного кроссворда заключается в следующем: 1) клетки кроссворда нумеруются так, как это принято для кроссвордов, 2) составляются списки пронумерованных слов по горизонтали и вертикали, 3) буквы в кроссворде заменяются пробелами. Осуществить декомпозицию кроссворда. 73. (Рисунок кроссворда.) Рисунок кроссворда можно задать матрицей из
Рис.1 (к задаче 73)
74. (Развитие темы задач 1 и 10.) Найти наименьшее множество символов Замечание. Решение задачи заведомо существует. Если Указание. Быть может, при построении 75. (Слова и кривые дракона.) Слово дракона где а) Напечатать все слова дракона порядка
Рис.2 (к задаче 75). Ломаная дракона для слова б) Множество всех слов дракона порядка в) Для заданного слова дракона напечатать рисунок соответствующей ломаной дракона. (На рис. 2 элементы рисунка, подлежащие печати, показаны жирно.) 76. (Скатерть С. Улама, или картинки из простых чисел.) Напечатать картинку, которая получается следующим образом. В клетках поля размером Пример. При |
A/B | |||||||||||
∗ | ∗ | ||||||||||
∗ | |||||||||||