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, иллюстрирующий переход от матрицы к соответствующему рисунку кроссворда.

1	0	0	1	0	0	1				1			2	3
0	0	1	0	0	0	0			4			5			6
0	0	0	0	0	1	0			7		8
1	0	0	1	0	0	1	⟹			9			10	11
0	1	0	0	0	0	0			12		13	14
0	0	0	0	1	0	0			16	17				18
1	0	0	1	0	0	1				19			20

Рис.1 (к задаче 73)

74. (Развитие темы задач 1 и 10.) Найти наименьшее множество символов , при котором заданный текст является-перевертышем.

Замечание. Решение задачи заведомо существует. Если − палиндром, то − пустое множество. Не исключено, что выбор не однозначен. Так, текст-словоявляется-перевертышем для .

Указание. Быть может, при построении будет полезно учесть следующий факт. Предположим, что буква входит в текст , но. Кроме того, пусть , где− фрагменты текста , не содержащие буквы , а , − число вхождений буквы в фрагмент . Тогда, если,, для некоторого ,,, то заведомо.

75. (Слова и кривые дракона.) Слово дракона порядка определяется так: значения букв,,,..., выбираются произвольно из алфавита ; Если и, где, то полагаем

где и. (Нетрудно заметить, что имеется различных слов дракона порядка .) Два слова дракона и порядка называют подобными, если после вычеркивания средней буквы эти слова либо совпадают, либо одно получается из другого заменой наина . Каждому слову дракона соответствует ломаная дракона. Она может быть начерчена так. Проведем отрезок (Все отрезки имеют здесь одну и ту же длину.) Далее, если равно , то из точки проведем влево (перпендикулярно к) отрезок ; если же равно, то соответствующий отрезок проведем вправо. Аналогично построим отрезок , соответствующий букв и т.д. На рис. 2изображена ломаная дракона, соответствующая слову дракона.порядка . Изломы отрезков закруглены для наглядности. О словах и ломаных дракона рассказывается, например, в статье [4].

а) Напечатать все слова дракона порядка .

R

L

R

R

L

R

R

R

0'''

L

0''

L

L

R

0

0'

R

L

R

Рис.2 (к задаче 75). Ломаная дракона для слова

б) Множество всех слов дракона порядка разбивается на классы попарно подобных слов..Напечатать по одному слову из каждого класса.

в) Для заданного слова дракона напечатать рисунок соответствующей ломаной дракона. (На рис. 2 элементы рисунка, подлежащие печати, показаны жирно.)

76. (Скатерть С. Улама, или картинки из простых чисел.) Напечатать картинку, которая получается следующим образом. В клетках поля размером , где − заданное натуральное число, располагаются по спирали натуральные числа, начиная с заданного числа , которое помещается в центральную клетку. Затем простые числа заменяют символом ,а составные символом ⊔" (пробел).

Пример. Прииполучаем

A/B	1	2	3	4	5
1	21	20	19	18	17				∗		∗
2	22	9	8	7	16					∗
3	23	10	5	6	15	⇒	∗		∗
4	24	11	12	13	14			∗		∗
5	25	26	27	28	29						∗

Указание. Используйте следующий факт: в клетке с координатами ,записано число

где ,,. Для проверки чисел на простоту полезно заготовить массив из некоторого числа первых простых чисел, , ... От­метим, что число является простым, если ни одно из чиселтакое, чтоне являются делителем числа. Пос­колькуи, то для проверки на простоту лю­бого числадостаточно получить предварительно мас­сив изпервых простых чисел. Для чиселдос­таточнопростых чисел и т.д. Если требуется получить большую картинку, то ее следует печатать по частям.

77. (Календарь.) Напечатать календарь для заданного от­резка времени - месяца,или года.

Указание. Можно использовать следующую формулу для оп­ределения дня недели:

.

Здесь Д − условное число, обозначающее день недели (− вос­кресенье, понедельник,вторник и т.д.),порядко­вый номер года,количество дней от начала года до данно­го календарного числа включительно,иознача­ют соответственно частное и остаток при делениина. От­метим, что в високосном году февраль включает 29 дней, а не 28, как обычно. Год с номеромявляется високосным, есликратно 4; исключение составляют годы, для которыхкрат­но 100 в этом случае годявляется високосным, есликратно.

78. ("Многоэтажная" печать.) Арифметическое выражение, данное в линейной записи, напечатать "многоэтажно".

Поясняющий пример. Выражение может быть напечатано, например, так:

Замечание. Это достаточно сложное и требующее уточне­ния задание. Исходное арифметическое выражение может быть задано, например, в инфиксной или префиксной формах записи.

79. (Печать Паскаль-программы, или познать себя.) На­писать программу на Паскале, которая читает текст произ­вольной (но синтаксически правильной) программы, напи­санной на Паскале в свободном формате, и печатает ее текст -выходную Паскаль-программу− в соответствии с некоторы­ми стандартными правилами. Изготовьте дубликат программы и пусть она родится заново, прочитав свой собственный текст.

Замечание. Общепринятых стандартов по оформлению прог­рамм не существует, однако польза таких стандартов несом­ненна − они направлены на то, чтобы облегчить чтение и по­нимание чужих программ. Полезно ознакомиться с п.Г.4 прило­жения Г книги [6], где приведены некоторые правила распо­ложения операторов; см. также [3] и [8].