Разбор выражений

1. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

<выражение>  ::= <цифра> | <выражение> + <цифра>  |

<выражение> – <цифра>

2. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

<выражение>  ::= <терм> | <выражение> + <терм>  |

<выражение> – <терм>

<терм>  ::= <цифра> | <терм> * <цифра>

3. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

<выражение>  ::= <терм> | <выражение>+<терм>  |

<выражение>–<терм>

<терм>  ::= <элемент> | <терм> * <элемент>

<элемент>  ::= <цифра> | (<выражение>)

4. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

<выражение>  ::= <цифра> | (<выражение><знак><выражение>) <знак>  ::= + | – | *

5. Проверить правильность выражения, заданного в виде строки S (выражение определяется по тем же правилам, что и в задании 1). Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного (или лишнего) символа в строке S.

6. Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом ("T" — True, "F" — False):

<выражение>  ::= T | F | And (<операнды>) | Or (<операнды>) <операнды>  ::= <выражение>,<выражение>

7. Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом ("T" — True, "F" — False):

<выражение>  ::= T | F | And (<операнды>) | Or (<операнды>) |

Not (<выражение>)

<операнды>  ::= <выражение>  | <выражение>,<операнды>

8. Проверить правильность расстановки скобок в строке S. Текст в строке S определяется следующим образом:

<текст>  ::= <элемент>  | <элемент><текст>

<элемент>  ::= a | b | c | (<текст>) | [<текст>] | {<текст>}

Если текст составлен правильно, то вывести True, иначе вывести False.

9. Проверить правильность расстановки скобок в строке S (текст в строке S определяется по тем же правилам, что и в задании 8). Если текст составлен правильно, то вывести 0; в противном случае вывести номер первой ошибочной скобки или –1, если в строке недостаточно закрывающих скобок.

Деревья

1. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл все возможные пути, ведущие от корня к листьям (каждый путь записывается в отдельной строке файла). Перебирать пути, начиная с "самого левого" и заканчивая "самым правым", при этом первыми заменять конечные элементы пути.

2. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл все пути, ведущие от корня к листьям и удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.

3. Дано упорядоченное дерево глубины N (N > 0 — четное), каждая внутренняя вершина которого имеет два непосредственных потомка: A с весом 1 и B с весом –1. Корень дерева C имеет вес 0. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.

4. Дано упорядоченное дерево глубины N (N > 0) того же типа, что и в задании 3. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен₁|неположителен₂. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.

5. Дано упорядоченное дерево глубины N (N > 0 — четное) того же типа, что и в задании 3. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующим условиям: суммарный вес элементов для любого начального отрезка пути неотрицателен₁|неположителен₂, а суммарный вес всех элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.

6. Подсчитать сумму элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).

7. Подсчитать число узлов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).

8. Подсчитать минимум из чисел, содержащихся в листьях заданного двоичного дерева.

9. Подсчитать максимум элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).

10. Дано вещественное x, целое k. Подсчитать количество чисел, меньших x, в узлах ниже k-ого уровня заданного двоичного дерева.

11. Упорядочить строки данного текстового файла в порядке возрастания их длин.

12. Отсортировать в алфавитном порядке слова в заданном текстовом файле, основываясь на k-ой литере каждого слова. Например, если k=3, то слова должны быть отсортированы по возрастанию значения в третьей литере. Если длина слова меньше k, то будем предполагать, что его k-ой литерой, реально не существующей, служит пробел.

13. Проверить, является ли данное двоичное дерево деревом поиска.

14. В заданном дереве найти поддерево двоичного поиска с максимальным количеством элементов.

15. Реализовать нерекурсивную процедуру печати всех элементов заданного двоичного дерева.

16. Реализовать рекурсивную процедуру печати всех элементов заданного двоичного дерева.

17. Описать логическую функцию, проверяющую на равенство два заданных двоичных дерева.

18. Описать логическую функцию, определяющую, есть ли в заданном двоичном дереве хотя бы два одинаковых элемента.

19. Описать процедуру, которая для заданного N строит двоичное дерево, в котором N полных уровней и на каждом уровне i располагаются узлы, информационные части которых равны i.

20. Дан текстовый файл. Слова содержат не более 20 символов. Определить частоту использования каждого слова в тексте. Результат оформить в виде таблицы, содержащей слова в лексикографическом порядке.

21. Даны два текстовых файла A и В. Максимальная длина слова — 20 символов. Занести в файл С те слова из файла A, которых нет в файле В. Для хранения слов файла В и ускорения поиска среди них воспользуйтесь деревом двоичного поиска.

Графы

1. Найти все вершины графа, недостижимые из заданной.

Указание:

использовать рекурсивную процедуру проверки доступности одной вершины из другой.

2. Раскрасить граф минимальным количеством цветов. Каждая вершина должна быть «окрашена» в цвет, отличный от цвета смежных вершин.

3. Определить, является ли связанным заданный граф.

Указание:

использовать рекурсивную процедуру проверки доступности одной вершины из другой.

4. Найти длину кратчайшего цикла в графе.

5. Определить вершину, удалением которой можно свести граф к дереву.

6. Найти вершину заданного графа, которая принадлежит каждому пути между двумя заданными вершинами.

7. Задана система односторонних дорог. Найти путь, соединяющий города А и Б, не проходящий через заданное множество вершин.

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

9. Найти город в системе двусторонних дорог, у которого сумма расстояний до любого города минимальна.

10. По системе двусторонних дорог определить, есть ли в ней город, из которого можно добраться в любой другой менее чем за 100 км. Разрешается построить дополнительно 3 дороги.

11. По системе двусторонних дорог определить, можно ли, закрыв какие-либо 3 из них, добиться того, чтобы из города А нельзя было попасть в город Б.

12. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города больше N. Определить N-периферию для заданного N.

13. Определить, изоморфны ли 2 графа.

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

15. Найти минимальное множество прямых, на которых можно разместить все точки заданного множества.

16. В 3-мерном пространстве задано множество точек. Найти разбиение этого множества на 2 непустых и непересекающихся множества, чтобы их центры тяжести находились наиболее близко друг к другу.

17. Неориентированный граф называется двудольным, если его можно раскрасить в два цвета так, что концы любого ребра будут разного цвета. Составить алгоритм проверки, является ли заданный граф двудольным (число действий не превосходит N + M).

Указание:

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

Замечание

В этой задаче безразлично, производить поиск в ширину или в глубину.

18. Решить задачу 17 для ориентированного графа (вывести все вершины, доступные из данной по дугам; граф может содержать циклы).

19. Доказать, что алгоритм Дейкстры можно модифицировать так, чтобы для N городов и N маршрутов он требовал не более O(N +K ln N) операций.

Указание:

на каждом шаге выбрать невыделенный город с минимальной стоимостью и скорректировать цены для всех городов, в которые из него есть маршруты. Если известен города, стоимость до которого минимальна, то хватило бы O(n + k) действий. Вычисление минимального элемента в массиве обходится в множитель log n.

20. С эйлеровыми циклами связана задача китайского почтальона, условие которой звучит так: ребрам неориентированного графа приписаны положительные веса. Необходимо найти цикл, проходящий через каждое ребро графа не менее одного раза и такой, чтобы сумма весов с учетом кратности прохождения ребер была бы минимальна.

Замечание

Эта задача часто встречается на практике. Например, при решении задач планирования проверки электрических, телефонных или железнодорожных линий, при решении задач доставки почты или продуктов питания и т. п.